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.

A few weighing puzzles

Here are three related puzzles. I'll post answers next week and discuss how it is related to certain notions in computer science.

1) Suppose I have ten stacks of ten gold coins each. Each coin weighs 1 ounce, but there is one set of counterfeit coins. The coins in that stack weigh only .5 ounces. You have a scale. What is the minimum number of weighings to determine which stack is counterfeit?

2) Suppose instead of a scale, you only have a balance and you don't know how light the counterfeit coins are but they are too light. Then how many weighings can you do it in? What if we instead have n stacks with one counterfeit? How many weighings does it take? Can you prove that you can't do it in fewer?

3) This last generalization is due to Elissa. Suppose we again have n stacks with one set counterfeit but instead of a balance we have a k-balance which compares k different objects simultaneously and returns their mass order. So for example, if on a 4-balance I had two two ounce objects (object a and object b respectively), one ounce object (c) and one three ounce object (d), I'd be told that
c < a = b < d. The normal balance is thus a 2-balance. In general for a k-balance with n stacks what is the minimum number of weighings?


Important PointAfter I put up this issue Etienne pointed a issue I had not anticipated. In the original phrasing of 2 and 3 there was only a single counterfeit coin and one no longer had stacks. In my phrasing above I assumed that this wouldn't make a difference for the general solution. It turns out that in fact it does. So instead for 2 and 3 assume that one just has n coins with 1 counterfeit rather than n stacks. Etienne has not yet worked out the general solution with stacks nor have I, so bonus points if you can do that.

Feel free to either post or email me solutions.

The number 1 does not exist.

Edit: I apologize for the crappy formatting. I'm having some trouble with blogger and using small fonts. I'll probably go harass Abbie or someone else who knows more about blogger's interface.

I'm a bit of a fan of fallacious proofs. This will be the first in a series of a posts over the next few weeks of some of my favorite fallacious proofs. Today we are going to prove that 1 does not exist.

Now you may recall from calculus that L'Hospital's rule states that if I have a limit of the form f/g and both f and g are both going to infinity or are both going to 0 then the limit is the same as the limit of f'/g' where f' is the derivative of f and g' is the derivative of g.

So for example, if I had lim x ->oo (x^2+1)/(2x^2) as x goes to infinity this would be equal to lim x ->oo 2x/4x=1/2 since the derivative of x^2+1 is 2x and the derivative of 2x^2 is 4x and both the top and the bottom of the original limit are going to infinity.

Another example would be if we had lim x ->oo (x+sin x)/x^2. We set f(x)= x+sin x and g(x)=x^2. f is going to infinity since sin x >=-1 so f(x) >= x-1 which goes to infinity. g(x) is clearly going to infinity. So we can apply L'Hospital's rule. f'(x)=1+cos x and g'(x)=2x. So lim x ->oo (x+sin x)/x^2 = lim x ->oo (1+cos x)/2x and this is clearly going to 0 since the top stays between 0 and 2 while the bottom goes to infinity.

Now a fun one: lim x ->oo (x^2+ sin x)/(x^2). I claim we can evaluate this limit without using L'hospital's rule. We have x^2- 1 <= (x^2 + sin x) <= x^2 + 1. Thus, (x^2- 1)/x^2 <= (x^2 + sin x)/x^2 <= (x^2 + 1)/x^2. Finally, since lim x ->oo (x^2- 1)/x^2 = lim x ->oo (x^2 +1)/x^2 = 1 (this is a good exercise if you haven't done any limit problems recently) we have lim x ->oo (x^2+ sin x)/(x^2) =1.

Now, let's see what happens when we apply L'Hospital's rule: Set f(x)= x^2+sin x and g(x)=x^2. Both are going to infinity. f'(x)= 2x+ cos x and g'(x)= 2x. So lim x ->oo (x^2+ sin x)/(x^2) = lim x ->oo (2x+ cos x)/(2x). Ok, this is still infinity over infinity so we can apply L'Hospital's rule again. Thus lim x ->oo (x^2+ sin x)/(x^2) = lim x ->oo (2x+ cos x)/(2x) = lim x ->oo (2 - sin x)/(2), and this limit doesn't exist because sin just keeps oscillating. But the limit has to be 1 by our earlier work. We thus conclude that 1 does not exist.