This is a nicely hard problem in the common prisoners and warden format.

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?

I’ll add there is no trickery involved. It is solvable as a pure logic puzzle.

Solution

This solution was created by me, Gene Foulk, and Casey Hart (ex-coworkers at Cybernet Systems in Ann Arbor). 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 sets, 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 set, 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, after all….

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

Task 1 - determine an upper bound on 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 $R_1,R_2,…,R_k$ are performed, with $k$ to be determined in the process. Prisoners are broken into two sets: 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 fixed 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 $R_i$, there are $t_i$ tagged prisoners and the rest are untagged. $t_1=1$. When the $t_i$ tagged send a light, between $1$ and $t_i$ 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 $R_k$ every prisoner sees a light. Since at least one prisoner gets tagged each round, $k\le N$, and the process must terminate. Since the number of tagged prisoners at most doubles each round, each prisoner now knows $N \le 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 sets. Currently each prisoners set is all prisoners tagged in the same round.

Task 2 - TODO

Let $K=2^k$, which is an upper bound for $N$. All prisoners know $K$ at this point.

Before the next task, here is an observation. A prisoner (or set 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 sets into smaller disjoint sets or leaves all sets alone, depending on what the warden does. If the sets are split into smaller ones, the process repeats. If no sets are split after two set measuring tasks, the final task is executed, which allows all prisoners to compute the set sizes, the sum of which is $N$. The number of passes must terminate since each pass either splits one or more sets into smaller sets, and there can be at most $N$ disjoint sets, each of size 1.

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

Set counting

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 the $j^{th}$ cycle of length K that prisoner signals everyone that such a set 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 sets with sizes $a_1,a_2,a_3,…,a_n$, which the prisoners want to determine. Let the special prisoner be in set $a_1$, so $a_1=1$ since no other prisoners can have the same history.

Subset lighting

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$ sets. 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 ${a_1,a_2,..,a_n}$, which is explained below.

Now, the set counting (part $1$) is done again. If there are the same number of sets, the final task $3$ below is executed, else $2$ is repeated, this time with the new history and new sets (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 ${a_1,a_2,…,a_n}$ that that no sets were split.

This means everyone in each set either saw light or saw dark, so looking at the total number of lights turned on from $a_j$ 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 ${a_1,a_2,…,a_n}$ 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 sets(s) saw which subset lighting up.

So now everyone knows the number $n$ of the groups, and for each subset $A$ of ${a_1,a_2,…,a_n}$, 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 unfortunately 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={a_1,a_2,…,a_n}$ of real numbers, suppose for each nonempty, proper subset $A\subsetneq S$, that there exists a subset $B\subset S$ such that $B$ contains at least one number not in $A$, with the property that $\sum_{a_j\in A}a_j = \sum_{a_j\in B} a_j$. Then given any such mapping $A\rightarrow B$, all solutions for the values of $S$ are determined by the value of $a_1$.

If this is true, then since $a_1=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 $a_1,a_2,…,a_n$, 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.

Proof: Suppose ${b_1,b_2,…,b_n}$ is another solution, with $b_1=a_1$ (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!