They agree on the following plan: The prisoner at the back of the line counts up the number of red hats he sees. If the number is odd, he says "Red". If it is even, he says "Black".
Now the 19th prisoner can count the red hats he sees. He can deduce what color his hat must be to make the total odd or even, as indicated by the previous prisoner. Each prisoner in line must keep track of the current state, odd or even, which changes each time someone behind him indicates having a red hat. Don On Mar 3, 2:18 am, freecoder <rajuljain...@gmail.com> wrote: > You are one of 20 prisoners on death row with the execution date set > for tomorrow. > > Your king is a ruthless man who likes to toy with his people's > miseries. He comes to your cell today and tells you: > > “I’m gonna give you prisoners a chance to go free tomorrow. You will > all stand in a row (queue) before the executioner and we will put a > hat on your head, either a red or a black one. Of course you will not > be able to see the color of your own hat; you will only be able to see > the prisoners in front of you with their hats on; you will not be > allowed to look back or communicate together in any way (talking, > touching.....) > > (The prisoner in the back will be able to see the 19 prisoners in > front of him > The one in front of him will be able to see 18…) > > Starting with the last person in the row, the one who can see > everybody in front of him, he will be asked a simple question: WHAT IS > THE COLOR OF YOUR HAT? > > He will be only allowed to answer “BLACK” or “RED”. If he says > anything else you will ALL be executed immediately. > > If he guesses the right color of the hat on his head he is set free, > otherwise he is put to death. And we move on to the one in front of > him and ask him the same question and so on… > > Well, good luck tomorrow, HA HA HA HA HA HA!” > > Now since you all can communicate freely during the night, can you > find a way to guarantee the freedom of some prisoners tomorrow? How > many? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
