:: Recommended ::

:: Collaborations ::

:: Hat Problem ::

100 prisoners are given the chance to be set free tomorrow. They are all told that they will each be given a hat to wear and that they cannot see the colour of the hat assigned to them. They know that there are 3 possible colours of hat: red, blue, and white. Each prisoner can see everyone else's colour hat except their own. The hats colours are assigned completely at random and once the hats are placed on top of each prisoner's head they cannot communicate with others in any form, or else they are immediately executed. The prisoners will be called out in random order and they are to guess the colour of the hat that he/she is wearing. They shout the colour of the hat so that everyone else can hear. If the prisoner guesses correctly the colour of his/her hat they are set free immediately, otherwise executed.

They are given the night to come up with a strategy amongst themselves to save as many prisoners as possible. What is the best strategy they can adopt and how many prisoners can they guarantee to save? (Hint: Start with the case where there are only 2 possible colour hats).

Answer: There is a strategy that will guarantee to save at least 99 prisoners which is independent of the number of hat colours.

To solve this problem it is best to start with the 2 colour hat case, say red and blue only. A score is associated to each hat colour, so assume 0 for red and +1 for blue. Each prisoner can see everyone else’s hat colour except their own and is able to work out the accumulated score of all others. We call this score X.. Another prisoner does the same and sees a score of Y. Depending on whether this number is odd or even, a parity {0,1} is associated such that it 0 is even, and +1 odd. When the first prisoner is called out they will shout out the parity of X, i.e. red or blue. He/She will have a 50% chance of having guessed correctly. The next prisoner that sees Y is able to deduce that the difference between the two parities (X and Y) is his/her hat colour.

The same principle is easily extended to 3 (or more) hats using the parity {0,1,2}.

Back for more