Simple City

This is a sequel to the first hat game post, please read for the background. Everything here is based on a recent talk by Robert Lubarsky, about work of his with Stefan Geschke, though any errors are mine. This post will end up with some unsolved questions: if you think you know the answers (either because you can solve them yourself, or you know where solutions can be found), please leave a comment here or drop Robert an email. (He told me he was quite happy to throw this material out into the public domain, and I would obviously be delighted if this blog helps find some answers!)

So… the basic puzzle in this post is as before, but this time the first person in line sees an infinite queue of hat wearers standing in front of him. What strategy can our team adopt, to maximize the number of hats they are able to name correctly? Have a think about it… and a discussion follows…

Hats and Tails

 
Last time we started representing our hat-wearers using binary sequences, that is strings of 0s and 1s. The new puzzle plunges us into a world of infinite binary sequences. Infinite things are generally not easy to write down, so let’s take a very simple example consisting only of ones:
A = 1111111111111111……..

We’ll say that two infinite binary sequences are equivalent if they share the same tail, meaning that are identical beyond some point, before which they may differ (or to put it another way, the two only differ in finitely many places). So the sequence A above is equivalent to B = 0010111111111111……..

This notion of equivalence divides the whole space of all possible binary sequences into ‘classes’, inside each of which all sequences are equivalent. Getting back to our hat-wearing friends, everyone in the line has infinitely many people in front of them, and only finitely many behind. So everyone can tell at a glance which class they are in. They all know whether or not they are equivalent to A, or to any other specified sequence.

This doesn’t immediately help them. But we can take it a little further. We say two sequences are evenly equivalent if they differ in an even number of positions. Obviously, if two sequences are evenly equivalent, then they are equivalent. But not vice versa: A and B are equivalent but not evenly so.

A little thought reveals that any sequence which is in the same class as A (and therefore B) must be evenly equivalent to either A or to B. (Think about it!) Now this really is a useful fact for the hatters to exploit. In their strategy-meeting before the game, they go through every class, and they select one special sequence from it, to act as a reference point. Let’s say, for the class containing A & B, they choose A.

When they come to line up, let’s suppose the sequence of hats which emerges is B = 0010111111111111…….. Now, everyone can see which class they are in. So everyone knows to follow the plan and compare their own sequence to A. But they do not know which subclass they’re in i.e. whether they are evenly equivalent to A. However, the first person (who is hatless in this version) can see the whole sequence. So she can discern the subclass, in particular she sees that the sequence is not evenly equivalent to A. So she calls out “1”. (It would have been “0”, had the sequence been evenly equivalent to A.)

Now, as far as the next person is aware, the sequence is X010111111111111…….. where X is his own hat colour. He doesn’t know the value of X, but he knows from what he hears over his shoulder that the overall sequence is not evenly equivalent to A. So, he deduces that X=0, which he calls out. The next person knows 0Y101111111111….., and that the whole sequence is not evenly equivalent to A, so concludes that Y=0, and so on.

Millinery Strategists

 
So our team has its strategy. The nub of it is to use the meeting beforehand to select one special sequence from every class, to which they will then compare their own via even equivalence. Call this strategy 1.

In fact, strategy 1 is overkill. The players don’t need to specify an individual sequence from each class. All they really need to select is one of the two subclasses. Of course, a unique sequence gives you a subclass (`the subclass containing A’), but not vice versa. Strategy 2 is to go through all the possible classes of sequences, selecting one subclass from each.

To put this into action, the first person will call “0” if the sequence is in the selected subclass, and “1” if it’s in the other. The next player now knows which subclass they’re in. Combining that with what he can see will tell him his hat-colour, and so on.

There is also a third possible strategy: the players use their meeting to decide upon a non-principal ultrafilter on the natural numbers. (I won’t go into further details here, people who care about such things can fill them in themselves.)

The Superpower to Choose

 
We have arrived at three solutions to the puzzle. But there are further questions: which strategy is the easiest? And what superpowers do the players need to follow it? Leaving aside their infinitely good eyesight, hearing, mental acuity, and patience, each strategy gives them a job to do during their planning meeting. These tasks are not at all straightforward!

In the example above, A is a very easy-to-describe sequence. Most sequences are not like this, but are uncomputable, random, and generally indescribable. In general, there is no procedure or algorithm that the players can hope to use to pick out a single sequence from each class, as strategy 1 requires. This can only be done using a superpower, meaning some version of the axiom of choice. But full choice is certainly excessive, and there is an assortment of weaker axioms. What is actually required here?

Strategy 2 appears slightly easier than 1: the players don’t have to select one sequence from the infinitely many in each class, they just need to pick one of the two subclasses. Nevertheless Lubarsky & Geschke have shown that this still requires more choosing-power than comes freely with the ZF axioms. What is more, strategy 2 is minimal: any strategy which solves the puzzle will allow a subclass to be selected from each class. Together these two facts imply that a team of hat-wearers working purely within ZF cannot solve the problem, but one with the full power of ZFC can. What is the minimum superpower, in terms of ability to choose, that the players need for each strategy?

We know from the above remarks that strategies 1 and 3 are each at least as strong as strategy 2. The conjecture here is that they are both strictly stronger than 2, and what is more that 1 & 3 are themselves inequivalent. Any further thoughts?