(Also lomonster.com and clomont.com)

Prisoners in Limbo


This riddle comes from the XKCD forums, at http://forums.xkcd.com/viewtopic.php?f=3&t=79935 and is as follows:

20 people are sent to Limbo. Before they can go to heaven, they must complete the following task: At noon each day, one person is chosen (uniformly at random) to go to a room with 2 switches, each with 2 states.They must switch exactly one switch. The nature of the switches is unknown beforehand (no "left and right, on and off" they can agree on), they may not be identical, and they may not appear the same to different prisoners (for example, prisoners may see colors differently or the room might always flip upside down for some of them) but will always be the same for the same prisoner.

Eventually, a prisoner must state that not only has everyone been to the room, but the last 20 people sent to the room included all 20 prisoners. If they are correct, everyone goes to heaven. If they are wrong, everyone goes to hell.

The prisoners know the above scenario. Before the task the prisoners have time to gather and make a strategy, but during the task they cannot communicate other than by the switches. They are able to keep track of time and know when the task will begin.

How can they go to heaven with probability 1?



This solution was created by me and Gene Foulk.

All prisoners know the stages for the solution and the lengths of each task beforehand. One prisoner is selected as the Counter. Then they execute the following stages, each for a predetermined number of days. If after all stages a win is not detected, the process repeats. Since the probability of a win is greater than 0 and there is no possibility of a false win claim, the probability of winning overall is 1. The stages are:

Labeling Stage: The first task is get agreement on the naming of the switches with high probability p1, determined later. For d1 days each prisoner j does the following: the first time in the room, choose a random labeling of switches Aj and Bj, switch Aj and remember Bj. On every subsequent entry, if Bj has been switched, randomly (with probability 1/2) reverse the labeling Aj and Bj. Switch Aj, remember the current Bj, and leave.

This is a random walk with stationary states being all prisoners agreeing on a labeling A and B for the buttons. The ways this can fail is if a prisoner never gets into the room (in which case that prisoner knows it, and selects a random A and B label the first time they enter the room) or a prisoner has chosen incorrectly. The former becomes less likely as d1 increases and the second one becomes less likely also as d1 decreases because the random walk has agreement on labels as the only stationary states.

Now call A and B the labels that the Counter has chosen. Other prisoners agree with him with high probability, but there is some chances for error, which are tracked throughout. This Aj=A and Bj=B for j=1,2,...,20 with high probability.

Direction Stage: Next, for d2 days, if prisoner j enters, he observes the state of the Aj switch and calls that the "on" direction Oj, and he toggle the Bj switch. Anyone not entering in the first stage picks a random set of labels and directions on first entry. After d2 days, everyone (with nonzero probability) knows the direction of Aj as Oj. So now (with high probability) everyone agrees on switch labels and directions. If we label the probability of this stage working as p2 given that the Labeling Stage succeeded then the chance of being correct so far is p1*p2.

Counting Stage: here the Counter makes sure everyone agrees on the switch labels and directions. On the first day, whoever enters the room makes sure A is off (toggling either A or B as needed). Then for d3 days the following is executed. The first time a prisoner other than the Counter enters the room when A is off, he turns it on. In all other cases he toggles B. Each time the Counter enters the room, if A is on, he increments a count tracking how many unique prisoners turned on A. The Counter makes sure that A is off on leaving by toggling A or B. Again, with enough days d3, the Counter will have counted everyone with high probability. Call the probability of success, given that the previous stages succeeded, as being p3. Thus the chance of success so far is p1*p2*p3.

Now for the final stage.

Direct Ordering: Then for d4 days the following cycle repeats in 20 day period. On the first day of a cycle the prisoner turns off A, which is used to detect duplicates. Each time a prisoner enters for the first time, B is toggled. Anytime a prisoner enters more than once in a period he turns on A. If the Counter is chosen on the last day and he sees that A is off, then he knows 20 unique prisoners have entered including himself, and he declares this and wins.


Solution complete!