## Red and blue hats

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?

[SOLVED]

#### Reiner Rückwald solved this puzzle:

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

In this manner, after the last prisoner declares the colour he has memorized, the next prisoner adjacent to him, who sees 98 others, declares his memorized colour. Then the next prisoner, who sees 97 others, declares his memorized colour. This continues until the first prisoner, who did not see any hats at all, declares his memorized colour.

In this manner, with the exception of the last one in the line, who declared his memorized colour first, all other 99 prisoners correctly declared the colour of their hats.

#### Rino Raj solved this puzzle:

Consider red to represent odd parity and blue to represent even parity. Each person counts the number of red hats visible in front of him and determines its parity. Now the last person shouts the colour corresponding to the parity he sees. He has a 50% chance of being right, but more importantly he has given critical information to everyone else. If the next person observes that the parity he has computed is different from the parity announced by the last person, he says red, else blue. In this turn, he is always correct. Similarly, the third person from the end knows the parity of the number of red hats including him and excluding the hat of the last person. Further he knows the parity of the number red hats in front of him. Hence he can always deduce the correct colour. Announcing this gives enough information for the next person and so on. As at least 99 people get it right, the warden sets everyone free.

A simple rule follows from the logic above. Each prisoner keeps track of a binary switch with states, red or blue. He starts with blue. For each red hat he sees, he flips the switch once. Then every time he hears someone shout "red" from behind, he flips the switch again. Finally when it is his turn sequentially from behind, he announces the state of his switch as his hat colour.

#### Ed Murphy solved this puzzle:

Number the prisoners #1 (who can see all the others) to #100 (who can't see anyone).

Prisoner #1 counts how many red hats he can see, and says "red" if it's even or "blue" if it's odd. This may match his hat, but they can't count on it, and don't need to.

Prisoner #2 counts how many red hats he can see. With that information plus what prisoner #1 said, he can work out his hat color and say it:

• If it's even and #1 said "red", then his hat must be blue.
• If it's even and #1 said "blue", then his hat must be red.
• If it's odd and #1 said "red", then his hat must be red.
• If it's odd and #1 said "blue", then his hat must be blue.

Prisoner #3 counts how many red hats he can see. With that information, and what prisoners #1 and #2 said, he can work out his hat color and declare it. And so on.

### Credit

This puzzle is taken from: