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

One thought on “Infinite Hats II

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