Puzzle time - prisoners and hats
-
@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!!
-
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.
-
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.
-
@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.
-
@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
