## 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 Guassian 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!