We have $2015$ prisinoers.The king gives everyone a hat coloured in one of $5$ colors.Everyone sees all hats expect his own.Now,the King orders them in a line(a prisioner can see all guys behind and in front of him).The king asks the prisinoers one by one does he know the color of his hat.If he answers NO,then he is killed.If he answers YES,then answers which color is his hat,if his answers is true,he goes to freedom,if not,he is killed.All the prisinors can hear did he answer YES or NO,but if he answered YES,they don't know what did he answered(he is killed in public).They can think of a strategy before the King comes,but after that they can't comunicate.What is the largest number of prisinors we can guarentee that can survive?
Problem
Source: Serbia TST 2015 Problem 3
Tags: combinatorics, puzzle
pco
27.03.2015 18:14
junioragd wrote: We have $2015$ prisinoers.The king gives everyone a hat coloured in one of $5$ colors.Everyone sees all hats expect his own.Now,the King orders them in a line(a prisioner can see all guys behind and in front of him).The king asks the prisinoers one by one does he know the color of his hat.If he answers NO,then he is killed.If he answers YES,then answers which color is his hat,if his answers is true,he goes to freedom,if not,he is killed.All the prisinors can hear did he answer YES or NO,but if he answered YES,they don't know what did he answered.They can think of a strategy before the King comes,but after that they can't comunicate.What is the largest number of prisinors that can survive? I think you mean "the largest number we can guarantee" (else obviously the largest number is $2015$ with a lot of chance). I have a strategy which guarantee at least $606$ survivors. (I supposed that noone knows during the "game" if a prisoner answering YES is killed or not)
junioragd
27.03.2015 18:26
It is known is he killed or not,but even if it is not known there is a strategy for $2012$ to survive(let the first $3$ guys make a strategy to say YES or NO in correspodence what is the sum of other $2012$ guys $mod5$(assign to each hat $0,1,2,3,4$),so there $2^3=8$ possiblites and $5$ possibilities $mod5$).The answer is $2013$(a guy from the problem selection commite told us),but no one at the TST found a strategy for $2013$ to survive.
pco
27.03.2015 18:33
junioragd wrote: It is known is he killed or not,but even if it is not known there is a strategy for $2012$ to survive(let the first $3$ guys make a strategy to say YES or NO in correspodence what is the sum of other $2012$ guys $mod5$(assign to each hat $0,1,2,3,4$),so there $2^3=8$ possiblites and $5$ possibilities $mod5$).The answer is $2013$(a guy from the problem selection commite told us),but no one at the TST found a strategy for $2013$ to survive. Ohhhh, very nice (and shame on me with my poor $606$ )
MellowMelon
27.03.2015 19:21
pco might have made the same mistake I did at first and not realized all prisoners could see all other prisoners. I was getting numbers around 606 for awhile as well. As for a strategy getting 2013, here's one that's essentially brute force:
Let $A$ be #2's hat mod 5 and let $B$ be the sum of #3 through #2015 mod 5. The goal is for everyone to know $B$ after #1 and #2 take their turns.
If $A+B \equiv 0,1 \pmod{4}$ or $(A,B) = (2,2)$ or $(A,B) = (0,4)$, then #1 says no. Otherwise, #1 says yes and guesses whatever. Let $X = 0$ if #1 said no and $X = 1$ if #1 said yes.
If #2 sees $B = 0$, (s)he says no.
If #2 sees $B = 1$, (s)he says yes and guesses hat color $3X$ mod 5.
If #2 sees $B = 2$, (s)he says no.
If #2 sees $B = 3$, (s)he says yes and guesses hat color $3 + 3X$ mod 5.
If #2 sees $B = 4$, (s)he says yes and guesses hat color $2 + 2X$ mod 5.
If you draw out the five by five grid with all values of $A,B$ and all results of the above, you'll see that the results of #1's and #2's guesses uniquely identify $B$ in all cases.
SmartClown
27.03.2015 20:17
I'm stupid.
MellowMelon
27.03.2015 20:18
The strategy I'm using takes advantage of the fact that prisoners can see whether or not the other guy lived, not that they can hear the actual guesses.