How many prisoners?

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

 

 

 

You, together with a finite number n-1 of other ideal mathematicians, have been arrested on a whim by a generic evil dictator and are about to be locked up in a prison. The prison is circular, with n identical windowless cells arranged in a ring around a central court. There are some problems with the lighting system - the light switch in each cell controls the light in the next cell clockwise around the ring. Even worse, electric power is only provided to the lights for one tenth of a second each night, just after midnight.

The warden is worried that you might use the lights to communicate (very slowly), so he will very often rearrange the prisoners, moving them about between the cells in any way he chooses and having all the cells cleaned to prevent prisoners leaving messages for one another. He might do this every day. This will all be done in such a way as to keep you all in ignorance; you will never see each other or any part of the prison except the inside of the cells. You do not even know how many other mathematicians are to be locked up with you.

The warden visits you in your cell, and explains that if you are able to communicate despite these precautions he will consider you all worthy of release. At any time, any prisoner who believes he has discovered how many prisoners there are may petition the warden for release. That prisoner will be allowed one guess at the number of prisoners; if they guess correctly, then all the prisoners will be released, but if they guess incorrectly then all the prisoners will be executed.

You have been chosen to devise a strategy by means of which you will be able to discover the number of prisoners. You may compose a single email outlining your strategy, which will be passed to all the prisoners. However, your strategy must be foolproof, as the warden (who has a deep hatred of ideal mathematicians) will also read your email.

Is there a strategy which will guarantee your release? If so, give one. If not, why not?

Solution

This solution was created by me, Gene Foulk, and Casey Hart (coworkers).
First, some observations:
1. There is a "special" prisoner, the one sending the email, and this is needed to know who starts off the process.
2. If the prisoners are in two non-empty groups, one sending light and one sending dark, it is impossible for the warden to arrange it so no dark senders see a light (and conversely so no light senders are sent a dark). The worst the warden can do is to set all the light emitters in a row, but then the last one will send light into the dark group, and the first will see a dark sent.
3. I assume prisoners can count days, and have perfect memories. It also turns out they need extremely long lifespans for this to work! But they are ideal mathematicians....

Suppose there are N prisoners; now the goal is for some prisoner to determine N.

The first task is to determine an upper bound on the possible number of prisoners and to ensure all prisoners know this bound. So k rounds labeled R1,R2,...,Rk are performed, with k to be determined in the process. Prisoners are broken into two classes: tagged and untagged. Initially only the special prisoner is tagged, and all others are untagged. On the first night of each round all prisoners who have been tagged will turn on their switch, and all others will turn theirs off. Any untagged prisoners seeing a light become tagged, and tagged prisoners remain tagged. Then a known number of nights (determined below) of the following: tagged prisoners turn on their switches until they are sent a dark, at which point they turn off all remaining lights this round. What happens (proven next) is each round ends with all prisoners seeing dark, until one round all prisoners see light, and then all prisoners will know an upper bound on N.

Here are the details: suppose at the start of round Ri, there are ti tagged prisoners and the rest are untagged. t1=1. When the ti tagged send a light, between 1 and ti new prisoners get tagged (depending on how the warden arranges this night). Thus at the end of round i, there must be between i+1 and 2^i tagged prisoners, inclusive. Note at least one new tagged prisoner exists. Now after each night in the second part of the round, if there is at least 1 untagged prisoner, by observation 2, there will be one less light sent the following night. After 2^i nights, if there was any untagged prisoners, every prisoner will see dark. Otherwise, after 2^i nights, if there were no untagged prisoners, everyone will send light each night, and all prisoners will see light at the end of the 2^i nights. Thus at the end of a round all prisoners know if everyone was tagged.

Thus rounds are performed until at the end of round Rk every prisoner sees a light. Since at least one prisoner gets tagged each round, k<N. Since the number of tagged prisoners at most doubles each round, N<2^k.

As part of this process, each prisoner remembers the round where they got tagged, remembers it as a binary number, and this is called their history. Each prisoners history will have bits appended below as needed, and will be used to separate them into groups. Currently each prisoners group is all prisoners tagged in the same round.

Let K=2^k, which is an upper bound for N.

Before the next task, here is an observation. A prisoner (or group of prisoners) can send a message to everyone if everyone knows when to start receiving as follows. The senders by emitting light (or dark) every night for K nights, and everyone else emits dark until they see a light, at which point they emit light. At the end of K nights, everyone will see light or dark, thus sending a bit of information. This is called signaling.

Now the prisoners perform a task consisting of a loop that either splits groups into smaller groups or leaves all groups alone, depending on what the warden does. If the groups are split into smaller ones, the process repeats. If no groups are split after two group measuring tasks, the final task is executed, which allows all prisoners to compute the group sizes, the sum of which is N. The number of passes must terminate since each pass either splits one or more groups into smaller pieces, and there can be at most N groups, each of size 1.

Each loop has two parts, 1) group counting and, 2) subset lighting.

In part 1, each player knows the current length L of history stored, and the history determines the group membership. For L cycles of K nights each, if a prisoner has history j, on night Kj that prisoner signals everyone that such a group exists, which takes K nights. At the end of each K night period, all prisoners know if group j has anyone in it or not. This takes LK nights. this results in there are n groups with sizes a1,a2,a3,...,an, which the prisoners want to determine. Let the special prisoner be in group a1, so a1=1 since no other prisoners can have the same history.

Next part 2 is performed, subset lighting. In this stage all possible subsets of the groups emit information just for one night each, and all these bits are appended to prisoner history. Suppose everyone knows there are n groups. Each prisoner counts 000...00 to 111.111 (n bits), one count per night, and for each count, if bit j is lit and prisoner is in group j then emit light, else do not emit light. For each light seen append a 1 to history and for each dark append a 0. This results in testing all subsets of {a1,a2,..,an}, which is explained below.

Now, the group counting (part 1) is done again. If there are the same number of groups, the final task 3 below is executed, else 2 is repeated, this time with the new history and new groups (which everyone knows from 1). Note each change in group numbers has to be a split, since all history matches in the previous group except perhaps the last bits. Prisoners in different groups remain in different groups. Note that each round the number of groups increases, so the value of n above increases to at most N.

Task 3, the final task: basically groups are split until no more splits happen. Suppose for each subset A of the current round of group sizes {a1,a2,...,an} that that no groups were split.

This means everyone in each group either saw light or saw dark, so looking at the total number of lights turned on from aj in A, the total seeing those lights must also sum to the same value. By observation 2 there must be a person not in the groups represented in A, so there must be at least one group receiving light that is not in A. So to each subset A of {a1,a2,...,an} there is a corresponding subset B of those groups who all saw (or did not see) light from A. Now this information is distributed to all: for each of the 2^n subsets, for each group 1,2,..,n, K nights are spent signaling everyone which group(s) saw which subset lighting up.

So now everyone knows the number n of the groups, and for each subset A of {a1,a2,...,an}, which subset B (depending on A) saw the lights. Each time A is nonempty and A is not all of the groups the resulting B must contain a group not in A by observation 2.

Now the question: are all groups necessarily split into single prisoners? The answer is no, and a little playing around with group sizes 1,1,1,1 and group sizes 1,1,2,2 show that there can be 4 groups, and the sizes are not unique (yet).

This leads to needing the following lemma (proven last):

Lemma: Given the set S={a1,a2,...,an} of real numbers, suppose for each nonempty, proper subset A of S, that there exists a subset B of S such that B contains at least one number not in A, with the property that sum of aj in A = sum of aj in B. Then given the relations A->B, all solutions for the values of S are determined by the value of a1.

If this is true, then since a1=1 in our case, there is a unique solution to the relations given from the A and B, which all prisoners know. We know there is at least one solution which gives the correct value of N. We must show this solution is unique (done below). Thus, being ideal mathematicians, they solve the equations, learn the values of a1,a2,..,an, and thereby N, and thereby escape.

On a practical note, there are 2^n equations over n variables, and they are all linear, so they are practically solvable using Gaussian elimination. So given the A and B, the solution is straightforward to actually compute.

Finally, the proof of the lemma, at which point this is finished.

Lemma: Given the set S={a1,a2,...,an} of real numbers, suppose for each nonempty, proper subset A of S, that there exists a subset B of S such that B contains at least one number not in A, with the property that sum of aj in A = sum of aj in B. Then given the relations A->B, all solutions for the values of S are determined by the value of a1.

Proof: Suppose {b1,b2,...,bn} is another solution, with b1=a1 (since the values are determined by the first entry being fixed). Then for each equation sum of aj in A = sum of aj in B, we must have the same for sum over bj when aj in A = sum over bj when aj in B. Subtracting gives the same relation for cj=aj-bj.

Now take A={aj such that cj >= 0}. b1=a1 so A is nonempty. If A is not all of S, then there is a matching B, and

sum of cj when aj in A = sum of cj over B = (sum of cj for aj in B and not A) + (sum of cj for aj in B intersect A) <= (sum of cj for aj in B and not A) + (sum of cj when aj A), and subtracting the last term from both ends, results in

0 <= sum of cj when aj in B and not A. This sum is nonempty since B must contain a term not in A, but this means the right hand side is negative (since cj anything outside A must be negative), which is a contradiction. Thus A must be all of S.

Similarly, starting with A={aj such that cj <= 0} we get again that A is all of S. Then S={aj such that cj >=0} intersection {aj such that cj <= 0} which means all cj = 0. This means bj=aj for all j, and the solution for S is unique once a1 is fixed.

Solution complete!