|
The king of some faraway land is bored, so he decides to setup a little game for his own amusement. These are the rules of the game:
7 prisoners will be seated at a round table. Each prisoner will have a hat placed on their head. Each hat is one of seven possible colors. The prisoners can see everyone else's hat, but they cannot see their own. The prisoners will then write on a piece of paper what they think their hat color is, and hand the paper to the king.
If any of the prisoners guesses their hat color correctly, they will all go free. Otherwise, they are all executed on the spot.
If the prisoners use the naive strategy of guessing randomly, then they have a survival chance of 66%. Can you think of a strategy such that the prisoners have a 100% chance of survival?
Clarification:
1) There are no restrictions on how many of each color there are. The prisoners could all be wearing hats of the same color, or they could also all be wearing hats of different colors.
2) The prisoners cannot communicate in any way to each other after being seated on the table.
3) You know which 7 colors are in the pool of possible colors.
Edit: Karlsberg posted an almost right solution, which prompted me to post the actual solution.
+ Show Spoiler [solution] +
We assign each color a number from 0-6
Now we can say that the prisoners are essentially getting a number, c0,c1,c2,c3,c4,c5,c6.
S = (c0 + c1 + c2 + c3 + c4 + c5 + c6) modulo 7
S has seven possible values, 0-6
At this point, what each prisoner is doing is trying to guess what S is, and solving for their own number to match S.
Prisoner 0 assumes S = 0, and solves the equation c0 = S - (c1+c2+c3+c4+c5+c6)
Prisoner 1 assumes S = 1, and solves the equation c1 = S - (c0+c2+c3+c4+c5+c6)
and so on..
At least one of the 7 prisoners will assume the correct S value. That prisoner will be able to guess the correct number for their own hat.
 
|
I believe you forgot the important rule that states no prisoners can communicate in whichever way with one another.
Otherwise, the game would end readily after a few questions are asked.
I will try to think of a solution without communicating.
|
1.Look at everyones hat, pass it around. So then you can look at other people's hats(aka, no longer your hat)
2.Say white, because that's the combination of all colors.
3.Say "Brow...*look at their reaction* I MEAN... gree...*look at their reaction. Finds approval.* Green
4.Technically, if you try to find a loophole, its just a random hat placed on their head. So they are not allowed to look at there OWN hat, by its not their hat. It's the king or someones. So they can just take it off and look at it.
|
i have a feeling that the answer isn't going to be one that'll make me go "OH THATS SMART" but rather "oh... -_-"
|
you may have mixed up two different puzzles into one combo puzzle that doesn't make sense.
|
this is tricky. let's look at the two extreme situations:
1) all the same color. to win in this situation, your strategy must select a color inside of the colors you see on other people's heads.
2) all different colors. to win in this situation, your strategy must select a color outside of the colors you see on other people's heads.
so your strategy is going to have to be a function of the distribution of colors you see.
|
Are they allowed to agree on a timing system beforehand?
|
On September 10 2010 05:54 Nytefish wrote:
Are they allowed to agree on a timing system beforehand?
that won't help considering they don't even know what colors are in the pool of hats except whats in front of them. the classic puzzle i know of only involves n colors, and 2n people, in which case a timing system works.
|
Taking out all possible forms of loopholes, how can a 100% survival rate be achieved since they all could guess incorrectly.
|
On September 10 2010 05:53 AcrossFiveJulys wrote:
this is tricky. let's look at the two extreme situations:
1) all the same color. to win in this situation, your strategy must select a color inside of the colors you see on other people's heads.
2) all different colors. to win in this situation, your strategy must select a color outside of the colors you see on other people's heads.
so your strategy is going to have to be a function of the distribution of colors you see.
I am bad at math but I doubt this will hit the 100% required.
I am guessing that the answer will be arrived at through a logical leap instead of math.
Question: Do they know what colors are available?
|
On September 10 2010 05:57 seRapH wrote:Show nested quote +On September 10 2010 05:54 Nytefish wrote:
Are they allowed to agree on a timing system beforehand? that won't help considering they don't even know what colors are in the pool of hats except whats in front of them. the classic puzzle i know of only involves n colors, and 2n people, in which case a timing system works.
i think they know the colors in the pool, otherwise in the example i brought up there's no way to win 100% when all colors are different.
|
Hungary11238 Posts
I wonder how the prisoners have a chance of 66% by guessing randomly. If they pick 1 / 7 (given they know the seven available colors), they have a 14% chance of getting it right. Doing it 7 times is 100%, so statistically one should get it right.
Or am I missing something?
|
On September 10 2010 05:58 LunarDestiny wrote:
Taking out all possible forms of loopholes, how can a 100% survival rate be achieved since they all could guess incorrectly.
It can't.
There must be a "logical trick" based on lack of information.
If the problem is "your hat could be any of 7 colours regardles of what you see, guess what it is out of 7 colours" you could play this game a million times and never guess right.
So the "trick" must allow prisoners to pass some form of information to each other.
|
I have updated the post with clarifications.
@tissue: They know the 7 possible colors
|
On September 10 2010 06:05 Aesop wrote:
I wonder how the prisoners have a chance of 66% by guessing randomly. If they pick 1 / 7 (given they know the seven available colors), they have a 14% chance of getting it right. Doing it 7 times is 100%, so statistically one should get it right.
Or am I missing something?
In case you aren't trolling it's 1 - 6/7 ^ 7 I believe, which comes to almost exactly 66%.
Flipping a coin is 50/50. Doing it twice doesn't mean you will have a confirmed heads or tails.
|
On September 10 2010 06:05 Aesop wrote:
I wonder how the prisoners have a chance of 66% by guessing randomly. If they pick 1 / 7 (given they know the seven available colors), they have a 14% chance of getting it right. Doing it 7 times is 100%, so statistically one should get it right.
Or am I missing something?
that's a common misconception about probability. Here's a hint as to why that's not right. If they each had 2 chances, do you think they have a 14*14 = 196% chance of winning?
|
Hello!
lurked at this site for some time and couldn't resist EDIT but didn't have the solution... EDIT
|
On September 10 2010 06:02 AcrossFiveJulys wrote:Show nested quote +On September 10 2010 05:57 seRapH wrote:On September 10 2010 05:54 Nytefish wrote:
Are they allowed to agree on a timing system beforehand? that won't help considering they don't even know what colors are in the pool of hats except whats in front of them. the classic puzzle i know of only involves n colors, and 2n people, in which case a timing system works. i think they know the colors in the pool, otherwise in the example i brought up there's no way to win 100% when all colors are different.
even then its mathematically impossible to have a 100% correct rate PER PERSON. your hat color is not affected by anyone else's.
the only solution i can think of is if the prisoners get to talk beforehand:
The first person will write a color of a hat he sees, show it to everyone, and give it to the king. everyone else writes that same color. but this involves a form of communication, and so feels gimmicky 
|
On September 10 2010 06:05 Aesop wrote:
I wonder how the prisoners have a chance of 66% by guessing randomly. If they pick 1 / 7 (given they know the seven available colors), they have a 14% chance of getting it right. Doing it 7 times is 100%, so statistically one should get it right.
Or am I missing something?
What you just calculated is the expected number of correct guesses if they all guess randomly. They only need one correct guess, and sometimes they can all guess wrong.
The correct way to calculate their chance of survival is like this:
Each prisoner has 1/7 of getting it right, which means 6/7 chance of getting it wrong.
The probability that all prisoners are wrong is (6/7)^7.
The probability that at least one gets it right is 1 - (6/7)^7 = .66
|
On September 10 2010 06:05 Aesop wrote:
I wonder how the prisoners have a chance of 66% by guessing randomly. If they pick 1 / 7 (given they know the seven available colors), they have a 14% chance of getting it right. Doing it 7 times is 100%, so statistically one should get it right.
Or am I missing something?
Not quite..... If the first one guesses correctly (which is a 1/7 chance), then the game is over.
If not, then the chance that the second one will guess correctly is 6/7 (chance of the first one being wrong) * 1/7 (chance of the 2nd one guessing correctly).
If the 2nd one does not get it, then the 3rd has the chance of (6/7)^2 * 1/7
The 4th then has the chance of (6/7)^3 * 1/7
etcetera.....
The chance that at least one gets it is the sum of these percentages. Which, no matter how many people there are, will never actually be 100%.
|
|
|
|
|
|
EPT
