Puzzle time - prisoners and hats
-
wrote on 11 Nov 2021, 11:55 last edited by
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?
-
wrote on 12 Nov 2021, 02:27 last edited by
Have to think about this more, but I assume that the prisoners can trade hats?
-
Have to think about this more, but I assume that the prisoners can trade hats?
wrote on 12 Nov 2021, 03:12 last edited by@taiwan_girl said in Puzzle time - prisoners and hats:
Have to think about this more, but I assume that the prisoners can trade hats?
Yes. They are trading their hats - which is a metaphor for their very souls, in this puzzle - for their freedom. Their very freedom. I suspect they are God-fearing conservatives, with the hats colored red, with four simple letters on the front. MAGA.
God bless Donald Trump, God bless America, and God damn imprisonment! I bet they are all minorities, falsely imprisoned!
The color of their hats? The color of freedom. Sanctified freedom, AMEN!! MAGA!!
-
wrote on 12 Nov 2021, 03:13 last edited by
Is that the correct answer, jon?
-
wrote on 12 Nov 2021, 06:10 last edited by
Let's establish a baseline.
Assuming that the prisoners would be willing to cooperate even if they are not freed, I think there's a baseline solution that would set 12 prisoners free:
The odd-numbered prisoners sacrifice themselves and call out the color of the guy in front of them. Which means that 12 of the 25 can be freed.
So, all we have to do now is improve on 12.
-
wrote on 12 Nov 2021, 06:20 last edited by Klaus 11 Dec 2021, 06:23
Ah, I do have a solution to set 24 free.
(spoilers don't work right now. Damn lazy and incompetent forum admin).
Let's call the colors c-1, c-2, c-3, ... . (These are not the colors of the prisoners but an enumeration of all colors).
Let d-1, ..., d-25 be the colors of the prisoners.
Let p-1=2, p-2=3, p-4=5, ... be the sequence of prime numbers.
The last prisoner sees all colors and computes the number
n = (p-1^d-1)(p-2^d-2) ... * (p-24*d-24).
and calls out c-n.
Thanks to the unique factorization theorem, every d-i can be uniquely computed from n, hence every other prisoner can reconstruct his color from the first color.
Problem solved.
(well, the prisoners would need to be quite good at distinguishing a very large amount of different colors
)I think in general the strategy needs to be to encode multiple colors into one color. I've described the limit case.
-
wrote on 12 Nov 2021, 06:25 last edited by Klaus 11 Dec 2021, 06:25
@jon-nyc said in Puzzle time - prisoners and hats:
calls out a color from the list
Ah, damn, missed that one.
I think the same basic strategy - enocde multiple colors into one - still applies, but now it all depends on how many colors are on the list - which Jon hasn't told us.
-
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?
wrote on 12 Nov 2021, 07:33 last edited by jon-nyc 11 Dec 2021, 07:35@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.
-
wrote on 12 Nov 2021, 08:00 last edited by
Re your answer I’m afraid the guy can only guess his color from the list of colors
-
wrote on 12 Nov 2021, 08:03 last edited by
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?
-
wrote on 12 Nov 2021, 08:24 last edited by
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!
-
wrote on 12 Nov 2021, 08:54 last edited by
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?
-
wrote on 12 Nov 2021, 14:18 last edited by
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.
-
wrote on 12 Nov 2021, 14:55 last edited by
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?
-
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?
wrote on 12 Nov 2021, 19:48 last edited by@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 ".
-
wrote on 12 Nov 2021, 19:51 last edited by
Number of colors on the list was never specified in the original problem.
-
wrote on 12 Nov 2021, 20:12 last edited by
Are these male prisoners or female prisoners?
8% of men are colorblind and .5% of women are.
-
Are these male prisoners or female prisoners?
8% of men are colorblind and .5% of women are.
wrote on 12 Nov 2021, 20:37 last edited by@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.
wrote on 12 Nov 2021, 21:02 last edited by@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?
wrote on 14 Nov 2021, 05:58 last edited by@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.