The ultimate prisoner puzzle

People like prisoner puzzles. Here is the hardest one I have ever seen. I heard it from Prof. Boris Bukh on the social hour of Maths Department couple of weeks ago, whom heard it on a maths conference. Since recently I am quite into Cryptography, especially setting up communication protocols, I would like to log the puzzle in my blog.

The storyline is like The Shawshank Redemption. You are locked into one of the cells in the jail. Unfortunately, you do not know how many prisoners there are in the jail. You do not even know whether you are the only one! The evil-hearted yet mathematically inclined warden wants to play a game with you. The rules are as follows.

1. On the first day, you can write up a communication protocol. The warden will make identical photocopies of your protocol and distribute them among other prisoners.
2. During the following days, everyday, each prisoner will be given one black card and one white card, and they should turn in one of them to the warden according to your protocol. The rest of the cards will be discarded. The warden would line up all prisoners in a circle in his mind and imagine each of them passes his or her chosen card to the next person clockwise. After going through all this in his mind, he will redistribute the cards to the prisoners accordingly. Notice, the warden could line up the people by any order he likes. Moreover, the orders could probably differ from day to day.
3. One day, you should call for a stop and immediately tell the number of prisoners in this jail. All prisoners including yourself will be released if you got the number correct.

Remember, the evil-hearted warden knows every detail of your protocol. So all odds are always against you.
The following is the solution I came up.

Denote the number of prisoners as p. First of all, we want to draft the protocol so that all prisoners know an upper bound of p, denoted as P. Before we say anything about the protocol, let us take a look at the significance of knowing such an upper bound.

If all prisoners know an upper bound P, then they can broadcast messages. To be precise, if one turns in a card of some color he chooses, say c. Everyone else should keep turning in white cards until he receives a black card, and then keep turning in black cards regardless of what cards are received. Then after P days, all prisoners will receive the the cards of color c. (Think about why this is true.) Now everyone knows the color c. Hence they succeeded in broadcasting a single bit. If the protocol says something about coding messages by colors, one can broadcast any message to others. Note that prisoners might not know who has sent the messages.

Though direct message is hard to realize in this situation, broadcasting would be good enough for us to figure out p.

Now, let us see how prisoners cooperatively figure out an upper bound P. We call it the first stage.

In the first stage, all prisoners will be labeled as either visible or hidden. At the beginning, only I am labeled as visible, all the rest are labeled as hidden. We break down the following days into several phases. At the beginning of the kth phase, all prisoners know the upper bound of the current visible prisoners P_k. For instance, P_1=1. Now, all hidden people broadcast the a single bit of message telling the others there are hidden people. The broadcasting is done similarly, i.e., whoever receives the black card once should keep sending black cards. The broadcasting can be done within P_k days because there are at most these many visible prisoners.

There are two possible turnouts. If no visible prisoner receives this message, then all prisoners are visible, and immediately all prisoners know P=P_k. Otherwise, on the next day, all visible prisoners turn in black cards. Whoever receives a black card changes his label to visible if it was hidden. The number of prisoners who change their labels is at most P_k. Thus we can use P_{k+1}=2P_k in the k+1th phase as now there are at most P_k+P_k visible prisoners. Since at least one prisoner changes his label in each phase, eventually, all prisoners will become visible. Hence this process will terminate at a certain phase and provides us an upper bound P.

After the first stage, comes the second stage.

In the second stage, we will partition prisoners by clans and try refining the clans as much as possible. During the second stage, each prisoner knows the total number of clans, the names of each clan and which clan he belongs to. At the beginning, I myself alone consists the first clan and the rest of prisoners consist the second clan. This initial set up is written into the protocol, so everyone knows it.

The following is how I refine the clans. I can broadcast a message that asks the members in a certain clans if any one has turned in a black card on a given day. Prisoners in this certain clan will broadcast a message of a single bit to indicate their answer. And then I broadcast a message that asks if any one in this clan has turned in a white card on that day. If both answers are ‘yes’, this means there are two people in this clan turned in different card on that given day. Then I will demand this clan to divide into two smaller clans according to the color of their cards turned in on that given day. I can also do the same thing to the cards they received on that given day as well.

So in the second phase, I can constantly refine the clans by asking questions clan by clan and day by day. Since the number of clans can not exceed P, this refining process will stop and the number of clans will stabilize. Moreover, once it stabilizes, prisoners in each clan will turn in the same cards and receive the same cards as well. Otherwise, some day I will interrogate the members in this clan and separate them into smaller clans.

Now we can assume the prisoners in each clans always turn in the same cards and receive the same cards. This is amazing!
Suppose c_i is the number of prisoners in the ith clan C_i for i=1,\ldots, n. Assume I am in C_1. Then c_1=1. Initially the values of all other c_is are unknown. Our goal is to find out each c_i, though it is enough to find \sum_{i=1}^nc_i.

Notation. [n] is the set of all naturals from 1 to n. If I\subset [n], c_I := \{c_i: i\in I\} and \mathrm{span}(c_I) be the set of all linear combination of \{c_i: i\in I\}.

For r = 1,\ldots, n-1, we claim that for all r-element subset I\subset [n] and i\in I, c_i can be written as a linear combination of \{c_j: j\in[n]-I\}. In abbreviation we shall write c_i\in \mathrm{span}(c_{[n]-I}). Note when we say ‘some variable can be written as a linear combination of other variables’, we mean all prisoners know this information. In other words, all prisoners keep track of these linear dependencies along the way. We will omit the details of how prisoners would share this information in the following proof and leave them to the readers.

Before we prove the claim, let us take a look at the consequence if what we claimed is true. When r=n-1, it means c_2, \ldots, c_n can be written as a linear combination of c_1=1. Thus we know c_i for all i\in[n]. Hence we know the total number of prisoners.

Now we prove the claim by induction on r. If r=1, we shall prove c_i\in \mathrm{span}(c_{[n]-\{i\}}) for all i\in[n]. This is relatively easy. Let the prisoners in the clan C_i send out black cards. Some of the other clans will receive those black cards. Thus c_i is the sum of the size of those clans which receive the black cards.

Suppose the claim is true for some r. Now we shall prove for every r+1-element subset I\subset [n] and i\in I, c_i\in \mathrm{span}(c_J), where J=[n]-I.

Fix some i_0\in I. By the induction hypothesis, we know for all i\in I with i\neq i_0, we have
c_i = \alpha_ic_{i_0}+\beta_i(c_J),
where \beta_i(c_J)\in \mathrm{span}(c_J).
This is also true for i=i_0. Because we may set \alpha_{i_0}=1 and \beta_{i_0}=0.

Let the index set I_+ be the set \{i\in I: \alpha_i > 0\} and I_-=I-I^+. As i_0\in I_+, I_+ is non-empty.

Now we demand all clans indexed by I^+ send out black cards. Suppose the clans indexed by I_+'\subset I_+ who send out black cards receive white cards and the clans indexed by I_-'\subset I_- and J'\subset J who send out white cards receive black cards. Hence we have the following equation.
\sum_{i\in I'_+}c_i = \sum_{i\in I'_-}c_i+\sum_{j\in J'}c_j

Hence
\sum_{i\in I'_+}\left(\alpha_ic_{i_0}+\beta_i(c_J)\right)=\sum_{i\in I'_-}\left(\alpha_ic_{i_0}+\beta_i(c_J)\right)+\sum_{j\in J'}c_j

The \alpha-coefficient on the left hand side is positive. Meanwhile it is nonpositive on the right hand side. Thus by the equation above we can solve for c_{i_0} in terms of a linear combination of c_J. Hence we can write c_i in terms of a linear combination of c_J for all i\in I. [qed]