XOR’s Hammer

Here’s a puzzle:

You and Bob are going to play a game which has the following steps.

1. Bob thinks of some function (it’s arbitrary: it doesn’t have to be continuous or anything).
2. You pick an .
3. Bob reveals to you the table of values of his function on every input except the one you specified
4. You guess the value of Bob’s secret function on the number that you picked in step 2.

You win if you guess right, you lose if you guess wrong. What’s the best strategy you have?

This initially seems completely hopeless: the values of on inputs have nothing to do with the value of on input , so how could you do any better then just making a wild guess?

In fact, it turns out that if you, say, choose in Step 2 with uniform probability from , the axiom of choice implies that you have a strategy such that, whatever Bob picked, you will win the game with probability 1!

The strategy is as follows: Let be the equivalence relation on functions from to defined by iff for all but finitely many , . Using the axiom of choice, pick a representative from each equivalence class.

In Step 2, choose with uniform probability from . When, in step 3, Bob reveals , you know what equivalence class is in, because you know its values at all but one point. Let be the representative of that equivalence class that you picked ahead of time. Now, in step 4, guess that is equal to .

What is the probability of success of this strategy? Well, whatever that Bob picks, the representative of its equivalence class will differ from it in only finitely many places. You will win the game if, in Step 2, you pick any number besides one of those finitely many numbers. Thus, you win with probability 1 no matter what function Bob selects.

This puzzle originally had the following form:

Suppose that there are countably infinitely many prisoners: Prisoner 1, Prisoner 2, etc., arranged so that Prisoner can see Prisoner iff .
A warden puts either a red hat or a blue hat on each prisoner’s head, and asks each to guess the color of the hat on his own head. Prove that the prisoners have a strategy of coordinating their guesses so that only finitely many of them will be wrong.

As before, let be the equivalence relation on functions defined by iff and differ on only finitely many places. The prisoners’ strategy will then be: Beforehand, pick a representative from each equivalence class. Let be the color of the hat on Prisoner ’s head. Then, since each Prisoner can see the color of the hats on Prisoner for , each prisoner knows which equivalence class is in. Suppose is the representative that they picked beforehand. Then, for each , Prisoner will guess that he’s wearing hat , and since , only finitely many of them will be wrong.

For some interesting comments on this puzzle, see Greg Muller’s blog post on it here and Chris Hardin and Alan Taylor’s paper An Introduction to Infinite Hat Problems.

After hearing this puzzle, Chris Hardin came up with a great generalization. Instead of having a Prisoner for each and declare that Prisoner can see Prisoner iff , let be an arbitrary partial order and declare that for each , there is a Prisoner , and that Prisoner can see Prisoner iff . Assuming again that red and blue hats are placed on all prisoners and that they must all guess the color of the hat on their own head, how many of them will be able to guess correctly?

Call a partially ordered set reverse well-founded if there are no strictly increasing chains in it. Chris Hardin and Alan Taylor showed in their paper A Peculiar Connection Between the Axiom of Choice and Predicting the Future that the prisoners have a strategy so that the set of prisoners who are wrong will be reverse well-founded. In the case of the original prisoners problem, this implies that there will be only finitely many prisoners who are wrong, since there are no infinite reverse well-founded subsets of .

Suppose that there is a Prisoner for each and that Prisoner can see Prisoner iff . Then, since all reverse well-founded subsets of are countable, at most countably many prisoners will be wrong under the Hardin-Taylor strategy. Since all countable subsets of are measure zero, this gives another way to win the game against Bob with probability one.

In fact, it implies that you can do more: You don’t need Bob to tell you , just . Hardin and Taylor express this by imagining that we represent the weather with respect to time as an arbitrary function . Then, given that we can observe the past, there is an almost perfect weatherman who can predict the current weather with probability 1. They further show that the weatherman can almost surely get the weather right for some interval into the future.

What is the Hardin-Taylor strategy? What the prisoners do is that they first choose a well-ordering of the set of functions from to (this uses the axiom of choice), and then for each , Prisoner simply guesses that his hat color is , where is the -least function consistent with what Prisoner sees.

Now, suppose that there is a sequence of prisoners who are wrong. Since each Prisoner sees all the prisoners that Prisoner for sees, we must have that . In fact, since for (since by assumption Prisoner was wrong about his hat color, whereas Prisoner will be right about it, since he can see Prisoner ), we have that , but this contradicts the fact that is a well-ordering.