Infinite Hats II

Today, we end our exploration of hat puzzles with a look at a couple of variations on the infinite hat puzzle from our last post. In particular, we will deal with situations in which the prisoners cannot hear each other’s guesses and therefore cannot pass along any information, and yet in which the prisoners still have surprisingly effective strategies at their disposal.


Puzzle Five: Countably infinite hats with no information

The setup is the same as that of Puzzle Four. There are countably infinitely many prisoners, labelled by the natural numbers. They are each given a red or blue hat and are lined up so that each prisoner knows their own number and can see exactly the prisoners with larger numbers. Each prisoner guesses the color of their own hat. If they are correct, then they are released; if they are incorrect, then they are executed. The difference is that, in this puzzle, although the prisoners can still devise a strategy beforehand, none of the prisoners knows the guesses of any of the others. How can the prisoners act to minimize the number of prisoners who guess incorrectly?


With no information being passed, it might seem hard to envision any strategy being reasonably effective. We will see, though, that for a reasonable definition of ‘reasonably effective,’ there is a reasonably effective strategy, and it can be found using only tools that we developed in our solution to Puzzle Four. As usual, configurations of hats will be represented as infinite sequences of 0s and 1s, with 0 meaning ‘red’ and 1 meaning ‘blue.’ In our last post, we isolated an equivalence relation, called E_0, on the set of all infinite sequences of 0s and 1s (this set is denoted by {^\omega}2), where, for two sequences x,y \in {^\omega}2, we say x \sim y if x and y differ in only finitely many positions. Also as in our solution of Puzzle Four, we can assume that, during their strategizing, the prisoners fixed a transversal of E_0, i.e. a function h from the set of equivalence classes of E_0 to {^\omega}2 such that, for every equivalence class X, we have h(X) \in X.

The point, of course, is that, when the prisoners are lined up with hats on their heads, each prisoner can see all but finitely many of the hats, so each prisoner knows precisely in which equivalence class their particular configuration lies. Denote this equivalence class by Y. Since each prisoner knows h, which was fixed in advance, each prisoner also knows h(Y) and knows that their configuration only differs from h(Y) in finitely many places. Suppose now that each prisoner guesses the color indicated for their position by h(Y). Whenever their particular configuration differs from h(Y), they will be wrong. However, we know that their configuration only differs from h(Y) finitely many times, so only finitely many prisoners are wrong. This finite number could be arbitrarily large, but it is guaranteed that, from some point on, the prisoners’ configuration will agree with h(Y), and all of the prisoners from that point on will guess correctly. This isn’t bad for a situation that may at first glance have appeared somewhat hopeless!


Puzzle Six: A continuum of hats

We have more prisoners now, one for each real number. They are again each given a red or blue hat and arranged in a line so that each prisoner can see exactly those prisoners with strictly larger numbers than their own. Each prisoner guesses the color of their hat; if they are correct, they are released, and if not, they are executed. And, again as in Puzzle Five, each prisoner knows their own number, and the prisoners are allowed to devise a strategy beforehand, but no prisoner knows the guesses of any of the other prisoners.


Note: The solution to this puzzle requires somewhat more sophistication than previous solutions, so be prepared to work a little bit here. It’s worth it, though!


In this situation, configurations of hats will be represented by functions f:\mathbb{R} \rightarrow \{0,1\}, where, for a real number r, f(r) gives the color of the hat worn by Prisoner r. Let \mathcal{F} denote the set of all such functions. We can try to recreate the strategy used in Puzzle Five in the following way: define an equivalence relation on \mathcal{F} by letting f \sim g if and only if f and g differ in only finitely many places. Oh, but now we run into a problem: no prisoner is able to tell in which equivalence class their configuration lies, since each prisoner is ignorant of the colors of the hats of all of the prisoners with smaller numbers and, for each real number r, the set of real numbers smaller than r has the same size as the set of all real numbers!

OK. Let’s try to generalize the strategy from Puzzle Five in a different way, using a different equivalence relation. Let’s say that f \sim g if, for all large enough r, f(r) = g(r). More precisely, f \sim g if there is some real number r^* such that, for all r\geq r^*, f(r) = g(r). The reader is invited to check that this does in fact define an equivalence relation. Also, it is evident that each prisoner is able to tell in which equivalence class of this relation the actual configuration lies. Therefore, we can mimic the strategy from Puzzle Four: the prisoners fix beforehand a transversal (call it h) of the equivalence relation, i.e. a function that chooses a representative element from each equivalence class. Then, given a real number r, Prisoner r guesses (h(X))(r), where X is the equivalence class of the actual configuration. By the definition of the equivalence relation, then, there is some real number r^* such that, for every prisoner with a number at least as large as r^*, that prisoner guesses correctly.

This is something, at least. We guarantee that continuum many prisoners are released, and we will certainly have an impressive run of success past the magic real number r^*. However, we don’t really know anything about what happens for the prisoners with numbers less than r^*. For all we know, it could be the case that all of them guessed incorrectly! We will have saved continuum many prisoners, but perhaps we have sent continuum many prisoners to their deaths as well! That doesn’t seem too good. Can we do better?

Yes, we can. In fact, I claim that the prisoners have a strategy which guarantees the following:

  1. Only countably many prisoners guess incorrectly.
  2. There is a real number r^* such that, for every real number r \geq r^*, Prisoner r guesses correctly.

How can we accomplish this seemingly miraculous feat? Think about it for a few minutes before continuing.

mad_hatter

The strategy works as follows. First, let \lambda denote the cardinality of \mathcal{F} (namely, \lambda = 2^{2^{\aleph_0}}). One of the many equivalent formulations of the axiom of choice is that any set can be well-ordered in order type equal to its cardinality. In other words, we can enumerate the elements of \mathcal{F} by the ordinals \alpha < \lambda such that each element is enumerated exactly once. Fix such an enumeration, \{f_\alpha \mid \alpha < \lambda\}, during the prisoners’ strategizing session.

Now suppose that the prisoners are given hats and lined up, and suppose that their actual configuration is given by a function g:\mathbb{R} \rightarrow \{0,1\}. Given a real number r and an ordinal \alpha < \lambda, let us say that (r, \alpha) is possible for g if, for all real numbers s > r, f_\alpha(s) = g(s). In other words, (r, \alpha) is possible for g if, as far as Prisoner r knows, the actual configuration might be f_\alpha. Now, for each real number r and ordinal \alpha < \lambda, Prisoner r is able to tell if (r, \alpha) is possible for g, since this depends only on values of g that Prisoner r can see. Prisoner r can thus identify the least ordinal \alpha < \lambda such that (r, \alpha) is possible for g. Denote this ordinal by \alpha_r. Prisoner r then guesses the hat color given by f_{\alpha_r}(r).

I claim that this strategy does what we want, though this fact should by no means be obvious at this point. To prove that it works, we have to analyze what happens when a prisoner guesses incorrectly. To this end, suppose that r is a real number and Prisoner r guesses incorrectly. In particular, this means that f_{\alpha_r}(r) \neq h(r). Now suppose that s < r. Prisoner s can see Prisoner r, so it must be the case that f_{\alpha_s}(r) = h(r). In particular, \alpha_s \neq \alpha_r, since f_{\alpha_s}(r) \neq f_{\alpha_r}(r). Also note that, since (s, \alpha_s) is possible for g and s < r, we easily have that (r, \alpha_s) is possible for g. But Prisoner r chose \alpha_r instead of \alpha_s, so we must have \alpha_r < \alpha_s. Putting this together, we have shown the following:

  • For all real numbers s < r, \alpha_s \geq \alpha_r and, if Prisoner r guesses incorrectly, then \alpha_s > \alpha_r.

Now let S be the set of all real numbers r such that Prisoner r guesses incorrectly, and let A = \{\alpha_r \mid r \in S\}. By what we have proven, if s < r are both in S, then \alpha_s > \alpha_r. In particular, |A| = |S|.

Claim: S is countable.

Proof: Suppose not. Then, as |A| = |S|, A is uncountable. Since A is a subset of an ordinal, A is well-ordered by the usual ordering on the ordinals. Let \gamma be its order type, and let \{\beta_\eta \mid \eta < \gamma \} enumerate A in increasing order. For \eta < \gamma, let r_\eta be the unique element of S such that \alpha_{r_\eta} = \beta_\eta. Note that, for \eta < \zeta < \gamma, we must have r_\zeta < r_\eta. Since A is uncountable, \gamma \geq \omega_1. Recall that the rational numbers, \mathbb{Q}, are dense in \mathbb{R}, i.e. for every pair of real numbers s < r, there is a rational number q \in \mathbb{Q} such that s < q < r. Now for each \eta < \omega_1, fix a rational number q_\eta such that r_{\eta+1} < q_\eta < r_\eta. Since the sequence \langle r_\eta \mid \eta < \omega_1 \rangle is strictly decreasing, it must be the case that, for \eta < \zeta < \omega_1, q_\eta \neq q_\zeta. But then \{q_\eta \mid \eta < \omega_1\} is an uncountable set of rational numbers, contradicting the fact that there are only countably many rational numbers. Thus, S is countable, and the claim is proven.

Therefore, when employing our strategy, only countably many prisoners guess incorrectly. It remains to show that there is a real number r^* such that, for all real numbers r \geq r^*, Prisoner r guesses correctly. If this is not true, then we can construct an increasing sequence  \langle r_n \mid n \in \mathbb{N} \rangle of real numbers such that, for all n \in \mathbb{N}, Prisoner r_n guesses incorrectly. But now, if m < n are natural numbers, then \alpha_{r_m} > \alpha_{r_n}, so \langle \alpha_{r_n} \mid n \in \mathbb{N} \rangle is an infinite, strictly decreasing sequence of ordinals, contradicting the fact that the ordinals are well-ordered. Thus, we have shown that are strategy works exactly as desired.

Remark: If this strategy is not sufficiently surprising to you, let me quickly remark that we can make the challenge to the prisoners seemingly much more difficult in two different ways, and yet the same strategy will have the same astoundingly good result.

  1. First, we assumed above that there were only two possible hat colors for the prisoners. We never actually used this fact, though. The strategy would work just as well if there were ten possible colors of hats, or one for each natural number, or one for each real number. The strategy would work even if the number of possible colors were equal to an inaccessible cardinal, a measurable cardinal, a supercompact cardinal! The only necessity is that the prisoners know beforehand the set of possible colors, in which case they can devise a strategy exactly as above.
  2. In this puzzle, in order to be released, each prisoner only has to guess the color of their own hat. Perhaps this is too easy, so let’s make it harder as follows. In this new, strengthened challenge, each prisoner guesses the color not only of their own hat but also the color of the hat of ever prisoner with a smaller number. For each real number r, in order for Prisoner r to be released, there must be some real number s < r such that Prisoner r guesses every hat color correctly on the interval [s,r] (recall this is the set of real numbers t such that s \leq t \leq r). Success in this new challenge probably now seems almost comically difficult, but, as I’ll leave it to the reader to check, the strategy we gave above easily generalizes to a strategy for this challenge with exactly the same result!

For more on this and related matters, the interested reader is directed towards the entertaining paper, “A Peculiar Connection Between the Axiom of Choice and Predicting the Future,” by Christopher S. Hardin and Alan D. Taylor.

 

Advertisements

Infinite Hats I

Now—Ten thousand, and ten thousand times ten thousand (for matter and motion are infinite) are the ways by which a hat may be dropped upon the ground, without any effect.—Had he flung it, or thrown it, or cast it, or skimmed it, or squirted, or let it slip or fall in any possible direction under heaven,—or in the best direction that could be given to it,—had he dropped it like a goose—like a puppy—like an ass—or in doing it, or even after he had done, had he looked like a fool,—like a ninny—like a nicompoop—it had fail’d, and the effect upon the heart had been lost.

-Laurence Sterne, The Life and Opinions of Tristram Shandy, Gentleman

We continue last week’s investigation of hat puzzles, moving today from the land of the finite to the land of the infinite, where amazing things can happen. We start by considering the infinite analogue of Puzzle Two from last Monday.


Puzzle Four: E0 and the infinite line

There is a countable infinity of prisoners, labeled by the natural numbers (Prisoner 0, Prisoner 1, Prisoner 2, etc.). They are each given a red or blue hat and are lined up (buried up to their necks, of course, as is standard practice) so that each prisoner can see exactly those prisoners with higher numbers. The warden then goes up the line, starting at Prisoner 0, and asks the prisoners to guess the colors of their hats. If a prisoner guesses correctly, they are released; if they guess incorrectly, they are executed. Assuming that the prisoners were able to decide upon a strategy beforehand, and assuming that each prisoner can hear the guesses of all of the prisoners with lower numbers, how can the prisoners act to minimize the number of prisoners who will be executed?


This is, of course, exactly Puzzle Two with a countably infinite number of prisoners, arranged like the natural numbers. In Puzzle Two, we were able to save all prisoners except possibly the first, who was guessing with no information. We would like to be able to generalize this strategy and, one would hope, be able to save all but one prisoner in this case, as well. The strategy in Puzzle Two relied on the prisoners counting whether there is an even or odd number of red hats in front of them and using their guesses to pass this information up to the other prisoners. However, it is likely that, in the infinite version, every prisoner will see infinitely many red hats and infinitely many blue hats. The odd/even distinction no longer makes sense in the usual way. But we shouldn’t give up yet; we’ll just have to work a bit harder.

As before, we will represent configurations of hats by strings of 0s and 1s, with 0 meaning ‘red’ and 1 meaning ‘blue.’ This time, the strings will be infinite, with bit 0 representing the hat color of Prisoner 0, bit 1 the hat color of Prisoner 1, and so on. The set of all infinite strings of 0s and 1s will be denoted by {^\omega}2. If x \in {^\omega}2 and n is a natural number, then x(n) is the n^{\mathrm{th}} bit of x.

If x,y \in {^\omega}2, let us say that x is equivalent to y, and write x \sim y, if there are only finitely many n such that x(n) \neq y(n). In other words, x and y are equivalent if, from some point on, they are the same. The reader can easily verify that this relation satisfies the following three properties:

  • (Reflexivity) For all x \in {^\omega}2, x \sim x.
  • (Symmetry) For all x, y \in {^\omega}2, if x \sim y, then y \sim x.
  • (Transitivity) For all x,y,z \in {^\omega}2, if x \sim y and y \sim z, then x \sim z.

Thus, the relation \sim is what’s called an equivalence relation. In fact, it is such an important relation that it has its own name, the Vitali equivalence relation, and its own symbol, E_0. E_0 is extensively studied in the field of mathematics known as descriptive set theory and is, in a certain sense, “the simplest complicated equivalence relation.” This vague statement is made precise in the famous Glimm-Effros Dichotomy, which states that, for every “nicely definable” (Borel, for those in the know) equivalence relation E on a Polish space (the real numbers, or {^\omega}2, are standard examples of Polish spaces), either E is smooth (i.e. admits a Borel transversal), or there is a continuous embedding of E_0 into E.

If x \in {^\omega}2, let [x] denote the E_0-equivalence class of x, i.e. the set \{y \in {^\omega}2 \mid x \sim y\}, and let {^\omega}2/E_0 denote the set of E_0-equivalence classes. The fact that E_0 is an equivalence relation means that each member of {^\omega}2 belongs to precisely one equivalence class. A function f:{^\omega}2/E_0 \rightarrow {^\omega}2 is called a transversal for E_0 if, for every E_0-equivalence class X, we have f(X) \in X. In other words, a transversal is a way of selecting one element from each E_0-equivalence class.

Side Remark: E_0 is not smooth, which means that a transversal for E_0 cannot be “nicely definable” (again, Borel). Coming up with a transversal for E_0 thus involves a non-trivial application of the axiom of choice and is precisely the place where the axiom of choice is used in Vitali’s famous construction of a set of real numbers that is not Lebesgue measurable.

What does all of this have to do with our puzzle? Well, notice that, though no prisoner can see the entire configuration of hats (even Prisoner 0 is missing one), each prisoner sees all except finitely many of the hats, and therefore each prisoner knows exactly which E_0-equivalence class the configuration of hats is in. In other words, if x^* is the actual configuration of hats, then no prisoner knows x^*, but every prisoner knows [x^*]. Suppose that, when the prisoners were devising a strategy, they fixed a transversal f:{^\omega}2/E_0 \rightarrow {^\omega}2. Thus, every prisoner knows f([x^*]). Let y^* denote f([x^*]).

Since f is a transversal, we know that x^* \sim y^*. Therefore, each prisoner sees only a finite number of places at which x^* and y^* disagree (for prisoners with large enough numbers, this finite number will in fact be 0). And now that we have finite numbers, we have meaningful concepts of ‘even’ and ‘odd’! The strategy of Puzzle Two can now be implemented as follows.

Prisoner 0 starts by comparing what they see of x^* with the corresponding part of y^* and counting the number of bits at which they disagree. If this number is even, they say ‘Red,’ and if this number is odd, they say ‘Blue.’ Of course, this guess has only a 50 percent chance of being correct, but we claim that, as in Puzzle Two, every prisoner after Prisoner 0 can now guess correctly! Let’s start with Prisoner 1. They can also count the number of bits at which what they see of x^* disagrees with the corresponding part of y^*. They also know, based on Prisoner 0’s guess, whether Prisoner 0 saw an even or odd number of disagreements. If Prisoner 1 agrees with Prisoner 0 about the parity of the number of disagreements, they know that their own color matches the corresponding bit of y^* (as otherwise Prisoner 0 would see one more disagreement than Prisoner 1, and the parity would be different), so they can guess the color indicated by y^*(1) and guarantee that they are correct. If Prisoner 1 disagrees with Prisoner 0 about the parity, they know that their own color disagrees with the corresponding bit of y^*, and they can guess the color different from that indicated by y^*(1).

The strategy then continues exactly as in Puzzle Two. Based on the guesses of Prisoners 0 and 1, Prisoner 2 knows whether Prisoner 1 sees an even or odd number of differences between x^* and y^*, compares this with what they see, and guesses accordingly. This continues all the way up the line, with every prisoner except Prisoner 0 guaranteed release.

At the risk of over-explaining, let’s see how the first few steps will work for a specific example. Suppose that:

x^* = 0110100\ldots

y^* = 1011001\ldots

and that x^* and y^* agree after what is written above. Every prisoner knows the part of x^* that lies after their position in the line, and every prisoner knows all of y^*. Prisoner 0 sees 4 differences between x^* and y^* (there are in fact 5 differences, but Prisoner 0 cannot see that their own hat color disagrees with y^*) and therefore says, ‘Red.’ Prisoner 1 sees 3 differences and knows that Prisoner 0 sees an even number of differences. Prisoner 1 therefore knows that their hat color differs from that corresponding to y^*(1) (which is ‘Red’), so they guess ‘Blue’ (correctly, of course). Now, since Prisoner 1 guessed the color different from that suggested by y^*, Prisoner 2 knows that Prisoner 1 disagrees with Prisoner 0 about the parity of the disagreements between x^* and y^*. Since they know Prisoner 0 sees an even number of differences, they know that Prisoner 1 sees an odd number of differences. Prisoner 2 also sees an odd number (3) of differences, so they know that their hat color matches that suggested by y^* and guess ‘Blue.’ This continues, with an infinite string of prisoners correctly guessing, as if by magic, the color of the hat they are wearing.

Remark: There is a slightly different strategy for solving this puzzle that involves the prisoners fixing in advance a non-principal ultrafilter on the natural numbers and using this ultrafilter to extend in a meaningful way the parity function on finite strings of 0s and 1s (i.e. the function that indicates whether there is an even or odd number of 0s) to a parity function on infinite strings of 0s and 1s. This function can then be used to implement exactly the strategy from Puzzle Two in the infinite case. I encourage the interested reader to work through the details. The mathematically mature reader may consult the linked paper of Geschke, Lubarsky, and Rahn for this and more on role of the axiom of choice in hat puzzles.

Hats and Hamming Codes

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.

Finite Hats

Why should anyone be frightened by a hat?

-Antoine de Saint-Exupéry

As a traveling mathematician, one steadily amasses, mostly over drinks with other mathematicians, a compendium of puzzles, conundrums that come to us from some strange world of transfinite subways and unnecessarily complicated lighting solutions.

One of the most common types of puzzle one encounters in this way is the “hat puzzle,” which typically involves a situation of the following form: some number of people are wearing hats. According to the prevailing fashions in this world, each hat is either red or blue. Some of these people can see the hats of some of the other people, but nobody can see their own hat. The most common way to make this plausible is to suppose that these people are prisoners at the whims of some sadistic prison warden who has buried them up to their necks so that they do not have use of their arms to reach up, remove their hats, and examine their color. The people want to guess the colors of their own hats in order to gain their freedom (the rules and winning conditions of the contest vary according to the puzzle under consideration). Your challenge is typically to come up with the optimal strategy for the prisoners to employ so that they have the highest chance of escaping or so that as many of them as possible are guaranteed to escape.

Hat puzzles come in two basic flavors that look similar in setup but feel very different in execution: puzzles with finitely many hat-wearers and puzzles with infinitely many hat-wearers. Solutions to finite hat puzzles typically involve finding clever ways to encode or transmit information. Solutions to infinite hat puzzles typically involve finding clever applications of the axiom of choice.  And though Point at Infinity is dedicated to all things infinite, I don’t want to deprive my readers of the joys of finite hat puzzles, so, over the next two weeks, we will look at both. This week will cover the finite case, with two basic puzzles today and a more involved one, with connections to information theory, on Thursday.


Puzzle One: The Four Hats

There are four prisoners, named A,B,C, and D. Each is wearing either a blue or a red hat, and each knows that there are two hats of each color between them. The prisoners are all buried up to their necks. A,B, and C are in a line on one side of a brick wall, so that A can see B and C, B can only see C, and C can see neither of the others. D is on the other side of the brick wall; they can see nobody else, and nobody can see them. The prisoners are not allowed to speak except to guess the color of their own hat. If the first prisoner to speak guesses their own hat color correctly, then all four go free. If the first prisoner to speak guesses their own hat color incorrectly, then all four are executed. Can the prisoners guarantee their release?

(ANSWER AFTER THE PICTURE. TAKE A MOMENT TO THINK BEFORE READING FURTHER.)

rsz_four_hats
The four prisoners in their predicament. Two are wearing red hats, and two are wearing blue hats (all hats are purple in the picture). The first to speak must guess their own hat color correctly. Can they succeed?

Yes, the prisoners can guarantee success. Here’s how.

  • First note that, if B and C have the same color hat, then A will know this. A will then know that there are no more hats of that color, since everyone knows there are only two hats of each color. A can then confidently declare the other color.
  • If B and C have different hat colors, then A can no longer be sure of the color of their hat. A will therefore be silent. After a short period of silence, B will be able to conclude that their hat color is different from C’s, as otherwise A would have immediately spoken. B can therefore confidently state the color that C is not wearing.

This covers all of the possible configurations of hats, so we are done!


Puzzle Two: The Ten Hats

That was just a warm-up. Let’s get to something more interesting. In this puzzle, there are ten prisoners (as we will see, the exact number is not important; the solution will generalize to any number of prisoners), numbered 1 through 10. They are each wearing a hat, either red or blue, randomly assigned. Each prisoner knows that all of the hats are either red or blue, but none of them knows how many hats of each color there are. The prisoners are again buried up to their necks in a straight line, this time in a way so that each prisoner can see exactly those prisoners with higher numbers.

The warden proceeds along the line, from back to front (1 to 10), asking each prisoner to guess the color of their own hat. The guesses are audible to all of the prisoners, but no other communication is permitted. (The prisoners were permitted to confer and devise a strategy before they were buried and given hats, though). For each prisoner, if they guess their hat color correctly, then they are released. If they guess incorrectly, then they are executed. How should the prisoners act to maximize the number of prisoners who are guaranteed to be released?

rsz_ten_hats
One particular instance of the ten hats puzzle. Each prisoner can see the hats of the prisoners with higher numbers. The prisoners, in order from 1 to 10, guess the colors of their own hats. The guesses are audible to everyone. What is the prisoners’ optimal strategy?

Here’s a first natural attempt at a solution. Suppose that each odd-numbered prisoner guesses the color of the prisoner in front of them. Then each even-numbered prisoner will hear this guess and know the color of their own hat, so they can simply repeat the guess of the prisoner behind them. This will guarantee that each even-numbered prisoner is released. In addition, some of the odd-numbered prisoners will get lucky and ‘accidentally’ guess their own color. Half of the prisoners are guaranteed to be released, and, on average, three-quarters of the prisoners will be released. Can we do better?

Yes! First, note that Prisoner 1 is always guessing with no information and thus cannot have better than a 50 percent chance of being released. The best we can possibly do, then, is to guarantee that the other nine prisoners can be released. This might seem, at first, hopelessly optimistic, but it can be achieved!

The key idea is that, through their guesses, the prisoners can pass up information about how many red or blue hats they can see, while simultaneously (except for Prisoner 1) guessing their own hat colors correctly. To get things started, it is agreed among the prisoners that Prisoner 1 will guess ‘Red’ if they see an even number of red hats and ‘Blue’ if they see an odd number of red hats. Let’s first see how this helps Prisoner 2.

After Prisoner 1’s guess, Prisoner 2 knows whether Prisoner 1 saw an even or odd number of red hats. Prisoner 2 also knows whether they themselves see an even or odd number of red hats. If the prisoners agree about this information, then Prisoner 2 knows that they must be wearing a blue hat and will guess ‘Blue.’ If they disagree about this information, then Prisoner 2 knows that they must be wearing a red hat and will guess ‘Red.’

Here’s how this will play out in the particular instance of the puzzle in the picture above. Prisoner 1 sees 4 red hats (and 5 blue hats) and will therefore say ‘Red,’ signifying an even number of red hats. Prisoner 2 sees 3 red hats, an odd number. Prisoner 2 therefore knows that, to account for the discrepancy between what they see and what Prisoner 1 sees, they must be wearing a red hat and will say ‘Red.’

Here’s the neat part: when Prisoner 2 guesses their hat color (correctly), they are simultaneously telling the other prisoners whether they see an even or an odd number of red hats, since their guess depends on whether what they see agrees or disagrees with what Prisoner 1 sees. Prisoner 3 is now in the same position as Prisoner 2 was after Prisoner 1 had guessed, so Prisoner 3 can guess correctly. But now Prisoner 3 is telling the other prisoners whether they see an even or odd number of red hats, and Prisoner 4 can guess correctly. This continues all the way up the line, and Prisoners 2 through 10 all escape.

Let’s go back to the picture to see how this would work in this particular instance. We know that Prisoner 1 says ‘Red,’ and then Prisoner 2 correctly guesses ‘Red.’ What does Prisoner 3 know now? They know that Prisoner 1 saw an even number of Red hats, because Prisoner 1 said ‘Red.’ They then know that Prisoner 2 saw an odd number of Red hats, because they also said ‘Red.’ Prisoner 3 sees an odd number (3) of red hats, which agrees with what Prisoner 2 sees. Therefore, Prisoner 3 knows their hat is blue and says ‘Blue.’ Prisoner 4 then knows that Prisoner 3 sees an odd number of red hats. Prisoner 4 also sees an odd number of red hats, so Prisoner 4 guesses ‘Blue.’ Prisoner 5 sees an even number of red hats. Since this disagrees with what they know Prisoner 4 sees, they guess ‘Red,’ and so on.

As I mentioned, it is clear that this solution does not depend on there being exactly ten prisoners; it will work for any number of prisoners who happen to find themselves in the same position. The first prisoner will be in the unfortunate situation of having only a 50 percent chance of escaping, but the remaining prisoners can all be guaranteed escape!

chapeau
Source: unepetitereveuse

Infinite Picture Books

I’ve been traveling for the last month or so and thus have not been posting here. I have returned, though, so I will try to begin regularly updating again.

Today, just a short post to tell you to go have a look at some fantastic work by Richard Evan Schwartz of Brown University, who has two delightful (and occasionally terrifying) PDF picture books about infinity on his website:

Enjoy!