Pages

Bookmark and Share

Wednesday, November 5, 2014

Prisoners With Hats Again

This is a generalization of the latest logic problem in MIT's Technology Review, November/December 2014 There are $n$ prisoners, $a_1, a_2, \dots, a_n$ where each prisoner is a perfect logician. Also, $a_n$ is blind but the other ones can see.

Initially they're all blindfolded. There are $n$ white hats and $n-1$ black hats, and out of those $2n-1$ hats, $n$ hats are randomly selected, and the rest hidden. Each prisoner is then given one of those $n$ hats to wear. At the same time, all the blindfolds are taken off.

Then the prisoners said the following things, in this order:
$a_1$ said: "I don't know my hat color."
$a_2$ said: "I don't know my hat color."
$a_3$ said: "I don't know my hat color."
...
$a_{n-1}$ said: "I don't know my hat color."
$a_n$ said: "I know my hat color."

What is $a_n$'s hat color?

Solution

If $a_1$ saw all black hats, then he would know that his hat is white, because there are at most $n-1$ black hats in the room. Because he doesn't know his hat color, then at least one of $a_2,\dots,a_n$ is white.

Likewise, if $a_2$ saw all black hats among $a_3, \dots, a_n$, given the information that at least one of $a_2, \dots, a_n$ is white, he would know that his hat is white. Because $a_2$ doesn't know his hat color, then at least one of $a_3, \dots, a_n$ is white.

We can continue this line of reasoning via induction. The hypothesis is that at least one of $a_k, \dots, a_n$ is white. If $a_{n-1}$ saw that $a_n$ has black, he would know that he has white. Because $a_{n-1}$ doesn't know his hat color, that means $a_n$ has white.