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.

2 thoughts on “Infinite Hats I”

  1. Pingback: Infinite Hats II | Point at Infinity
  2. Pingback: Playing Games I: Setting Up the Pieces – Point at Infinity

Leave a comment