Puzzle time - prisoners and hats
-
@klaus said in Puzzle time - prisoners and hats:
Q: Do we assume that the prisoners cooperate, even when they won't be among the freed?
Q: Do we know how many distinct colors are on the list?
Yes. The prisoners will.
-
Re your answer I’m afraid the guy can only guess his color from the list of colors
-
Hint - what’s the ideal method if there are only 2 colors, say black and white?
Can an analogous method be scaled to n colors?
-
I can prove that all prisoners must necessarily have the same color.
The proof is by induction on the number of prisoners n.
Base case n = 1: Surely if there's only a single prisoner, he'll have the same color as himself.
Inductive step: n = m + 1.
Pick an arbitrary prisoner p1 and look at the remaining m prisoners (including p2 from below). By induction hypothesis, they'll all have the same color.Now pick a different prisoner p2 and look at the remaining m prisoners (which includes p1). By induction hypothesis, they'll also all have the same color.
This means that p1 and p2 must have the same color as everyone else. So all prisoners must have the same color.
QED.So it's quite easy: all 25 prisoners can be freed!
I'm lucky this turned out so well!
-
For the two color case - black and white:
The last guy in line, who sees all hats except his own, calls out “black”, say, to communicate he can see an odd number of black hats. Otherwise, he says “white”, meaning he can see an even number of black hats.
He of course has only a chance of guessing his own color.
But the next guy will either see the same parity (odd/even) of black hats indicated in the first answer, or not. If he does, he can assume he has a white hat, if not he can assume black. Next in line same, after taking into account any ‘parity switch’ indicated by the second man’s stated color.
By that method all but the last in line (first guy to call his color) are freed.
Is there an analogous method for n colors?
When you shake someone's deep sense of self-worth, leaving a scar in their ego, they will persistently try to diminish you through petty arguments & obsessive captious criticism of your actions, just to soothe the wound.
- Nassim Nicholas Taleb
-
If there are 25 colors, everyone can see ahead of themselves, and know what was said behind them, so they can know the color of their own hat.
-
IT - there can be many people with the same color hat. Also by what method are you assuming the earlier people in line guessed their color correctly?
When you shake someone's deep sense of self-worth, leaving a scar in their ego, they will persistently try to diminish you through petty arguments & obsessive captious criticism of your actions, just to soothe the wound.
- Nassim Nicholas Taleb
-
@jon-nyc said in Puzzle time - prisoners and hats:
IT - there can be many people with the same color hat. Also by what method are you assuming the earlier people in line guessed their color correctly?
"Twenty-five prisoners are given a list of colors ... each will be fitted with a hat whose color is on the list ... each prisoner in turn calls out a color from the list"
"If there are 25 colors, everyone can see ahead of themselves... "
Process of elimination -- this assumes the given list of colors corresponds to the actual hat colors, and there is only one hat per color -- which is implied by "each will be fitted with a hat whose color is on the list ".
-
Are these male prisoners or female prisoners?
8% of men are colorblind and .5% of women are.
-
@lufins-dad said in Puzzle time - prisoners and hats:
Are these male prisoners or female prisoners?
8% of men are colorblind and .5% of women are.
I doubt the puzzle creator even thought of this, due to our systemic visually impaired hatred. This is why those Microsoft people announce their appearance. I think we’ve all learned something from this puzzle - just not what the puzzle author intended.
Let’s try to be kinder and more compassionate to the color blind moving forward.
-
@lufins-dad said in Puzzle time - prisoners and hats:
8% of men are colorblind and .5% of women are.
Mens' eyes matter!
-
@jon-nyc said in Puzzle time - prisoners and hats:
For the two color case - black and white:
The last guy in line, who sees all hats except his own, calls out “black”, say, to communicate he can see an odd number of black hats. Otherwise, he says “white”, meaning he can see an even number of black hats.
He of course has only a chance of guessing his own color.
But the next guy will either see the same parity (odd/even) of black hats indicated in the first answer, or not. If he does, he can assume he has a white hat, if not he can assume black. Next in line same, after taking into account any ‘parity switch’ indicated by the second man’s stated color.
By that method all but the last in line (first guy to call his color) are freed.
Is there an analogous method for n colors?
Big hint: I can use slightly different words to describe this very same method and it will scale to n colors.
-
That’s exactly right.
When you shake someone's deep sense of self-worth, leaving a scar in their ego, they will persistently try to diminish you through petty arguments & obsessive captious criticism of your actions, just to soothe the wound.
- Nassim Nicholas Taleb
