Craftsman 12" Bandsaw – Fully Rebuilt + Turning Blanks
Articles Forums Gallery Marketplace Videos

WoodCentral Forums

Est. 1998 — 27 years of woodworking knowledge

Portable Sawmill & Tree Service – Abingdon, VA

Friday Puzzler -- Prisoners' hats

Posts

Friday Puzzler -- Prisoners' hats

#1

Friday Puzzler -- Prisoners' hats

Alex Y

I think I have seen one like this here before, but I couldn't remember it, so maybe you can't either

There are 100 prisoners in a prison. The warden will set them free if they win a game involving red and blue hats. All the prisoners will be made to stand in a straight line. The warden will blindfold all the prisoners, then put either a blue hat or a red hat on each prisoner's head, and finally remove all the blindfolds. Each prisoner can then see the hats of all the prisoners in front of him but he cannot see his own hat or the hats of those behind him. If at least 99 prisoners can correctly declare the colour of his hat, the warden will set them free.

Once the game begins, each prisoner is allowed to utter "red" or "blue" only once to declare the colour of his hat. They will not be allowed to communicate in any other manner. The warden will give them one day to decide a strategy to win this game. What should their strategy be?

Re: Friday Puzzler -- Prisoners' hats

#2

Re: Friday Puzzler -- Prisoners' hats

Larry Barrett

Here's a start.

Suppose there are just two prisoners, and they go free if at least one of them gets the right color. They decide that the second prisoner will call out the color of the one hat in front of him. Then the first prisoner will call out the same color.

Now suppose there are three prisoners, and they go free if at least two get the right colors. They decide that the third prisoner will call out red if the hats in front of him are either both red or both blue, and he will call out blue if the hats in front of him are either blue/red or red/blue. For instance, suppose both hats are red (or both blue); the second prisoner, seeing the one hat in front of him is red (or blue), will know the color of his is also red (or blue)and will call out red (or blue). The first prisoner, hearing the second prisoner call out the correct color of his hat, will call out the same color. Similar logic if the hats are different colors. So both prisoners one and two will get the correct color.

Just need to extend this to 100.

Re: Friday Puzzler -- Prisoners' hats

#3

  Correct, and nice approach

Alex Y

Here's one way of extending it to 100 (or any large number):

Each prisoner in the line counts the number of red has he sees in front of him. If the value is even, he memorizes "red". If the value is odd, he memorizes "blue". Then the last one in the line declares the color he has memorized. His chance to correctly declare the color of his hat, is 50%. Every time a prisoner declares "red", each of the remaining prisoners, who hasn't declared his color yet, changes his memorized color to the opposite one. If a prisoner declares "blue", all remaining prisoners retain their memorized color.

👍 This page answered my questions

Your vote helps other woodworkers quickly find the answers and techniques that actually work in the shop.