On Monday, we considered some basic puzzles involving finite number of hats. We continue these investigations here with a slightly more involved puzzle. This puzzle is due to Todd Ebert and appeared in his 1998 PhD thesis. It attracted much attention, largely due to its connections with coding theory, and even inspired a New York Times article.


Puzzle 3: Hats and Coding

The Puzzle

There’s a finite group of prisoners. The prisoners are led into a room, where each is randomly (and independently) adorned with either a red or a blue hat (each has a 50% probability). Each prisoner can see the hat colors of all of the other prisoners, but no prisoner can see the color of their own hat. Each prisoner has a device with three buttons: ‘Red,’ ‘Blue,’ and ‘Pass.’ At a fixed time, the prisoners simultaneously press a button, with each prisoner either trying to guess the color of their hat or passing. If at least one prisoner guesses a color and everyone who guesses a color guesses correctly, then the prisoners are released. If everyone passes or at least one person guesses incorrectly, then the prisoners are executed. The prisoners are not allowed to communicate once they are given their hats; their guesses or passes must be based solely on the colors of the hats they can see. However, the prisoners can confer beforehand and devise a strategy. How can the prisoners maximize their probability of being released?

Solution for 3 prisoners

A naive strategy would be to choose one prisoner to be the ‘guesser.’ That prisoner will always guess ‘red,’ and everybody else will pass. This strategy will have a success rate of \frac{1}{2}. It turns out, though, that we can do better. This might initially be surprising to you. Since anybody guessing the color of their own hat has no useful information about the color of their hat, the success rate of any individual guess will be \frac{1}{2}. However, if we cleverly choose the circumstances in which a prisoner will guess and the color they will guess, we can concentrate the wrong guesses in a small number of ‘bad’ configurations of hats while spreading out the right guesses to a larger number of ‘good’ configurations.

To see how this might work, let’s suppose there are three prisoners, and let’s suppose we use the following strategy, which we call Strategy A: if a prisoner sees that the other two prisoners have the same color hat, they will guess the other color. If a prisoner sees that the other two prisoners have different colors, then they will pass.

How will Strategy A fare? If all three of the prisoners have the same color hat, then all three prisoners will guess the other color, and all three will be wrong. However, if two prisoners are wearing one color and one prisoner is wearing the other, then only the prisoner wearing the color appearing just once will guess, and they will be right! This strategy fails, therefore, only if all of the prisoners have the same color. What are the chances of this happening? For each color, the chances of all hats being that color are \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}, so the chances of it happening for either color is \frac{1}{8} + \frac{1}{8} = \frac{1}{4}. Strategy A therefore has a success rate of \frac{3}{4}.

This is certainly better than the \frac{1}{2} success rate of the naive strategy. Is it the best we can do? To make further analysis less cumbersome, let’s replace ‘red’ and ‘blue’ with ‘0’ and ‘1,’ i.e., suppose that prisoners with red hats are labeled ‘0’ and prisoners with blue hats are labeled ‘1,’ and that the prisoners guess ‘0’ or ‘1’ rather than ‘red’ or ‘blue.’ Let’s also suppose that, as part of their strategizing, the prisoners number themselves, from 1 to 3 (or 1 to n if there are n prisoners). A configuration of hats can therefore be represented as a sequence of length 3 (or, generally, n) of 0s and 1s. Note that, for 3 prisoners, there are 8 possible configurations of hats (in general, the number is 2^n):

000    001    010    011    100    101    110    111

When Strategy A is deployed, 12 total guesses are made throughout all configurations: 6 incorrect guesses are made in the configurations 000 and 111, and 6 correct guesses are made in the other configurations. As mentioned, because the prisoners have no real information about their own hat colors, this equality of correct and incorrect guesses is necessary. Suppose, then, that we had a strategy better than Strategy A. Since Strategy A succeeds in 6 of the 8 configurations, this new strategy would have to succeed in at least 7. It would therefore have to have at least 7 correct guesses across all of the configurations, which means it would also have to have at least 7 incorrect guesses. However, these 7 incorrect guesses would have to be restricted to the single configuration on which the strategy fails. Each configuration only has room for 3 guesses, so this is impossible. Therefore, Strategy A is optimal.

Generalizing the solution

With an eye to generalizing Strategy A to work with more prisoners, let’s look at it a little more deeply. Given two configurations of hats, let us say that the two configurations are close if they are same configuration or if one can be turned into the other by changing just one hat. So, using our ‘0’ and ‘1’ notation, 110 and 100 are close, whereas 101 and 010 are not close. Strategy A identifies two special configurations (000 and 111), which we will call bad configurations, which satisfy the following conditions:

  1. Every configuration is close to one of the bad configurations.
  2. No configuration is close to two different bad configurations.

Once these bad configurations have been identified, Strategy A can be formulated as follows. Each prisoner looks at the other hats and figures out whether what they see is consistent with one of the bad configurations. If it is, then they guess that their hat is the color that is different from the color of their hat in this bad configuration. So, for example, if Prisoner 1 sees two blue hats, they know that this is consistent with one of the bad configurations, namely 111, so Prisoner 1 guesses 0, or ‘red.’ If the prisoner sees something that is inconsistent with all of the bad configurations, they pass. So, if Prisoner 1 sees that 2 is wearing blue and 3 is wearing red, then they know the configuration could not possibly be any of the bad configurations, so they pass.

Suppose now that the number of prisoners is an arbitrary natural number, n. There are now 2^n possible configurations of hats, each represented by a string of 0s and 1s of length n. Let {^n}2 denote the set of all strings of 0s and 1s of length n. In analogy with our analysis of Strategy A, let us make the following definition.

Definition: Suppose H \subseteq {^n}2 (so H is a set of strings of length n of 0s and 1s). We say H is an n-Hamming set if it satisfies the following two conditions:

  1. Every element of {^n}2 is close to a member of H.
  2. There is no element of {^n}2 that is close to more than one member of H.

Suppose for a moment that H is an n-Hamming set. What can we say about |H|? For each x \in H, let A_x be the set of y \in {^n}2 such that y is close to x. For each x, there are n+1 elements that are close to it (x is close to itself, and there are n ways to change one position of x). Therefore, each set A_x has size n+1. Moreover, condition 1 in the definition of Hamming set implies that the union of all of the A_xs is all of {^n}2, which has size 2^n, and condition 2 in the definition of Hamming set implies that, if x_1 and x_2 are different members of H, then A_{x_1} \cap A_{x_2} = \emptyset. Putting this all together, we obtain:

|H| \cdot (n+1) = 2^n, or

|H| = \frac{2^n}{n+1}

Since |H| is an integer, it must be the case that n+1 evenly divides 2^n, so, in order for there to be an n-Hamming set, n+1 must be a power of 2. Thus, we may assume there is a natural number k such that n=2^k-1, in which case |H| = 2^{n-k} = 2^{2^k-(k+1)}.

It turns out that, if n+1 is a power of 2, then there is always an n-Hamming set. We will not prove this fact; it can be done with a modest amount of linear algebra.

Theorem: Suppose k \in \mathbb{N}. Then there is a 2^k-1-Hamming set.

This allows us to demonstrate an optimal strategy for the puzzle in cases in which the number of prisoners is one less than a power of 2. To see this, suppose k is a natural number and n = 2^k - 1. Let H be an n-Hamming set. Now suppose that the prisoners have been given their hats and, based on what a prisoner sees, the configuration could be one of the elements of H. Then the prisoner will guess the color they are not wearing in that element of H. In all other cases, the prisoner will pass. For example, if n=7, 0110011 is in H, and Prisoner 1 sees ?110011, then they will guess ‘1.’ If the actual configuration is 1110011, all other prisoners will pass, and the strategy will succeed. If the actual configuration is 0110011, then all of the prisoners will guess (and all will be incorrect). Condition 1 of the definition of Hamming set implies that at least one prisoner will guess in each configuration. Condition 2 implies that the strategy is well-defined. Therefore, the strategy will only fail if the configuration appears in H. Since \frac{|H|}{|{^n}2|} = \frac{2^{n-k}}{2^n} = \frac{1}{2^k}, the success rate of the strategy is \frac{2^{k}-1}{2^k} = \frac{n}{n+1}. The more prisoners there are, the more likely they are to succeed. Also, an easy calculation similar to that done for n=3 shows that this is the best we can do.

If the number of prisoners is not one less than a power of two, things don’t work out quite so nicely. Note that, if m < n, then a strategy for m prisoners can be employed by n prisoners as follows: m prisoners are chosen to pretend like they are the only prisoners and enact the strategy for m prisoners. The remaining n-m prisoners are sent off to twiddle their thumbs (and, of course ‘pass’ when the time comes to guess). This strategy will have the same success rate as the corresponding strategy for m prisoners. Thus, if there are n prisoners and k is the largest natural number such that 2^k-1 \leq n, then there is a strategy for n players with a success rate of \frac{2^k-1}{2^k}. For some values of n (such as n=4, where k=2), this is still optimal. For others, it might not be. The question of the optimal strategy for n prisoners when n is not necessarily one less than a power of 2 turns out to be a very difficult question, and we won’t say more about it here.

Coding theory

We end by remarking that Hamming sets can be used to develop error-correcting codes. Suppose you are sending some information, but the channel you are using to send it is a little noisy, and a small but non-negligible amount of error is introduced. You would like to be able to both identify and correct these errors. Here’s one way to do that. Suppose that your message can be sent using an alphabet of 16 symbols. Let H be a 7-Hamming set. By the calculations above, |H| = 16, so we can assign each letter of our alphabet to a member of H. We can then send the message, using the members of H to stand for the corresponding letters. Now, when the message is received, if a 7-bit string is in H, then it can be decoded as the corresponding letter. If it is not in H, then there is a unique element of H that is close to the received string, so the string can be changed to that element of H and then decoded. As long as there is no 7-bit string in which two errors occur (and, if the error rate is sufficiently small, this is a reasonable assumption), then the message is transmitted perfectly.

Advertisements

One thought on “Hats and Hamming Codes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s