Associated Topics || Dr. Math Home || Search Dr. Math

### 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;

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

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

(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

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/
```
Associated Topics:
College Probability
High School Calculators, Computers
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search