Linear Prisoners

Alright, time to do the second half of the solution to the prisoners and light switches problem. In order to explain the solution in full, we first must make use of a lemma (thats right, this solution is so epic that it actually needs a lemma).

First, the statement of the lemma:

Suppose we have a system of unknowns a₁, a₂, ....a_k that obey a series of equations. Let S={a₁, a₂, .... a_k} and suppose the equations have the following properties:
1) a₁=1 is one of the equations
2) For every nonempty, proper subset P of S, there exists a subset Q of S such that there exists an x in Q that is not in P and one of the equations reads "the sum of P" = "the sum of Q"
3) There exists a positive solution to the equations

Then, the solution is unique over the positive numbers.

Alright, lets try to make sense of this lemma before I go proving it. First, we have k unknowns that obey some equations, how many equations exactly? Well, for every nonempty proper subset P of S, there is an equation, and there are 2^k-2 such subsets, also there is a₁=1. In total we have 2^k-1 equations for this system, so it is probably extremely overspecified. The lemma says that if we are so lucky that a solution actually exists, there is not going to be more than one.

As an explicit example, lets suppose we have three unknowns, a, b, c, that obey these equations:

a=1
a=b
b=a
c=a+b
a+b=c
a+c=b+c
b+c=a+c

We can see that it satisfies the conditions of the lemma, for every nonempty proper subset of {a,b,c}, that subset appears summed on the left side of some equation and there is a subset that is summed on that left side such that the right side has at least one element that is not on the left. Clearly one can see that a=1, b=1, c=2 is a solution, and it is fairly obvious that it is unique. In fact, we don't even need to restrict a, b, and c to be positive to get uniqueness, and I think the lemma is true without it, but the proof is very simple with that assumption. Whats more, for our purposes of solving the puzzle, we only need the lemma to be true over the positive integers.

Note that instead of b+c=a+c, we could have had b+c=a instead. Then we would still have satisfied condition 2), but not condition 3), making it so that the lemma gives us nothing useful.

Alright, lets go with the proof now. Suppose we have our system of equations and we have two sets of positive solutions {x₁...x_k} and {y₁...y_k}, we will now prove that x_i and y_i represent the same solutions. Define L_i=x_i/y_i. The set of the L_i is finite so it has a smallest element, call that L. Define z_i=x_i-Ly_i. Since L is smaller than x_i/y_i, it must be the case that z_i is nonnegative, but since L=x_i/y_i for some i, it must be the case that at least one z_i is zero. We also know that the z_i solve the same system of linear equations, being a linear combination of x and y.

Next, I claim that all the z_i are zero. Suppose some of them are not. Let P be the set of z_i=0 and P is not all of {z₁....z_k}, then by 2) there exists a Q such that the sum of P is the sum of Q and Q has an element that is not in P. But the sum of P is zero, and the sum of Q cannot be. This contradiction shows that P is either empty or all of the z_i. Since P is nonempty, we have that z_i=0 and so x_i=Ly_i. Since a₁=1 is one of the equations, it must be the case that all the x's and the y's are equal, completing the proof of the lemma.

Good times.

Now, lets construct the solution to the puzzle.

Recall we had three procedures previously, the "upper bound procedure", to find an upper bound B on the number of prisoners, the "ping", a B round procedure to send out a common knowledge signal to everybody, and the "bing", a one round procedure to send out a signal with the knowledge that the number of signals out equals the number of signals received.

We will need to define one more procedure for this solution, the "group division procedure". If this procedure is called for on night W, each prisoner looks at their history for the past W-1 nights and treats it as a binary number between 1 and 2^W (treat a history of all zeros as 2^W I guess). We have 2^W nights of pinging, where if a prisoners history was i, they ping on the i^th night. This divides people into groups. First, "you" are in group 1, and then the first group of people to ping during the group division procedure are the people in group 2, the next group of people to ping are group 3, the next group is group 4 and so on.

At the end of the group division procedure we have groups G₁ through G_k with G₁ having only "you" in it. The number of groups k is common knowledge and every person knows what group they belong to.

Note that if we call the group division procedure and get k groups, and then later we call it again and get h different groups, it must be the case that h is no smaller than k, people who had different histories at one point cannot later "merge". Whats more, if h=k, each person must be in the same group as they were last time.

The main goal of the strategy is to have every nonempty, proper subset of {G₁....G_k} send out a bing, which will be received by other people in other groups. we then check to see if everybody in the same group received the same signals, if they did we will have a series of equations that we can solve, and the lemma will guarantee the uniqueness of the solution. If it was not the case that everybody in a group received the same bings, then we can use that to make a finer group division. The adversary will have to choose between making finer and finer groups or giving us our series of equations. Eventually the groups will all be size 1, then the adversary will have no choice.

Alright, explicitly the strategy is:

First, perform the upper bound procedure, obtain a common knowledge upper bound B on the number of prisoners.

Next, perform the group division procedure, there are now groups G₁ through G_k and each prisoner belongs to some group and knows what group they belong to. k is also common knowledge.

Next, for each nonempty proper subset P of {G₁....G_k}, send out a bing if you are in a group which belongs to P. There are 2^k-2 such subsets, so there will be that many rounds of bings. Make a note of any bings you receive and the particular set P that it came from.

Next call the group division procedure again, if the number of groups is larger than it used to be, go back to the previous paragraph using the new groups, if the number of groups is the same as before, it must be the case that everybody in a given group has had the exact same history the whole time, even throughout the bing rounds.

Next, for each nonempty proper subset P of {G₁....G_k}, we will have k rounds of pings. Send out a ping on the i^th round if you belong to group G_i and you received a signal from P during the most recent bing round.

Now, for each nonempty proper subset P we know what groups received a signal from that set, meaning that we have an equation that reads "the sum of P" = "the sum of Q" for some known Q. Whats more there must be something in Q not in P, as there cannot be a closed loop that is less than all the prisoners. We know the size of group G₁ is exactly 1, as that group is "you". Finally, a solution to these equations must exist if the prisoners actually performed it. Our lemma guarantees that there is not more than one solution to this set of equations, so we can uniquely solve them to get the size of every single group. Since every prisoner was in some group, we can just add the size of the groups to get N.

This completes the deterministic solution to the puzzle. It is a bit funny that the final value of N is common knowledge to the prisoners, none of the solutions presented made use of the fact that any individual prisoner can declare knowledge of N, it didn't have to be common knowledge. Anyway, I doubt that there is much improving on this solution, because you have such limited communication available and the adversary can really restrict what sort of things you can attempt. Anyway, next time I want to do a post about how long this solution might take to implement. My guess is something like 2 tetrad N, but I haven't calculated it out yet.