Prisoners, Information Transfer, and the Axiom of Choice

The following entry is courtesy a variety of people. I believe that I heard the initial version of this riddle from my twin. The follow-up to infinitely many people is due to Erick Knight. Note that since I’ve noticed that I’m not very good at remembering to post follow-ups to puzzles I post I am just going to include the solutions in this post.

Initial riddle: Suppose there are a hundred prisoners. They are in a room and told that they will be all lined up so that the first one can see the next ninety-nine, the second one can see the next ninety-eight but not the first person, the third one can see the next ninety-seven but not the first or second, and so on. Each one will have placed on his head a black or white hat. The first one gets to shout out “black” or “white” so that everyone in the line hears. Then the second one shouts out “black” or “white”. If everyone shouts out the same color as the hat that that person is wearing then they will all get to go free. What is the best strategy for the prisoners? Remember, they are able to communicate before hand but once in can only say “black” or “white”. And no using stupid tricks like delaying when they say it to communicate more information.

Answer:

The first person counts the parity of all hats they see, with black hats as 1 and white hats as 0. If the result is odd they black and if the result is even they say white. Each person after that one will then know what their hat is, since it must preserve parody with all the hats before and after them. Thus, they will get 99 hats correct and will have a ½ chance getting the first hat correct.

Exercise: generalize this to n different hat colors.

Now the part due to Erick Knight:

Suppose we have the exact same problem as before, but there are countably infinite prisoners each wearing a black or white hat (so there’s a first prisoner, a second prisoner, a third prisoner and so on). How can they assure that they at most finitely many people will not say the correct hat color. You may assume that the prisoners are able to see everyone in front of them.
Ok, the solution to this is unbelievably cool. Again, denote a black hat by 1 and a white hat by 0. So every possible string consists of some strings of 1s and 0s. Now, define an equivalence class on strings as follows: two strings are equivalent if they agree for all sufficiently far off digits. So for example, 010010000000000000... Is equivalent to 000000000… Now, from each such class pick a representative string, and remember it. When the prisoners are lined up each prisoner can see the string in front of him, and can recognize that as being in some equivalence class. So all the prisoner does is consults which representative string from that class they choose, and picks whichever 0 or 1 corresponds to his current position. Using this method, at most finitely many prisoners will get it wrong, because otherwise the string in question would not be equivalent and would thus not be a representative of that equivalence class.

Ok, isn’t that bizarre? It doesn’t even require any actual communication among the prisoners except at the start.

There are a number of objections to this solution: I will note three of them and discuss one of the more interesting ones in more detail:
Objection 1: People cannot look at infinite strings of data in finite time.
Objection 2: People cannot store all the representative strings (exercise so that the set of representative strings is uncountable).
These two objections are uninteresting, because even if one accepts them it isn’t at all clear why beings able to do these things should be able to get away with this. At best it is non-intuitive.
Objection 3: This is the interesting one: Who said I can pick representatives? In fact, in order to do so I need to use the axiom of choice, which says essentially that if I have a collection of disjoint non-empty sets I can pick one representative from each. This seems intuitive but the axiom can lead to strange results and some mathematicians do not accept the axiom. This puzzle gives a starting groundwork for appreciating that the axiom of choice although intuitive is strange. I hope to discuss the axiom of choice in more detail in a later blog entry.