Before discussing the solution to last week’s problem, I want to mention another interesting problem, which led to this latest one:
100 Prisoners. This is perhaps my favorite of the many of the “prisoners-with-a-strategy-for-collective-survival” type. It goes as follows: you and 99 others are held prisoner by the usual bloodthirsty yet eccentric pirates, who offer the following scenario. In a room are 100 boxes, and in each box is a slip of paper with exactly one prisoner’s name on it. Each prisoner’s name appears on the slip in exactly one box. Each of you in turn will be taken into the room, one at a time, and allowed to open at most 50 boxes, inspecting the slip in each box, looking for the slip with your own name on it. You must leave the room and the boxes exactly as you found them, and you may not communicate with the other prisoners in any way. Once all 100 prisoners have entered and exited the room, if all 100 of you were able to find your name, then you will all be freed. If even one of you fails to find his name, you will all be executed. You may discuss strategy before beginning. How can you maximize your chance of survival?
This problem is interesting because, at first glance, survival seems nearly impossible. For example, if each prisoner simply chooses any 50 boxes at random, finding his own name with probability 1/2, then the probability that all of the prisoners find their names is only . The surprising fact is that it is possible to do much better, using a clever and rather simple strategy.
I have seen this problem, and its solution, before– what is recently new to me is that this simple strategy is in fact best possible, proved in 2006 by Eugene Curtin and Max Warshauer; see “The Locker Problem” for their excellent article describing the problem, the strategy, and its optimality.
Two Prisoners. While reading about Curtin and Washauer’s result, I stumbled upon the problem in last week’s post, originally discussed on Oliver Nash’s blog. There is a great description there not only of the solution, but also of some interesting generalizations to other similar problems. But the strategy may be described very concisely:
Number the squares on the board from 0 to 63. You compute the bitwise exclusive-OR of (1) the indices of all of the squares with coins showing heads, together with (2) the index of the square selected by the pirate. Flip the coin on the square with the resulting computed index. Your friend computes the bitwise exclusive-OR of the indices of squares showing heads; the resulting index indicates the selected square.
The chess board turns out to be a bit of a red herring. That is, consider trying to solve the problem for a different number of squares/coins than 64. It is not necessary that be a perfect square. A nice application of the pigeonhole principle shows that a necessary condition is that be a power of 2 (why?). The above explicit strategy shows that this condition is also sufficient.