Thursday, July 12, 2007

Know the color or die puzzle

The puzzle calls for a planning for life :D.

A medieval age mad king devices another mad trick for his fun that plays on life of his best 100 men.

He calls them and line them up and then places a red or a white cap on everyone's head. After lining up they are not allowed to communicate among themselves and can only look at all the men in front of them , not himself and not behind the person himself.

He then tells them to that he will start from the end of the line and ask the person the color of the cap he is wearing (from the person in the line from whom the question is asked) . If he is correct he survives and stays there, and if incorrect he dies silently and the other in front of him wont even know about it. He will keep on moving until he reaches the first person in line.
Any break in rule or devising a way to communicate among themselves calls for killing of all of them.

Now, what is the maximum number of men that can survive for sure? Whats the plan?

1. Now, is this a trick question? It says he will ask the men what color of cap he is wearing-by "he" do you mean the king? If so, all 100 men can survive because they can all look at the king and tell him what color of cap the king's wearing.

2. No .. its not a trick question..

By the color of the cap means, the color of the person's cap from whom the king is asking the question

3. Half of them will always survive. Last one will tell the color of cap of the person in front of him.so that next person will know the color on his head. He may or may not die depending upon the color of his cap.But the next person ll tell the truth and will be saved. This will be repeated.

4. I can get 99 to survive for sure!
OK. White = "W"(0) Red ="R"(1)
Last man(first who is asked) checks if he can see even number
of WHITE caps.
If it's true - he says "WHITE", otherwise - "RED". He lives or dies.
The next person in the Queue checks if parity of WHITE caps of people in front of him is the same
as said by 1 guy. If it's true - he has RED cap and says "RED" otherwise "WHITE".
He lives.
All other people in front of him update their 'caps parity'
(prev_cap-parity, Color_said)
->new_cap-parity :
(W,W)->R, (W,R)->W, (R,W)->W, (R,R)->W.
All guys after 2nd guy acts as follows:
0. Update cap-parity after hearing the guy questioned before
1. Check parity of WHITE caps in front of him("W", "R").
2. If these parities are the same - he has RED cap(since his own cap doesn't change the parity) and say "RED", otherwise he says "WHITE". The man survives.

So only first guy can die and the rest will survive(99).

5. This comment has been removed by the author.