Nonlinear Prisoners

OK, I just finished my PhD departmental defense, so now its time to look over the solution to the prisoners and light switches puzzle. I wanted to have a post calculating out how long the actual strategy would take for the prisoners to complete, so here we go.

First, we need to figure out how long each procedure will take to perform, starting with the upper bound procedure. The upper bound procedure has k nights of activating people, followed by k nights of deactivating people. If the number of prisoners is N, they will have to run k from 1 to N before the warden is forced to reveal there is an upper bound, this will take N(N+1) nights, and they will have an upper bound B=2N. The cannot say the upper bound is lower than that, as they do not know what the warden chose to do.

A ping procedure takes B nights to perform, obviously, and the bing procedure takes 1 night. The upper bound procedure is the awful one, for it takes 2z nights if it is called for on night z.

When the how many times can the warden make them call the upper bound procedure? Well, that depends on how big he can group them up. If he groups the prisoners into very large groups and then splits them off one at a time until they are all in their own groups of size one, the warden will maximize the number of times they perform the group division procedure.

Suppose we have N prisoners. As they run the upper bound procedure, the warden cannot do better than to split them into lg(N) groups. Actually, odds are that if he does this maximally, they will probably find their value of B faster and it will be smaller, but I don't want to do a more complicated calculation than this. So, they have taken on the order of N2 nights to find B, the group division procedure than takes like 2N2 nights. Next they do lg(N) pings, costing B lg(N) nights, but that is nothing compared to 2N2. The adversary makes one more group, so they call the group division procedure again and it takes 2^(2^(N2)) more nights.

We can see where this is going, the warden can make them call the group division procedure N-lg(N) times, resulting in the prisoners needing xN2 nights, where x is 2^2^2^2^..., N-lg(N) times, also known as 2 tetrad (N-lg(N)). I tried calculating out that number for something like N=20, but it was huge beyond my comprehension. So then I tried N=5, and again, it was huge beyond my comprehension. Basically, this strategy is stupid.

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 a1, a2, ....ak that obey a series of equations. Let S={a1, a2, .... ak} and suppose the equations have the following properties:
1) a1=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 2k-2 such subsets, also there is a1=1. In total we have 2k-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 {x1...xk} and {y1...yk}, we will now prove that xi and yi represent the same solutions. Define Li=xi/yi. The set of the Li is finite so it has a smallest element, call that L. Define zi=xi-Lyi. Since L is smaller than xi/yi, it must be the case that zi is nonnegative, but since L=xi/yi for some i, it must be the case that at least one zi is zero. We also know that the zi solve the same system of linear equations, being a linear combination of x and y.

Next, I claim that all the zi are zero. Suppose some of them are not. Let P be the set of zi=0 and P is not all of {z1....zk}, 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 zi. Since P is nonempty, we have that zi=0 and so xi=Lyi. Since a1=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 2W (treat a history of all zeros as 2W I guess). We have 2W nights of pinging, where if a prisoners history was i, they ping on the ith 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 G1 through Gk with G1 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 {G1....Gk} 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 G1 through Gk 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 {G1....Gk}, send out a bing if you are in a group which belongs to P. There are 2k-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 {G1....Gk}, we will have k rounds of pings. Send out a ping on the ith round if you belong to group Gi 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 G1 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.

Random Prisoners

Alright, time to do the solution to the latest prisoners and light switches puzzle. I'm not going to post everything about the full solution here, because that would take too long, but I do want to fully examine all the probabilistic solutions.

First of all, it is quite easy to establish an upper bound on the number of prisoners that there are. We will have two types of prisoners, called "active" and "inactive". If you are active, turn your switch on every night, if you are inactive you leave it off. Suppose we selected a number k that all the prisoners knew, and we begin with everybody inactive, but "you" begin active. If the light in your room comes on on a given night, you change your state to active and leave it that way. If we keep doing this for k nights, then at the end of the process there will be somewhere between k+1 and 2k activated prisoners. After k nights have passed, we can then check if there are any inactive prisoners still by reversing the strategy, make it so that if you see your light off, you turn inactive and stay that way. If there were still any inactive prisoners, then it will take no more than 2k nights to deactivate everybody.

The procedure is as follows: for each k starting at 1, spend k rounds activating people, followed by 2k rounds deactivating people. If at the end anybody is inactive, then it must be the case that everybody is inactive and the number of prisoners must be greater than k+1 (else everybody would have been active for sure), and we move on to the next value of k. If at the end of the deactivating process there are no inactive people then the number of people can be no greater than 2k.

We will call this entire process the "upper bound procedure", it will be used to establish an upper bound B on the number of prisoners. B will always be a power of 2, but that doesn't really matter for what we will do, it is sufficient that B is determined in a well prescribed way and at the end of the process we have determined an upper bound that every prisoner is aware of. Whats more they are all aware that they are all aware of it, and so on, thus making the upper bound "common knowledge" among the prisoners.

Once we have an upper bound on the number of prisoners, we can construct another procedure which I will call a "ping". A ping is a method for prisoners to send out a signal to everybody, such that a signal being sent becomes common knowledge. If the strategy calls for a ping on day M, the procedure lasts for B (=upper bound) days, from M to M+B-1. First, each prisoner decides if they would like to send out a signal or not, if a person would like to send out a signal they are "active", otherwise they are "inactive". As always, turn on your switch if you are active, and off if you are not. If your light comes on, change your state to active. If anybody was active, then by the end of the procedure everybody will be active, if nobody was active at the start then nobody will be active at the end. Thus, if our strategy call for a ping procedure on some specified day M, the prisoners will be able to distinguish "somebody wanted to send out a signal" from "nobody wanted to send out a signal". Note that they cannot distinguish "one person wanted to send a signal" from "two people wanted to send a signal", also note that the existence of a signal being sent becomes common knowledge.

We now have enough structure to set up our first solution. Begin by performing the upper bound procedure to find an upper bound B for use in the ping procedure. Next, have an agreed on number F which depends on B, such that if B independent integers are chosen between 1 and F, it is unlikely that any two of them are the same (I will make the concept of "unlikely" more precise later). Next, each prisoner selects a random integer between 1 and F. Now we call for F rounds of pings. On the ith round of pinging, send out a signal if your random number is i. After that, count the number of rounds that signals were sent out, guess that that number is the number of prisoners N.

As an example, suppose we determined that the number of prisoners was no greater than 8 (B=8), and we have agreed that in the case B=8, we will use F=100 000 000 (perhaps F=10B was agreed). You perform the 100 000 000 rounds of pinging, and signals are sent on the following rounds:
18398520
19216152
41001462
53182675
71507596
90195088

Then odds are that there are 6 prisoners. Its possible that there are 7 and two of them generated the same random numbers, but unlikely, it is even possible that there are 8 and there were two duplicates, but very very unlikely.

Given B random integers from 1 to F, what is the chance that two of them are the same? I did that calculation back when I was working out stuff about the birthday paradox, the answer comes out to be approximately B2/F, provided that B2 is much smaller than F. So, if you choose F=B2/e, then you fail with probability no more than e (this is approximately true as long as e is small, you might want to choose F=B3/e to be sure).

This completes the strategy that will work with probability 1-e for any e>0. This is also as far as I was able to get in figuring out this puzzle, everything after this was me cheating and reading other peoples answers.

For the next strategy, we will attempt to number the prisoners, and then each round we will check to see if anybody is still unnumbered, and then try to number them. If nobody is unnumbered we will declare success. The prescription will be such that everybody knows their own number and if m people are numbered the number m is common knowledge. It will begin with "you" being number 1 and everybody else being unnumbered. The strategy will gradually assign new numbers to people and will keep the total m common knowledge as we do it.

We will need a new, fairly simple, procedure for this solution (we will also need it for the final solution, so I might as well set it up now), a "bing" is a one night procedure, a person who wants to send out a signal turns on their switch that night, and people who do not want to send out a signal do not. Some other prisoners receive the signals, and some do not. The only thing that is common knowledge here is that the number of signals sent must equal the number of signals received (look, I said it was a simple procedure, but I need a name for it because I will use it alot).

Suppose that so far we have numbered people 1 through m, with m being common knowledge, first we have a ping round, send out a ping if you are unnumbered. If nobody sends out a ping we are done, N=m. If somebody out there is unnumbered we will next do something that will select a group of people S such that every person in S is an unnumbered person, and we will then assign numbers to the people in S.

We perform a bing where if you have a number you send out a signal, and if you are unnumbered you do not. If you received a signal that night and you are unnumbered then you are in S, if you received a signal that night and are numbered just remember it for now, we will need it later. S is necessarily nonempty, because there must have been an unnumbered person next to a numbered person. We must find the size of S and make its size common knowledge. We do this by having m rounds of pings, where on the ith round, you send out a signal if your number is i and you received a signal during the earlier bing night. This will determine how many "wasted" signals there were during the bing night. If there were no wasted signals then the size of S would equal m, and for each wasted signal then S will be 1 fewer than that. So at this point we have a set S of unnumbered people, each person who is in S knows that they are, and the size of S is common knowledge. We will denote the size of S with s.

Each person in S chooses a random integer between 1 and s, and then we have s rounds of pings. On the ith round, send out a ping if your random number was i. If there is a round where nobody sends a signal, then it must be the case that two people in S chose the same random number, go back to the start of this paragraph with the same set S. If a ping was sent every round then we are good, it means that each person in S has selected a different number between 1 and s. Each person in S can now claim the number m+i and each person who is numbered has a unique number, so we have now numbered people m+1 through m+s. Go back to the part of the strategy where we asked if anybody was still left unnumbered.

This strategy will always work eventually, a nonempty set S will get chosen and after some number of rounds they will eventually pick unique random numbers that they can use to number themselves with (it will on average take s! rounds to do that). Gradually people will all get numbered, notice this works even if the adversary is aware of what random numbers the random number generators are going to generate, though he might be able to delay it for quite some time in that case.

That is all I am going to post about this for now. Next time I will go over the full deterministic solution.

Crazy Warden

Alright, so I found a new puzzle on the xkcd forums, and it is just far too epic to not post here:
There are N prisoners and N cells in a prison (though the prisoners do not know the value of N). The cells are all identical from the inside, you cannot tell them apart. The cells are arranged in a circle, and in each cell there is a switch. The switch controls a light in the next cell clockwise around the circle. However, the power supply for these lights is usually off, and it only comes on at midnight each night for a tenth of a second (a tenth of a second not being long enough for a prisoner to see the state of their light and make a decision about their switch).

Each day, the warden will take the prisoners out of their cells and clean out the cells, setting the light switches back to "off". The warden will then place the prisoners back into the cells as he sees fit (the prisoners do not see eachother during this process). At any time, any prisoner may announce "I know how many prisoners there are." If they are then able to state the value of N, the prisoners win and are released, if they are incorrect they lose and all the prisoners are killed.

You are one of the N prisoners. Before the game, you may send out a single email outlining the strategy the prisoners must follow. Your email cannot refer to any prisoner in particular, as you know nothing about their identities. Find a strategy that guarantees the prisoners escape against the warden acting as an adversary.

Man, those wardens are nuts. Anyway, the light switch thing can be equivalently expressed as "every night each prisoner must simultaneously transmit a '0' or a '1' to the next prisoner clockwise from them". Your strategy may contain two types of prisoners, "you" and "everybody else".

The puzzle is pretty hard, I was only able to make a small amount of progress before giving up and just looking at the solution. There are a variety of degrees of solutions one can arrive at, there is a fairly easy strategy that works with probability 1-e for any e>0, and there is a better strategy that works with probability 1. In both of these cases, it is necessary to assume the prisoners have a private random number generator at their disposal to actually generate said probabilities. The full solution, however, is a guaranteed escape, and in fact is guaranteed that for each N there is a K such that "if the number of prisoners is no greater than N, we will escape before K days have passed". Though, K is a really really huge number compared to N.

The Lowest One

Solution time! Last puzzle was about Infinite Hats. Actually, its funny, I found a solution and then I told it to Mark and he found a slightly different solution that had the exact same probability of working, but then those clever people over at Tanya Khovanova’s Math Blog found a better solution than mine. Anyway, lets go over my solution first, because I'm egotistical like that.

First lets consider the two person case, as soon a one person guesses we are at probability 1/2 of being correct, and we simply need to make sure that both of them are right together or that they are wrong together. Specifically, I want to make sure that if Alice guesses wrong, Bob will also guess wrong (say). In this case, suppose Alice looks at Bobs hats and writes down the smallest number that is a black hat and similarly Bob writes down the lowest number that is a black hat on Alices head. So if Bobs first hat is black, Alice will write down 1 and then if she is wrong Bob will also be wrong.

What is the actual chance of this working? We will calculate this by looking up the hats on their heads slowly, starting at the bottom. If both are black then we lose, if one is white while the other is black, then the person with a white hat is considered correct, and if both are white we move up to the next pair of hats. Let P be the chance that one person is correct, in this case we have
P=0*1/4+1*1/4+1*1/4+P*1/4

that is, 1/4 of the time we get BB and we are wrong, in the cases where we get BW or WB then we are get one person correct, and in the case of WW we haven't really changed anything. One can solve this to get P=2/3.

Now that one person is correct, what is the chance that the other person is correct? Suppose we have already seen WB go by, so person 1 is already correct, now WB and WW both have no effect, and BB results in a loss while BW results in a win. This the odds are 1/2 of the second person being correct. All in all, the probability is 1/3 of winning the game, better than 1/4.

Actually, there is a faster way to arrive at that answer of 1/3. Consider looking at the hats that occur, from the bottom up, you will see a series of things like WW, WB, BW, BB, and then look for the lowest occurrence of each of BW, WB, and BB. If BW and WB each occur before BB, then we win. That is, of those three if the highest is BB then we win, which is clearly 1/3.

Naturally this strategy generalizes to 100 quite easily. Simply look for the lowest occurrence of all black hats by your teammates and write down that number. The relevant sequences are BBB...BBW, BBB...BWB, BBB...BWBB, ...., BWBB...BB, WBB...BBB, and BBB...BBB, of which there are 101. There is a 1/101 chance that the last one is that all black one, and then we win. This generalizes to a strategy that works with probability 1/(N+1).

Marks strategy was slightly different, instead writing down the lowest occurrence of all white hats rather than all black hats (attempting the align when the players are right rather than when they are wrong). The relevant sequences are the all white and all white with one black, again N+1 of them in total. Naturally the game is won if all white occurs before any of the other ones, and that is again 1/(N+1).

The better strategy can be arrived at in a similar fashion to some other hat puzzles, using modular arithmetic. First, let Ki be the location of the lowest white hat on person i's head. Let S be the sum of all the Ki. If each person knew S, they could find the value of Ki. Fix a constant CN (the constant can depend on N, the number of players). Each person is to make their guess assuming the following two things:
1) S mod CN = 0
2) each Ki is no larger than CN

If these statements are actually true, then this is enough for the players to guess correctly. What is the chance that those two statements were actually correct? Well, the largest Ki is going to be about as large as lg(N) (lg being log base 2), so if CN - lg(N) gets large as N goes to infinity, we should be safe as far as the second point is concerned. As for the first one, it will be on average probability 1/CN, since S is just a random number, and the two points are approximately independent. For example you could use CN=2lg(N) and then you have a chance of winning of about 1/2lg(N), maybe a little worse, but this is asymptotically much better than 1/(N+1). One of the posters at Tanya Khovanova's Blog showed that it is basically optimal to use CN=lg(N)+lg(lg(N))-lg(lg(lg(N))), but thats neither here nor there.

It is interesting that this better solution always attempts to find the location of the lowest white hat on your head, rather than any hat at all, so it seems clear one should be able to do better than this, but it is not clear how much better.