Mathematics could save your life December 6, 2010Posted by Ezra Resnick in Math, Puzzles.
Three prisoners are brought to jail, but the jail is full. So the warden suggests the following procedure: Each of the three prisoners will have a colored hat placed on his head, either white or black or red. (Each color may appear any number of times — they may all get red hats, or two could be white and one black, etc.) Each prisoner will be able to see the others’ hats, but not his own. Without communicating with each other in any way, they must each write down on a piece of paper what color they think their own hat is. If at least one of them guesses correctly, they will all go free; otherwise, they will all be executed. The warden gives the prisoners a few minutes to talk it over before the procedure begins. What should they do to ensure their survival?
I like this puzzle because at first it seems impossible: there is no way for a prisoner to deduce anything about the color of his own hat based on the hats of the others, so what strategy could possibly ensure that at least one of them will guess correctly? The key is to think like a mathematician, and look at the underlying structure of the scenario. Try to solve it on your own before reading on.
Let us assign a number to each of the colors: zero for white, one for black, two for red. Now, consider the sum of the three numbers corresponding to the colors of the prisoners’ hats. We don’t know what this sum is, but each of the prisoners knows two out of its three components. Next, think of the remainder we will get if we divide that sum by three: it must be either zero or one or two. For example, if there are two red hats and one white hat, then the sum is four, and the remainder when dividing by three is one. The idea is for each of the prisoners to be assigned one of the possible remainders, and each will guess the color which, when added to the other two colors he sees, yields a sum whose remainder matches the one he was assigned.
For instance, if prisoners zero and one are wearing red hats, then prisoner two will guess that his hat is black (bringing the sum to five and the remainder to two). He could be wrong, of course — but exactly one of the prisoners will always be right: the one who was assigned the remainder that matches the actual sum of the three colors. In the above case, if prisoner two’s hat is white then prisoner one will guess correctly, and if prisoner two’s hat is red then prisoner zero will guess correctly.
In case you were worried, this strategy can naturally be generalized for n prisoners and n hat colors.