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.
1 comment:
Holy shit.. how does your brain fit inside your head?? I think I actually lost several brain lobes from being over intellectualised...
Post a Comment