Probability and the Prisoner Problem
Date: 07/04/2001 at 22:39:45 From: Nick Martin Subject: Probability and the "Prisoner Problem" Hi. This is a problem that was posed a few months ago at a lecture attended by a friend of mine. The lecturer didn't give the answer; she couldn't work it out and after putting our heads together with several others', we're still coming up empty. Maybe you can help. Sixteen prisoners are assembled and told the following: Each will receive a hat that is either red or blue (the colour is selected randomly and each has a 1/2 probability.) Then, all the prisoners must simultaneously either: - Try to guess the colour of their hats, or - Pass. The prisoners will be set free if - at least one person guesses, AND - nobody guesses wrong. Otherwise, they will be executed. The prisoners may consult beforehand to decide on a strategy, but they will be unable to communicate in any way after the hats are put on; and all must answer simultaneously. Apparently, there exists some strategy that will give the prisoners a probability of survival greater than 90%. We eventually discovered a solution for only three people: each person follows the following strategy: - If both of the other people have the same colour hat, guess the opposite colour. - If the other two people have different-coloured hats, pass. The prisoners will be set free unless they all wear the same colour hat (75%). Attempts to extend this further to more people, however, only lowered the probability, and the best we can do with sixteen people is still 75% (by having thirteen people all pass, and the other three simply follow the above strategy). I've also been told that the situation is "best" when there are (2^n-1) prisoners, but work on a 7-person solution went nowhere either. Help!
Date: 07/10/2001 at 13:18:35 From: Doctor Rick Subject: Re: Probability and the "Prisoner Problem" Hi, Nick, thanks for writing to Ask Dr. Math with a great problem! This is an interesting problem! It is contrary to my (trained) intuition that one can do any better than a 50% probability of surviving. Given that the assignment of hat colors is completely independent, a prisoner's knowledge of other prisoners' hat colors cannot skew the probability of his own hat color away from 1 in 2. Part of the solution must be to explain where my intuition went wrong. I have played with the problem quite a bit in the past 6 days. I haven't reached the end yet, but I have learned a lot. I wrote down my thoughts along the way, so you can see my problem-solving technique, as far as it goes. Considering the scheme you present for 3 prisoners, which gives a 75% probability of survival, we can get a hint as to how the odds can be beaten. Here are the 8 cases, with the guesses each prisoner makes ("-" means pass): R R R B B B (all wrong) R R B - - B (correct) R B R - B - (correct) R B B R - - (correct) B R R B - - (correct) B R B - R - (correct) B B R - - R (correct) B B B R R R (all wrong) We see that a total of 12 guesses are made, and in fact half of them are wrong! There is nothing counterintuitive about the individual guesses. What skews the probability of survival is that all the wrong guesses are concentrated in only 1/4 of the possible states, while the correct guesses are distributed evenly among the remaining states. Let's consider whether we have any hope for a strategy along these lines. What happens when we go to N prisoners? There are 2^N possible states. If we want the wrong guesses to occur in 2^N/10 or fewer states, then there can be at most N*2^N/5 guesses. This is because there are at most N*2^N/10 guesses in the 2^N/10 states, and the number of right guesses will equal the number of wrong guesses. On the other hand, death also follows in a state for which *no* guess is made. Thus we want at least one guess in each state. Thus we have a lower limit on the number of guesses, namely (N+9)*2^N/10: the N*2^N/10 wrong guesses, and one each in the (9/10)*2^N other states. If the total number of guesses is G, then (N+9)*2^N/10 < G < N*2^N/5 There will be numbers in this range if N+9 < 2N Thus, I conclude that, if my scenario for "beating the odds" is the way to go, we can only possibly exceed 90% success if N > 9. Your 75% success is pretty good for only 3 prisoners. And this gives me a little hope that we may actually have a *better* chance the higher the number of prisoners ... if we can come up with a strategy. Let the number of cases in which wrong guesses are made be M. Then each prisoner will make a guess in 2M states. M of these guesses will be correct, and the other M states will differ only by the color of the prisoner's own hat. The M states in which a prisoner makes a correct guess will be different for each prisoner, so that there are NM such states. The total number of states is thus NM+M, or M(N+1). We know there are 2^N states, so that 2^N = M(N+1) We cannot achieve equality in general. We must choose the smallest M greater than 2^N/(N+1) so that all states are covered. N 2^N/(N+1) M ------------------------------ 3 8/4 2 (exact) 4 16/5 = 3.2 4 5 32/6 = 5.3 6 6 64/7 = 9.1 10 7 128/8 = 16 16 (exact) 8 256/9 = 28.4 29 ... 15 32768/16 = 2048 2048 (exact) 16 65536/17 = 3855.1 3856 I'm feeling good about this - the values of N that yield exact matches (so that we might actually have exactly one prisoner guess in each of the NM correct states) are just those that the hint said were best! Now perhaps we can try a particular case - the next "exact" case, N = 7. We want to pick 16 out of the 2^7 = 128 "sacrificial" states, in which all will guess wrong. Each of the other 112 states should differ from one of the 16 in just one hat color. The 16 states must differ from each other in two or more hat colors. I'll start by picking RRRRRRR and BBBBBBB to be two of the 16. No state with exactly one R or one B can then be among the 16. Let's try states that are nearly evenly divided, having 3 or 4 Red hats. How many of these are there? There are 7!/(3! 4!) = 35 states of each type. That's too many. Let's try a set of states that is closed under rotation among the prisoners. Here's what I mean: If the prisoners stand in a circle and their hats are in the set of 16, then if each gave his hat to the prisoner to his left, the set would again be in the set. RRRRRRR and BBBBBBB have this property themselves: if you rotate the state RRRRRRR, you get RRRRRRR again. Any other state is part of a closed set of 7 states, generated by rotating the state successively 6 times. Thus the closed set of 16 states that we need can be formed of RRRRRRR, BBBBBBB, and two 7-member closed sets, such as: RRRRRRR RRBBBBB BBRRRRR BBBBBBB BRRBBBB RBBRRRR BBRRBBB RRBBRRR BBBRRBB RRRBBRR BBBBRRB RRRRBBR BBBBBRR RRRRRBB RBBBBBR BRRRRRB Since none of these states differs from another by only one hat color, this set should work. All we need now is a set of rules such that each prisoner will guess incorrectly in these states. These rules do the trick: If you see all the same color hat, guess the opposite color. If you see only one hat of one color, guess the other color. If you see two hats of the same color together and the rest the other color, guess the same color as the two hats. Take any one prisoner. If the hats are in any of the 12 states listed above, he will guess incorrectly. For each of these states, there is another in which he will make the same guess, but it will be correct; and he will be the only one who guesses, so all will be freed. In the 12 states listed, all 7 prisoners will simultaneously guess wrong, so they will be executed. The deadly states are 16/128 = 1/8 of the states, so with 7 prisoners we have a probability of 7/8 = 87.5% that the prisoners will be freed if they use my strategy. We don't yet have a general strategy that will work with any number of prisoners. Before thinking about "inexact" numbers, let's consider the next "exact" number, N = 15. In this case, M = 2^15/16 = 2^11 = 2048. We need to choose a set of 2048 states that is closed under rotation, so that all 15 prisoners, using the same rules, will guess wrong in these states. This is where I bogged down. I tried endless approaches to identifying subsets of hat states that total 2048, without complete success yet. Here is one approach that came closest so far. What I did with N = 7 was to take the states with 0 red or 0 blue hats, and a subset of the states with 2 red or 2 blue hats. Let's take a look at the numbers of states with K red hats: 0 1 1 15 2 105 3 455 4 1365 5 3003 6 5005 7 6435 8 6435 9 5005 10 3003 11 1365 12 455 13 105 14 15 15 1 ----- 32768 Perhaps we can find a subset of the 3003 states with 5 red hats that will come close in size to the 2048 we need. One way to create subsets while maintaining the closure under rotation is to restrict the pattern of adjacent red hats around the circle. For instance, we could require 2 red hats together, and another 3 red hats together but not adjacent to the two. Place the 10 blue hats in a row, creating 11 sites (between the blue hats and at the ends) where we can put a cluster of red hats. We find the following numbers of states with the possible clustering patterns: 5 R together: P(11,1) = 11 4 + 1: P(11,2) = 110 3 + 2: P(11,2) = 110 3 + 1 + 1: P(11,3)/2 = 495 2 + 2 + 1: P(11,3)/2 = 495 2 + 1 + 1 + 1: P(11,4)/6 = 1320 1 + 1 + 1 + 1 + 1: C(11,5) = 462 ---- 3003 The total is correct, but the subsets need some tweaking. Some of our states have a cluster of red hats at both ends, which (when the prisoners form a circle) will become a single cluster. Thus, some states must be moved up to another subset. We need to move two of the 4+1 states (those with 4 R's at the left and 1 at the right, and vice versa) and two of the 3+2 states up to the 5-R subset, making the 15 states that we knew there should have been. Likewise, we must move - two 3+1+1 states (3-1, 1-3) and one 2+2+1 state (2-2) to the 4+1 subset, - a 3+1+1 state (1-1) and two 2+2+1 states (1-2, 2-1) to the 3+2 subset, - two 2+1+1+1 states (2-1 and 1-2) to the 3+1+1 subset, - one 2+1+1+1 state (1-1) to the 2+2+1 subset, - and one 1+1+1+1+1 state to the 2+1+1+1 subset. Our counts become 5 R together: 11 + 2 + 2 = 15 4 + 1: 110 - 2 + 3 = 111 3 + 2: 110 - 2 + 3 = 111 3 + 1 + 1: 495 - 3 + 2 = 494 2 + 2 + 1: 495 - 3 + 1 = 493 2 + 1 + 1 + 1: 1320 - 3 + 1 = 1318 1 + 1 + 1 + 1 + 1: 462 - 1 = 461 ---- 3003 We can do the same analysis on the sets with other numbers of red hats if necessary. Then we look for a small number of subsets whose counts add to 2048. One solution is 4 red hats 1365 5 R, none together 461 5 R, in two clusters 222 (3+2 or 4+1) ---- 2048 To generate this set of "sacrificial" states, we can write the first rule for those who have a blue hat: If you see 4 red hats, or 5 red hats with no two neighbors having red hats, or 5 red hats in two clusters, then guess that you have a red hat. This guess will be wrong if it is one of the "sacrificial" states listed above. A prisoner who is wearing a red hat must also make a guess. What rule will achieve this? If you see 3 red hats, or 4 red hats that (supposing that you also have a red hat) are all separated by blue hats, or 4 red hats all in a group (not including your neighbors), or 4 red hats in two groups (one of which may include one or both neighbors), then guess that you have a blue hat. What a mess! There must be a better way - can you find one? Before I end this report, let's think a bit about solutions when N is not one less than a power of 2. You came up with a method for these cases: the prisoners select 2^K-1 of their number to do the guessing, based on the hats they see on the others of this same set, while the other N-(2^K-1) prisoners sit it out. Using this method, 16 to 30 prisoners have the same probability of freedom as 15 prisoners, namely 1/16. Is this the best that can be done? Going back to my early calculations, I found that for N = 16, the optimal number of "sacrificial" states M is 3856. The optimal probability is thus 3856/65536 = 0.058838 = 1/16.996. We should be able to do a little better than 1/16. Still, we've done significantly better than 90% success, even with the less-than-optimal solution. I'd like to close this out by finding a really good solution to the puzzle. If you can come up with one, please write back and let us know. Also, the contents of the lecture in which this puzzle was presented might provide a clue to the solution, so perhaps you could let me know more about it. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Date: 07/12/2001 at 09:34:38 From: Doctor Rick Subject: Re: Probability and the "Prisoner Problem" Hi again, Nick. I have more to report on your "Prisoner Problem." Another Math Doctor, finding the problem intriguing, searched the Web to see if it was a hot topic in the math community. Indeed it is! It even made the New York Times science section on April 10, 2001. Here is an article by Todd Ebert of the University of California at Irvine, who says he invented the puzzle. The Colored Hats Puzzle http://www.ics.uci.edu/~ebert/teaching/spring2001/ics151/puzzles.html As it turns out, in order to come up with a truly satisfying and general solution to the problem on my own, I would have had to reinvent a mathematical concept called the Hamming code. This is a technique used to encode data (being transmitted from a space probe to earth, for example) in such a way that an error in a single bit out of N bits can be detected and corrected automatically. Here is an explanation of how a Hamming code works. Error Correction and the Hamming Code (University of New Brunswick) http://www.ee.unb.ca/tervo/ee4253/hamming.htm This page details the (7,4) Hamming code, which uses 7 bits to encode 4 data bits. The other 3 bits are used to determine whether the 7 bits were transmitted correctly, or if not, which of the 7 bits is in error. (If more than one bit is in error, the code will not be corrected correctly.) Out of the 128 possible 7-bit codewords, 16 are valid. Sound familiar? When there are 7 prisoners, the winning strategy is to guess one's hat color such that the hats on all the prisoners' hats (letting red be a 0 bit and blue be a 1 bit) represent a Hamming code with an error. Then if the hats represent a valid Hamming code, all will guess wrong; but if not, then the prisoner corresponding to the erroneous bit will guess correctly. The rule for 7 prisoners thus is (see the link for more details): Put the prisoners in a pre-determined order, 1 to 7. Assume that you have a red hat, and generate a 3-bit binary number as follows: The ones bit is 1 if among prisoners 1, 3, 5, and 7 there is an odd number of blue hats (1). The 2s bits is 1 if among prisoners 2, 3, 6, and 7 there is an odd number of blue hats. The 4s bit is 1 if among prisoners 4, 5, 6, and 7 there is an odd number of blue hats. Generate a second 3-bit number using the same rules but assuming that you have a blue hat. Then look at the two numbers. If neither is zero, PASS. IF one is zero, then that is the valid Hamming code. You want to guess that the code has an error, so guess the hat color that led to the non-zero number. This rule looks much more complicated than my rule for 7 prisoners! The great thing about it is that it is extensible to any number of prisoners of the form 2^k-1. The numbers you generate will have k bits in general. Here are the 16 valid (7,4) Hamming codes -- the hat patterns for which all prisoners guess incorrectly: 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 The bits are numbered 1-7 left to right. The valid codes have an even number of 1's (0 parity) in each of the three groups of bits listed in the rule. The incorrectly guessed codes in my solution, for comparison, look like this: 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 I believe this solution is equally valid; the problem with it is that it is not extensible. It gave me no clue as to how to deal with 15 prisoners. This certainly is a fascinating problem. It starts out looking paradoxical: how can the prisoners possibly do better than 50-50? It ends up teaching us something about a very practical application of mathematics in this information age: error-correcting codes. I hope you will explore this field further! For one thing, I have not touched the question of how to handle the 16 prisoners in your version of the problem. I have ideas, but I'll leave it to you. - Doctor Rick, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.