Puzzle time - prisoners and hats
-
wrote on 3 Aug 2020, 20:25 last edited by
Three prisoners are told that at midnight, in the dark, each will be fitted with a red or blue hat according to a fair coin flip. The lights will then briefly be turned on, enabling each prisoner to see every other prisoner's hat color. Once the lights are on, however, the prisoners will have no opportunity to signal to one another or to communicate in any way.
Each prisoner will then be taken aside and given the option of trying to guess whether his or her own hat is red or blue, but he or she may choose to pass. All three prisoners will be freed if (1) at least one prisoner chooses to guess his or her hat color, and (2) every prisoner who chooses to guess guesses correctly.
The prisoners have a chance to devise a strategy before the game begins. Can they achieve a winning probability greater than 50%?
-
wrote on 3 Aug 2020, 20:35 last edited by
Argh! Argh!! ARGH!!! This brings back memories! It was assigned to us in a Logic course when I was a dewy young thing . . . I solved it, but it took me two weeks! And I thought of nothing else the whole time! The solution was so ornate that I had to write it down before I forgot it. I was obsessed with this puzzle! It was love-hate!
Argh!!!
-
wrote on 3 Aug 2020, 20:57 last edited by
Possibly, but I think there are a lot of puzzles of this type.
-
Three prisoners are told that at midnight, in the dark, each will be fitted with a red or blue hat according to a fair coin flip. The lights will then briefly be turned on, enabling each prisoner to see every other prisoner's hat color. Once the lights are on, however, the prisoners will have no opportunity to signal to one another or to communicate in any way.
Each prisoner will then be taken aside and given the option of trying to guess whether his or her own hat is red or blue, but he or she may choose to pass. All three prisoners will be freed if (1) at least one prisoner chooses to guess his or her hat color, and (2) every prisoner who chooses to guess guesses correctly.
The prisoners have a chance to devise a strategy before the game begins. Can they achieve a winning probability greater than 50%?
wrote on 3 Aug 2020, 21:30 last edited by@jon-nyc said in Puzzle time - prisoners and hats:
The prisoners have a chance to devise a strategy before the game begins. Can they achieve a winning probability greater than 50%?
The crux of this problem is really the question of what type of prisoners they are. If they are highly educated political prisoners currently serving time for example in a Chinese prison due to their resistance to the measures being undertaken against democracy in Hong Kong, then yes, I would say that there is a better than 50% chance that they will be able to devise a strategy.
If they are the more typical type of prisoner serving time for robbing liquor stores or attempting to sell drugs to schoolchildren, then I would put their chances of coming up with a winning strategy at about 1%.
Of course, the point is moot, since the chances of the Chinese prison authorities giving them stupid hats on the basis of a coin flip are remote at best.
-
wrote on 3 Aug 2020, 22:22 last edited by
That puzzle sounds familiar. Didn't we have that in the past?
-
wrote on 3 Aug 2020, 22:34 last edited by
I don't think so. There are a number of 'prisoner hat' problems.
-
wrote on 4 Aug 2020, 14:48 last edited by
@jon-nyc said in Puzzle time - prisoners and hats:
Possibly, but I think there are a lot of puzzles of this type.
Such as these.
Give me some more time. I know there are many "color of your hat" puzzles, but I'm pretty sure I've also seen one involving probabilities in the past. Maybe not exactly that one.
-
wrote on 4 Aug 2020, 15:02 last edited by
I think I now remember where I saw the puzzle.
There's a mathematician who publishes such puzzles on a regular basis, Peter Winkler. He has a monthly column in the "Communications of the ACM", of which I'm a subscriber. I believe I saw that puzzle there. If I think about the puzzle more, I may remember parts of the solution, so I guess I better just keep my mouth shut.
-
wrote on 4 Aug 2020, 15:37 last edited by
I guess the set of rules would attempt to clump wrong guesses together while right guesses would tend to be alone. The rules would also want to ensure that at least one person guessed.
-
wrote on 4 Aug 2020, 15:45 last edited by
If they were that smart they wouldn't be prisoners, now would they?
-
wrote on 4 Aug 2020, 15:48 last edited by
Tell that to Stalin and his pogroms against intellectuals.
-
I guess the set of rules would attempt to clump wrong guesses together while right guesses would tend to be alone. The rules would also want to ensure that at least one person guessed.
wrote on 4 Aug 2020, 18:35 last edited by@Horace said in Puzzle time - prisoners and hats:
I guess the set of rules would attempt to clump wrong guesses together while right guesses would tend to be alone. The rules would also want to ensure that at least one person guessed.
So, is the answer that simple? Those who see two different colors would not vote. If the other two people are same, guess opposite? This will cause any configuration of colors other than all-same to be a win (one correct vote), while all-same would be a loss (3 wrong votes).
-
wrote on 4 Aug 2020, 18:39 last edited by
- Do the prisoners know (or can determine) the order in which they are asked?
- Can the prisoners hear all the answers?
-
wrote on 4 Aug 2020, 18:48 last edited by
Oh, I think I now remember the key to the solution. The probability can be raised to 75%.
-
wrote on 4 Aug 2020, 18:51 last edited by Horace 8 Apr 2020, 18:52
Yes that is the % of my proposed solution. I got there by figuring that each guess would be 50/50 so the rules would have to clump wrong guesses together and single out right ones. One such set of rules leaves 75% of color combinations yielding one right guess.
-
wrote on 4 Aug 2020, 20:36 last edited by
I got the same answer as Horace.
Official answer comes out Saturday but I cant see them improving on 75%.
-
wrote on 4 Aug 2020, 20:43 last edited by
It gets interesting if you generalize the number of prisoners and/or the number of colors.
-
wrote on 4 Aug 2020, 21:02 last edited by
Oh man, you ruined the bonus round.
