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.
Showing posts with label prisoners. Show all posts
Showing posts with label prisoners. Show all posts
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:
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:
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.
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:
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.
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:
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.
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.
Patient Prisoners
So, continuing my earlier ideas about the solution to the prisoners problem, lets see how long we expect the strategies to take. First, as a warm up, lets figure out in the case that the prisoners know the initial position of the light switches. Before I can do that though, I need to prove a very useful lemma that will be used constantly in the discussion of the solution.
Naively, one expects the answer to be 1/p (if the coin has 1/3 chance of landing on heads, you expect to need to flip it 3 times). Of course, there is a small chance that you will need 4 flips, or 5 flips, or a billion flips. There is some sort of concern that the infinite sum will ruin things, so lets actually perform the infinite sum. The chance of stopping on exactly the Nth flip is p(1-p)N-1, as (1-p)N-1 is the chance you failed the first N-1 flips, and p is the chance you stopped on the Nth one. Summing to find the expectation value of N, and we will denote 1-p=q and D as derivative with respect to q, so we have
So, we see that the naive expectation is actually correct, still, it is nice to prove it.
Now, moving on with our actual problem, for our strategy to work, we first must have one of the 99 non master prisoners to come in, then we need the master to come in, then one of the 98 remaining, then the master again, and so on down the line. the chance of each of these events is easy to figure out (remember, we are assuming that the warden selects a random prisoner each day). So, for the first few terms, the number of days it takes is 100/99+100+100/98+100+100/97+... since each time the master needs to enter the room, it takes about 100 days for that to happen. The full sum is
Where N is summed from 1 to 99. Approximating, that comes out to 9900+100Ln99 ≈ 10359, which is a little over 28 years. It would be nice to see if there is a solution with a smaller expectation number of days, especially since the average number of days it takes for every prisoner to enter the room once is 100Ln100 ≈ 460.
Now, for the real problem we have a bit more of a trick on our hands. For the solution when the prisoners do not know the initial position of the switches, they must have the master enter the room 198 times to count everybody. This means we have a flat out 19800 days on top of how long it takes the non masters to do their stuff. Each prisoner must enter the room twice and then gets ignored. This is equivalent to the following problem:
If we let F(N) denote the solution to that problem, then our prisoners expect to get out in 19800+F(99) days. This problem is actually difficult to solve, and I doubt it has a nice solution, I will share my thoughts on it here to see what we can get.
First, let f(w,g,b) denote how many steps on average it takes to get from a position with w white balls, g green balls, and b black balls to the final position of w+g+b black balls. Now, suppose that half the bag has black balls in it, that means that it is the same as a position with no black balls in it but every step takes twice as long. In mathspeak, I claim that f(w,g,w+g)=2f(w,g,0), similarly, if 2/3 of the balls are black each step will take 3 times as long, and this can be extended into the claim that f(w,g,b)=(w+g+b)/(w+g) f(w,g,0). Its a bit of a trick to prove it, but I assure you that it is true. Now, we know that from the position represented as (w,g,b), we can take three possible paths, giving us the result that
The three terms represent the chance of drawing a white, green, and black ball, respectively. Now, let us denote f(w,g,0) as H(w,g), then by the earlier claim we have f(w,g,b)=(w+g+b)/(w+g)H(w,g), and so, setting b=0 in the previous equation, we find for H, the relation
Alright, now just to find the H that satisfies that recursion relation with the initial condition H(0,0)=0. First, we can try to find H(0,g). It must satisfy
This turns out to be solved by our previous solution of H(0,g)=g Σ 1/i summing i from 1 to g. One can try a similar trick for H(1,g), but the solution gets ugly fast.
This is as much progress as I have made on the solution, I still doubt it has a clean solution at all, but if anybody can get a solution feel free to post it in the comments.
Consider a coin that lands on heads with probability p ∈ [0,1]. How many times on average do you have to flip the coin before it lands on heads?
Naively, one expects the answer to be 1/p (if the coin has 1/3 chance of landing on heads, you expect to need to flip it 3 times). Of course, there is a small chance that you will need 4 flips, or 5 flips, or a billion flips. There is some sort of concern that the infinite sum will ruin things, so lets actually perform the infinite sum. The chance of stopping on exactly the Nth flip is p(1-p)N-1, as (1-p)N-1 is the chance you failed the first N-1 flips, and p is the chance you stopped on the Nth one. Summing to find the expectation value of N, and we will denote 1-p=q and D as derivative with respect to q, so we have
< N > = Σ Np(1-p)N-1 = p Σ NqN-1
= p Σ D(qN) = p D Σ qN = p D(1/(1-q)) = p(1/(1-q)2)
= 1/p
So, we see that the naive expectation is actually correct, still, it is nice to prove it.
Now, moving on with our actual problem, for our strategy to work, we first must have one of the 99 non master prisoners to come in, then we need the master to come in, then one of the 98 remaining, then the master again, and so on down the line. the chance of each of these events is easy to figure out (remember, we are assuming that the warden selects a random prisoner each day). So, for the first few terms, the number of days it takes is 100/99+100+100/98+100+100/97+... since each time the master needs to enter the room, it takes about 100 days for that to happen. The full sum is
100*99+100* Σ 1/N
Where N is summed from 1 to 99. Approximating, that comes out to 9900+100Ln99 ≈ 10359, which is a little over 28 years. It would be nice to see if there is a solution with a smaller expectation number of days, especially since the average number of days it takes for every prisoner to enter the room once is 100Ln100 ≈ 460.
Now, for the real problem we have a bit more of a trick on our hands. For the solution when the prisoners do not know the initial position of the switches, they must have the master enter the room 198 times to count everybody. This means we have a flat out 19800 days on top of how long it takes the non masters to do their stuff. Each prisoner must enter the room twice and then gets ignored. This is equivalent to the following problem:
Consider a bag filled with N white balls. At each step, you select a ball from the bag. If the ball is white, paint it green and return it to the bag. If the ball is green, paint it black and return it to the bag. If the ball is black, return it to the bag. On average, how many steps will it take for the bag to have only black balls left in it?
If we let F(N) denote the solution to that problem, then our prisoners expect to get out in 19800+F(99) days. This problem is actually difficult to solve, and I doubt it has a nice solution, I will share my thoughts on it here to see what we can get.
First, let f(w,g,b) denote how many steps on average it takes to get from a position with w white balls, g green balls, and b black balls to the final position of w+g+b black balls. Now, suppose that half the bag has black balls in it, that means that it is the same as a position with no black balls in it but every step takes twice as long. In mathspeak, I claim that f(w,g,w+g)=2f(w,g,0), similarly, if 2/3 of the balls are black each step will take 3 times as long, and this can be extended into the claim that f(w,g,b)=(w+g+b)/(w+g) f(w,g,0). Its a bit of a trick to prove it, but I assure you that it is true. Now, we know that from the position represented as (w,g,b), we can take three possible paths, giving us the result that
f(w,g,b)=w/(w+g+b) [f(w-1,g+1,b)+1]
+g/(w+g+b) [f(w,g-1,b+1)+1]+b/(w+g+b) [f(w,g,b)+1]
The three terms represent the chance of drawing a white, green, and black ball, respectively. Now, let us denote f(w,g,0) as H(w,g), then by the earlier claim we have f(w,g,b)=(w+g+b)/(w+g)H(w,g), and so, setting b=0 in the previous equation, we find for H, the relation
H(w,g)=w/(w+g) [H(w-1,g+1)+1]+g/(w+g) [f(w,g-1,1)+1]
H(w,g)=w/(w+g)H(w-1,g+1)+g/(w+g-1)H(w,g-1)+1
Alright, now just to find the H that satisfies that recursion relation with the initial condition H(0,0)=0. First, we can try to find H(0,g). It must satisfy
H(0,g)=g/(g-1)H(0,g-1)+1
This turns out to be solved by our previous solution of H(0,g)=g Σ 1/i summing i from 1 to g. One can try a similar trick for H(1,g), but the solution gets ugly fast.
This is as much progress as I have made on the solution, I still doubt it has a clean solution at all, but if anybody can get a solution feel free to post it in the comments.
Not Really A Dilemma
So, I always hate it when people misuse the word dilemma, I mean seriously now, its supposed to be a problem involving two choices. If you don't have exactly two choices its not a dilemma. Naturally, that didn't stop me from breaking this rule when I posted the problem last week and titled it prisoners dilemma. Whatever, anyway, lets have a look at the solution now.
First of all, its important to realize the two switches and the manditory flipping thing is a big ol' red herring. You can just use the switch on the right as a "dummy switch" and the switch on the left as your real switch. You flip the right switch if you are in the room and do not feel like flipping the left switch. So now there is just one switch in the room and flipping it is optional.
Next, the problem is alot easier if we assume that the prisoners know the initial position of the switch. So, let us assume that the switch starts in the up position. The solution is begins by having one person designated to be the "master" who will count off the prisoners by being the only person to flip the switch to up. The strategy for every prisoner who is not the master is:
The strategy for the master is:
So flipping the switch up declares a prisoner to be 'counted', and each prisoner will be counted exactly once. Its interesting to ask how long it takes for this strategy to work assuming the warden picks prisoners at random, I'll get to that next week.
This strategy might even work if you don't know the initial position of the switch (because it might start as up anyway), but if it started as down then the master will count a prisoner that wasn't actually there and the warden (being an adversary) will arrange things so that you lose.
You could try to solve that by having the master count to 100, but then if it had started as up you will never manage to end the strategy, as nobody will ever make the last flip (and you will never be sure it isn't just the warden holding out on you).
So, with an unknown initial switch position it is a bit harder. You can deal with this by counting everybody off twice. Agian, designate a master, the strategy for any prisoner who is not the master is:
So now each prisoner will ask to be counted exactly twice. The strategy for the master is:
Counting to 198 is counting every one of the "non-master" prisoners twice. Now, if the switch started as down, then you counted that once, but that does not matter. All that would mean is that there is a prisoner out there that you only counted once, which is good enough anyway.
Calculating how long this strategy takes is much harder, and I am still working on the solution to that.
First of all, its important to realize the two switches and the manditory flipping thing is a big ol' red herring. You can just use the switch on the right as a "dummy switch" and the switch on the left as your real switch. You flip the right switch if you are in the room and do not feel like flipping the left switch. So now there is just one switch in the room and flipping it is optional.
Next, the problem is alot easier if we assume that the prisoners know the initial position of the switch. So, let us assume that the switch starts in the up position. The solution is begins by having one person designated to be the "master" who will count off the prisoners by being the only person to flip the switch to up. The strategy for every prisoner who is not the master is:
If the switch is down, do nothing.
If the switch is up, then flip it down if you have never flipped it down before. If you have flipped it down before, do nothing.
The strategy for the master is:
If the switch is up, do nothing.
If the switch is down, flip it up.
If you have flipped it up 99 times, declare that all 100 prisoners have been in the room.
So flipping the switch up declares a prisoner to be 'counted', and each prisoner will be counted exactly once. Its interesting to ask how long it takes for this strategy to work assuming the warden picks prisoners at random, I'll get to that next week.
This strategy might even work if you don't know the initial position of the switch (because it might start as up anyway), but if it started as down then the master will count a prisoner that wasn't actually there and the warden (being an adversary) will arrange things so that you lose.
You could try to solve that by having the master count to 100, but then if it had started as up you will never manage to end the strategy, as nobody will ever make the last flip (and you will never be sure it isn't just the warden holding out on you).
So, with an unknown initial switch position it is a bit harder. You can deal with this by counting everybody off twice. Agian, designate a master, the strategy for any prisoner who is not the master is:
If the switch is down, do nothing.
If the switch is up, then flip it down if the number of times you have flipped it down before is one or zero. If you have flipped it down twice before, do nothing.
So now each prisoner will ask to be counted exactly twice. The strategy for the master is:
If the switch is up, do nothing.
If the switch is down, flip it up.
If you have flipped it up 198 times, declare that all 100 prisoners have been in the room.
Counting to 198 is counting every one of the "non-master" prisoners twice. Now, if the switch started as down, then you counted that once, but that does not matter. All that would mean is that there is a prisoner out there that you only counted once, which is good enough anyway.
Calculating how long this strategy takes is much harder, and I am still working on the solution to that.
Prisoners Dilemma
OK, one of these days I'm going to run out of puzzles. As it is, I think I am reaching the point where all my puzzles either are really simple or require the axiom of choice to solve. Anyway, this puzzle for this week is still a good one. I have learned this one many times in different incarnations, but this particular version was told to me by Bart:
Note that the prisoners do not know the initial configuration of the switches, and must always flip exactly one switch when they are in the room (you can make an easier version of this puzzle by modifying these facts). Also note that the warden does not have to place a prisoner in the room each day, so if you are in the room one day and in there again some days later, you do not know how many people have been in the room since. Finally, to make precise the statement that "given enough time, each prisoner will enter the room arbitrarily many times," I mean: For each prisoner P, for each integer N, there exists an integer K such that before day K prisoner P will have visited the room more than N times.
You may assume that the warden is an adversary, capable of meddling with any strategy to maximum effect (up to the rules of the problem). Also, do not worry about the finite lifetimes of the prisoners, that would just make this stupid, I suppose the prisoners are immortal or something.
There is a prison with 100 prisoners and a warden who likes to play bizzare games with them. In this particular game there is a room with two light switches in it. The light switches do not do anything, and can only be in the states up or down. Each day, the warden may select a prisoner and place them in the room. While in the room, the prisoner must flip exactly one of the switches and then is released from the room back to their cell. The prisoners are unable to leave any sort of messages in the room besides the positions of the light switches (the warden will always return the room the its initial state except for the switches).
On any day, any prisoner may declare "we have all been in the room at least once." If this declaration is made and is correct, the prisoners win and will all be released. If the declaration is made and incorrect, the prisoners lose and are killed.
It is promised that given enough time, each prisoner will enter the room arbitrarily many times. The prisoners may plan ahead of time, but then will never get to see eachother again until the game is over. Find a strategy that guarantees the prisoners victory.
Note that the prisoners do not know the initial configuration of the switches, and must always flip exactly one switch when they are in the room (you can make an easier version of this puzzle by modifying these facts). Also note that the warden does not have to place a prisoner in the room each day, so if you are in the room one day and in there again some days later, you do not know how many people have been in the room since. Finally, to make precise the statement that "given enough time, each prisoner will enter the room arbitrarily many times," I mean: For each prisoner P, for each integer N, there exists an integer K such that before day K prisoner P will have visited the room more than N times.
You may assume that the warden is an adversary, capable of meddling with any strategy to maximum effect (up to the rules of the problem). Also, do not worry about the finite lifetimes of the prisoners, that would just make this stupid, I suppose the prisoners are immortal or something.
And We All Go Down Together
OK, I feel like distracting myself from work, so its time to post the full solution to the hats in a room puzzle. You must have already seen the hint I gave, so I will go from there.
The next case to solve is the four person case. The random strategy for that case gives a 1/16 chance of success, and the 'left-right' strategy gives 1/6. Doesn't seem like there is much room to improve, but lets try. First, let us name our people Adam, Betty, Candy, and Dale (I suppose I could give them numbers as names, but the hats will also need to be numbered, and it will make my explanation a bit less transparent). Suppose we plan to have Adam and Betty look under the two hats on the left, and Candy and Dale will look under the two hats to the right. Adam will look under hat 1 first, if he sees his own name, then all is well. If he sees Betty's name in that hat, then we are still OK. However, if he sees either Candy or Dale under that hat, then there is a problem.
If Adam knows that Candy's name is under hat 1, then he knows that the plan is going to fail unless he aborts. Whats more, he knows that the plan will fail anyway unless Candy also aborted. One way that Candy will abort is if she sees Adam's name under hat 3. If Candy sees Adam's name under hat 3, she will know that the default plan is doomed, and must abort. Thus, if Adam sees Candy's name under hat 1, he should look under hat 3 next. Out of some sort of symmetry, he might as well look under hat 4 if he sees Dale's name under hat 1.
At this point you can guess the strategy (actually, lots of people guess this strategy after the hint, but few are able to convince themselves it actually works). Adam will be assigned hat 1, Betty hat 2, Candy hat 3, and Dale hat 4. Look under your own hat, and whatever name you see, look under that persons hat next. What are the odds this works? Its is easy enough just to look at all 24 arrangements of the hats and see. I will denote an arrangement like Adam under hat 1, Dale under hat 2, Candy under hat 3, Betty under hat 4, with the letter sequence ADCB, and write S for success and F for fail.
So, 10 successes out of 24, thats better than the 'left-right' strategy of 6 successes out of 24 (actually, those successes are a subset of these ones). Okay, its not likely that we will do better than that, as its easy to show that no matter what the first person does, he cannot win with more than 1/2 chance, so at best we can approach 12 out of 24. Back to the 100 person case.
Easy enough strategy, does it work? More simply, given the numbers 1 to 100 in a line (an element of the permutation group) what are the odds that there is no cycle of length 51 or more?
Alright, we know that in total there are 100! ways to arrange the numbers 1 to 100, how many of them contain a cycle of length 51 or more? Well, lets assume we wanted to construct a list with a cycle of length n (with n>50), then there are 100Cn ways to choose those elements. Given those n elements to form a cycle, there are (n-1)! ways to arrange them into a cycle (because the first one can link to n-1 others, the second one to n-2 others and so on). Finally the remaining 100-n elements can be arranged (100-n)! ways (note there is no concern of the remaining elements forming a cycle of length n, as n>50).
We can see that the total number of ways to create a list of the numbers 1 to 100 that contains a cycle of length exactly n is:
Well, isn't that nice.
So the probability that there is a cycle of length n is
Where the sum has n going from 51 to 100. The sum can easily be calculated on some math program, or you can approximate is as an integral if you believe that 100 is large enough (it is). Then it is the integral from y to 2y of 1/x dx, which is simply ln(2)≈ 0.69. That is the total probability of failure.
We can see that even in the case that the number of prisoners tends to infinity, the chance of success using this strategy will, at worst, be 1-ln(2)≈ 0.31. Thus they can expect to get out in just over 3 days.
As a side note, what are the odds that the first person expects to find his name when he first enters the room? He will not find his name if it is part of a cycle of length n with n>50. There are 99Cn-1 ways to choose the other n-1 elements, and (n-1)! ways to arrange them into a cycle, and (100-n)! ways to arrange the remaining elements. Thus, we are interested in summing
as n goes from 51 to 100. But that term is exactly 1/100, so after summing we will have 1/2.
As one would expect, the chance of the first person (or any individual, for that matter) finding their own name is 1/2. However, if that person is wrong, then there are at least 50 other people who are wrong with them. This is standard in problems where one person being wrong ruins everything. Make sure that nobody is ever wrong alone, they must take as many people with them as possible.
On the other hand, with problems where you only need one person to be right (such as with some of my earlier hat problems), you need to make sure they are always right alone, so you don't waste any extra "rightness".
The next case to solve is the four person case. The random strategy for that case gives a 1/16 chance of success, and the 'left-right' strategy gives 1/6. Doesn't seem like there is much room to improve, but lets try. First, let us name our people Adam, Betty, Candy, and Dale (I suppose I could give them numbers as names, but the hats will also need to be numbered, and it will make my explanation a bit less transparent). Suppose we plan to have Adam and Betty look under the two hats on the left, and Candy and Dale will look under the two hats to the right. Adam will look under hat 1 first, if he sees his own name, then all is well. If he sees Betty's name in that hat, then we are still OK. However, if he sees either Candy or Dale under that hat, then there is a problem.
If Adam knows that Candy's name is under hat 1, then he knows that the plan is going to fail unless he aborts. Whats more, he knows that the plan will fail anyway unless Candy also aborted. One way that Candy will abort is if she sees Adam's name under hat 3. If Candy sees Adam's name under hat 3, she will know that the default plan is doomed, and must abort. Thus, if Adam sees Candy's name under hat 1, he should look under hat 3 next. Out of some sort of symmetry, he might as well look under hat 4 if he sees Dale's name under hat 1.
At this point you can guess the strategy (actually, lots of people guess this strategy after the hint, but few are able to convince themselves it actually works). Adam will be assigned hat 1, Betty hat 2, Candy hat 3, and Dale hat 4. Look under your own hat, and whatever name you see, look under that persons hat next. What are the odds this works? Its is easy enough just to look at all 24 arrangements of the hats and see. I will denote an arrangement like Adam under hat 1, Dale under hat 2, Candy under hat 3, Betty under hat 4, with the letter sequence ADCB, and write S for success and F for fail.
ABCD - S
ABDC - S
ACBD - S
ACDB - F
ADBC - F
ADCB - S
BACD - S
BADC - S
BCAD - F
BCDA - F
BDAC - F
BDCA - F
CABD - F
CADB - F
CBAD - S
CBDA - F
CDAB - S
CDBA - F
DABC - F
DACB - F
DBAC - F
DBCA - S
DCAB - F
DCBA - S
So, 10 successes out of 24, thats better than the 'left-right' strategy of 6 successes out of 24 (actually, those successes are a subset of these ones). Okay, its not likely that we will do better than that, as its easy to show that no matter what the first person does, he cannot win with more than 1/2 chance, so at best we can approach 12 out of 24. Back to the 100 person case.
With 100 people the strategy generalizes simply, assign each of them a number and have each person look under the hat of their number. Then go to the hat corresponding to the name of the person you saw under that hat, repeat until you either see your own name or you have looked at 50 hats. There is no concern that you get sent back to your first hat, as only seeing your own name can do that.
Easy enough strategy, does it work? More simply, given the numbers 1 to 100 in a line (an element of the permutation group) what are the odds that there is no cycle of length 51 or more?
Alright, we know that in total there are 100! ways to arrange the numbers 1 to 100, how many of them contain a cycle of length 51 or more? Well, lets assume we wanted to construct a list with a cycle of length n (with n>50), then there are 100Cn ways to choose those elements. Given those n elements to form a cycle, there are (n-1)! ways to arrange them into a cycle (because the first one can link to n-1 others, the second one to n-2 others and so on). Finally the remaining 100-n elements can be arranged (100-n)! ways (note there is no concern of the remaining elements forming a cycle of length n, as n>50).
We can see that the total number of ways to create a list of the numbers 1 to 100 that contains a cycle of length exactly n is:
T(n)=100Cn*(n-1)!*(100-n)!
=100!*(n-1)!*(100-n)!/(n!(100-n)!)
=100!/n
Well, isn't that nice.
So the probability that there is a cycle of length n is
Σ T(n)/100!
Where the sum has n going from 51 to 100. The sum can easily be calculated on some math program, or you can approximate is as an integral if you believe that 100 is large enough (it is). Then it is the integral from y to 2y of 1/x dx, which is simply ln(2)≈ 0.69. That is the total probability of failure.
We can see that even in the case that the number of prisoners tends to infinity, the chance of success using this strategy will, at worst, be 1-ln(2)≈ 0.31. Thus they can expect to get out in just over 3 days.
As a side note, what are the odds that the first person expects to find his name when he first enters the room? He will not find his name if it is part of a cycle of length n with n>50. There are 99Cn-1 ways to choose the other n-1 elements, and (n-1)! ways to arrange them into a cycle, and (100-n)! ways to arrange the remaining elements. Thus, we are interested in summing
99Cn-1*(n-1)!*(100-n)!/100!
as n goes from 51 to 100. But that term is exactly 1/100, so after summing we will have 1/2.
As one would expect, the chance of the first person (or any individual, for that matter) finding their own name is 1/2. However, if that person is wrong, then there are at least 50 other people who are wrong with them. This is standard in problems where one person being wrong ruins everything. Make sure that nobody is ever wrong alone, they must take as many people with them as possible.
On the other hand, with problems where you only need one person to be right (such as with some of my earlier hat problems), you need to make sure they are always right alone, so you don't waste any extra "rightness".
Hints In A Room
So as a follow-up to my hats in a room puzzle, I'm going to be doing something unusual this time....I'm going to be giving a hint. This puzzle is particularly difficult, and even with this hint it still is quite a trick. Before giving the hint though, lets go through some of the logic that you have probably already gone through.
First of all, you need to see just how badly the random strategy fails. Each person has a 1/2 chance to select their correct hat if done randomly, so the chance that they all happen to be correct is 1/(2100). Thats pretty bad. OK, next we try to solve the two person case and try to do better than 1/4 that the random strategy gives. Its clearly a waste of time for both people to look under the same hat, so we might as well agree that one person looks in the left one, and the other person in the right one. This gives a 1/2 chance of success, huzzah. Generalizing this back to the 100 person case, if 50 people look in the ones on the left and the other 50 look in the ones on the right, you have a 1/(100C50) chance of success. This is substantially better than 1/(2100), but still nowhere close to being able to get out in a week. This is the best you can do without a key realization.
The realization that you need to come to is that you do not have to choose all of the hats you will look under right away, you can look under some of them and use that information to decide where to go next.
I'll finish the entire solution some time later this week.
First of all, you need to see just how badly the random strategy fails. Each person has a 1/2 chance to select their correct hat if done randomly, so the chance that they all happen to be correct is 1/(2100). Thats pretty bad. OK, next we try to solve the two person case and try to do better than 1/4 that the random strategy gives. Its clearly a waste of time for both people to look under the same hat, so we might as well agree that one person looks in the left one, and the other person in the right one. This gives a 1/2 chance of success, huzzah. Generalizing this back to the 100 person case, if 50 people look in the ones on the left and the other 50 look in the ones on the right, you have a 1/(100C50) chance of success. This is substantially better than 1/(2100), but still nowhere close to being able to get out in a week. This is the best you can do without a key realization.
The realization that you need to come to is that you do not have to choose all of the hats you will look under right away, you can look under some of them and use that information to decide where to go next.
I'll finish the entire solution some time later this week.
Hats In A Room
So, I haven't been in town for a while, I've been away at the go congress. My performance there was average, but I'm happy with the games I played. Anyway, onto the new puzzle. I first learned this one from Bart:
As I understand, Bart first learned this one at a talk entitled "Seven Problems You Swear You've Heard Incorrectly".
There are 100 prisoners in a room (we shall call this room A) and the warden of these prisoners has decided to play a game with them. In another room (room B) there are 100 hats, and each one has the name of one of the prisoners underneath it (each prisoner has a unique name). A prisoner will be selected randomly and sent into room B. While in room B, the prisoner may look underneath 50 of the hats and then will be sent into another room (room C). Room B will then be restored to its initial state before a new prisoner is sent into it.
One by one, each prisoner will have a chance to look underneath 50 hats before being sent into room C. Once they are all in room C, they will all be released if each one of them has looked under the hat that contains their own name. If any of them has not looked under the hat that contains their own name, they will be sent to their cells for another night and the scenario will be run again tomorrow, with the names randomized underneath the hats each time.
The prisoners may plan while in room A. Come up with a strategy that, on average, will set them free in less than a week.
As I understand, Bart first learned this one at a talk entitled "Seven Problems You Swear You've Heard Incorrectly".
Subscribe to:
Posts (Atom)
