Am I red, or Am I blue?
There are 100 criminals in a jail and the jailor gets a change of heart and wants to release them. But he does not want to release them just like that, he wants to play a game with them. He announces that the next day, he will be putting hats, either blue or red, in equal randomness, on each of the prisoner's heads and all the prisoners will be lined up facing in one direction in a single file. So the last prisoner is able to see all the others' hats except of course his, the last but one will be able to see all the others except his and the last prisoner's, and so on...Basically they all can see what is in front of them. The first prisoner is unable to see any prisoner's hat as he is the first guy. The prisoners will be blindfolded until the jailor completes the task of putting the hats and then the blindfold will be removed. Once the blindfolds are removed, the jailor starts from the back and asks the color of the hat the prisoner is wearing. If the prisoner guesses the color of his own hat correctly, he survives, if not he is shot. To make things spicy, lets say the jailor allows others only to hear prisoner say the color of his hat and not whether he was correct or wrong. The prisoners are dismissed for the night. They discuss a strategy and come up with an optimal solution of saving lots of their fellow buddies. To top it all off, the jailor has a microphone bug inside the cell and he is able to hear their plan. So what is the strategy of the prisoners and how do they make sure lots of their folks are saved in the cruel game played by the jailor?Once you solve the problem, lets try to get a generic methodology for a 'N' prisoner and 'K' different colors of the hats put in random. How many prisoners can be saved at a maximum and how many will be killed at a minimum?
Level: Hard
(Image courtesy: www.londonstimes.us/toons/index_misc.html, I have put in the red and blue hats for those prisoners)
posted by Karthik Nagaraj at
7:09 AM
3 Comments:
Given 100 prisoners X1 to X100
all standing in a single file facing the same direction.X1 is the last and X100 is the first
x1 can see x2 to x100
x2 can see x3 to x100, x2 can hear x1
x3 can see x4 to x100, x3 can hear x1,x2
say red = 0 and blue = 1
Hence
x1 can perform a XOR of x2 till x100 and give out the result. It may be right or wrong.
X2 does a XOR of X3 till X100 and then XORs the same result with what X1 has said.
This will be the right color of his cap.
X3 does similarly.
XOR of all the people before him and XOR of all the people behind him. He also gets the right answer.
All the prisoners use the XOR operation to give out their right color.
Only X1 may fail.
Atleast 99 prisoners can be saved.
Mayura,
Good thinking the solution is almost correct but not complete. I liked your EXOR idea. What about the last prisoner, how will he tell his hat color, he can only EXOR the previous responses given to him and that may or may nor be correct right. Take this example of 7 prisoners and the binary of Read and Blue is like this:
RBBBRRB
So the last prisoner from the right would see the following in his binary representation:
111000, so his computed answer is 1 -> Blue, not correct! The bit on the right is 0 because the the first guy exor all he sees in front of him and it turns out to be RED, so 0. Then on all will be the color of their own hats.
So lets make one small change to the last prisoner's way of thinking -> He exors all the previous replies and then exors the reply to itself. Then he can get the right color of his hat.So that would complete your idea of the solution.
Now, what about the case of the N hat and K-color scheme? How do you plan on applying the exor scheme here? My clue to you - think what really exor does to the answers and why everyone else can get their answers right based on 1 reply from the 1st guy. Think about it, you are almost there.
Ok, time's up guys! Mayura almost got the answer right but his methodology cannot be generalized for a N person, K-hat scheme.
So here is one way we can work things out: All the prisoners discuss that the last guy (the who is able to see everyone's hat) will be the key for this victory. If he sees an odd number of RED colored hats then he will shout out RED and if he sees an even number of RED colored hats then he will shout out BLUE. Now we do not know if that guy survived or not, but henceforth any guy can count the # of red hats in front of him and deduce the color of his hat accordingly. So all the 99 remaining prisoners can save themselves. The last prisoner has only certain amount of chance to survive which is probably about 50-50 chance - if he says red and it is correct or if he says blue and it is wrong. and so on...
Now consider the N-person with the K-color hat scheme - The key to save maximum people is in the hands of the last K-1 people who can see N-1, N-2,...N-K+1 in front of them. Each one agrees on the same methodology that the previous guy up till the N-K+2nd prisoner will count the # of his designated color hat and tell out one or the other color. depending on whether it is even or odd.
Lets dry run this example with 10 prisoners and 3 hats. Lest say the jailor places the hats in this fashion
RBYYBYRYBB
R=red
B=blue
Y=yellow
Now starting fron the right the 1st guy will count the # pf R. It is even so he will B. The second guy counts the # of Y, it is even, so he will tell B. Now the 3rd guy counts both the # of R and Y, he finds that the # of R is still even, but the # of Y is now odd. So his color must be Y. Henceforth all the prisoners can name the color of their hat correctly. So at least N-K+1 prisoners can be saved.
This method is foolproof even if the jailor has heard every word of their plan (unless the jailor decides to change the color of the hats dynamically, which is not given so it is out of the scope of this question). So I guess this puzzle is SOLVED!
Subscribe to Post Comments [Atom]
<< Home