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?
-
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?
Only non-witches get due process.
- Cotton Mather, Salem Massachusetts, 1692
-
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?
@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.
The Brad
-
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.
-
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:
8% of men are colorblind and .5% of women are.
Mens' eyes matter!
-
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?
@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.
