```Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-07 20:53:08

Here's a nifty little math problem to start off the new year.

A friendly jail warden is in charge of 3 prisoners with life sentences.
Wanting to do them a favor, he decides to give them a chance to be
released.  For each of the 3 prisoners, he randomly selects one mug-shot
from the prisoner's file; each photograph is either a PROFILE (side view)
shot or a FRONT shot, with equal probability.  He calls in each of the 3
prisoners, one at a time, and shows each of them the selected mug-shots of
the OTHER 2 prisoners, but not his own.  The prisoner may then either:

1) guess whether his own mug-shot is a profile shot or a front shot, OR
2) pass (if he doesn't wish to guess).

Everyone goes free if at least one prisoner guesses right and no one
guessed wrong.  (Equivalentally, all the prisoners stay imprisoned if
anyone guessed wrong, or if no one guesses at all.)

The prisoners may discuss ahead of time what strategy they should use, but
once a prisoner has seen the mug-shots and made his guess (or passed), he
is not permitted to communicate with anyone else.

What strategy should the 3 prisoners adopt to maximize their chances of
going free?

Part 2: Would the prisoners' chances of going free increase, decrease, or
stay the same if there were 7 prisoners instead of 3?

Enjoy!

Author: ioconnor ()
Date: 2004-Jan-07 21:37:21

Do the other prisoners hear the pas/mug/profile answer? In otherwords if
prisoner one said "pass" do the other two prisoners hear him say "pass"?

Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-07 22:17:28

The other prisoners do not see/hear any other guesses.  Each of them is
completely ignorant of what the other prisoners have done.

Author: geekbot (Brian Pan)
Date: 2004-Jan-07 22:40:49

Don't tell us the answer yet, I'm thinking out loud. :)

Since seeing the other two pictures doesn't help you guess, and there's no
way to pass information after seeing the pictures.  My guess at the answer
is to dedicate one prisiner as the guesser and the other two pass.  The
guesser will have a 50% chance of setting them free.  I can't think of a
way to increase the odds better than 50%.

-geek

Author: lukas (lukas)
Date: 2004-Jan-07 23:03:48

I agree with geek.  The only way I can see to make the odds better than 50%
is for the prisoners to figure out a way to cheat.
If the probability of getting a front or side view on the mug shot is
equal, and if that probability is independent for each prisoner, then
geek's strategy which gives a 50% chance is works the same for 3, 7, or 500
prisoners.

Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-07 23:16:45

Hint:  Contrary to intuition, it is indeed possible to get a
better-than-50% chance of being freed, without resorting to cheating.

Author: ioconnor ()
Date: 2004-Jan-07 23:23:52

Got it. The three prisoners have a 75% chance of going free.

Hee are the possible scenarios, labeled 'M' for Mug shot and 'P' for
profile shot.

1) M, M, M
2) M, M, P
3) M, P, M
4) M, P, P
5) P, M, M
6) P, M, P
7) P, P, M
8) P, P, P

And the strategy is the first guy will guess if he sees the other two have
both Mug or Profile shots. He'll choose the same profile for himself as he
sees the other two have. He has a 50% chance if he chooses and rules out
conditions 1, 4, 5, & 8.

If he doesn't guess then prisoner two knows only the following conditions
exist.
2) M, M, P
3) M, P, M
6) P, M, P
7) P, P, M
and if he sees two faces with the same shot he'll choose the opposite for
himself. He has a 100% chance of getting it right if he picks.

If the third person is asked he knows he has either condition 2 or 7.
2) M, M, P
7) P, P, M

So he chooses just the opposite of what he sees and has a 100% chance.

There were only two scenarios where there was a risk for prisoner 1. So the
odds are 6/8 or 75% they get to go free from the bum charge white police
officers put them in jail with for a phony crime and a false witness!

Author: ioconnor ()
Date: 2004-Jan-07 23:56:17

I'll leave the 2nd part as an exercise for somebody else. It seems to be
pretty straight forward though.

Author: geekbot (Brian Pan)
Date: 2004-Jan-08 00:04:46

ioconner, the prisoners don't have the ability of hearing whether or not
the previous prisoners pass or not.  In addition, if the 1st guy gets it
right, but then the 2nd or 3rd guy gets it wrong, they still return to
prison.

Author: ioconnor ()
Date: 2004-Jan-08 00:26:19

It depends I suppose on how you read it. I read it that they are set free
if the first person guesses right and if he guesses wrong they don't get a
chance. The only time they get a chance is if he passes. And if he passes
then they know by the fact they are asked to guess that he passed.

The author needs to clarify this.

Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-08 00:43:25

Sorry if I didn't make it clear, but neither the 2nd nor the 3rd prisoners
know whether the previous prisoners have guessed or passed.  All 3
prisoners are asked to guess or pass, no matter what the previous prisoners
have done.  So your solution isn't quite right.

Author: ioconnor ()
Date: 2004-Jan-08 01:10:43

Is this a trick question based on how one reads the question?

If not and there is no information passed between the prisoners and they
all must be asked then it wouldn't make any sense for more than one to
guess. It wouldn't matter how many prisoners are asked either. They would
all have had to agree to pass except for one. And that one person would
have a 50% chance.

Looking at the other two photos doesn't tell him anything about his photo.
And showing the other prisoners photos doesn't impact him at all.

Yet you say he has a better than 50% chance. How can this be?

Author: bob (Bob)
Date: 2004-Jan-08 02:14:15

One prisoner guesses and the other 2 pass for the 50%.

Afterwards, if they failed they snitch on the guard's criminal behaviour
i.e. conspiracy to effect an unlawful release. Their sentences are reduced
for good behaviour. This increases the probability that one or more of them
will come to the end of their sentences - which are probably relatively
short after all, since the guard wouldn't be likely to be friendly with
serious criminals - and be freed ;^)

Bob (sdf-eu)

Author: tomc (Tom Carmichael)
Date: 2004-Jan-08 16:19:28

There is a solution which works for 75% of the cases with no communication
required.

If the prisoners agree to pass if they see mixed pictures and guess the
other viewpoint (front or profile) if they see 2 of the same picture, they
will succeed any time all 3 pictures are not the same.

FFF - all guess profile and lose
FFP - pass, pass, profile
FPF - pass, profile, pass
FPP - front, pass, pass

etc.

If they have 7 prisoners, the situation is more complicated.  There are
many combinations which would never have any of the prisoners seeing a
universal viewpoint.  I don't have a solution to that piece yet.

Tom

Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-08 17:14:01

Tom's solution is the correct one for 3 prisoners.  They have a 75% chance
of being freed using that strategy.  (The other "solutions", while clever,
go beyond the bounds permitted by the original problem.)

I'll let people stew about the 7-prisoner case for a few more days before
posting an answer.  Since it's fairly complicated if you don't know the
general theory, I'll consider it solved if someone tells me what the
chances of survival are, with some basic reasoning as to why this might be
the case.

Mike

Author: tomc (Tom Carmichael)
Date: 2004-Jan-08 18:12:11

Actually, I worked on this a bit more over lunch and have a stab at a
guess:  65.625%.

The strategy goes as follows:

For the 7 prisoner problem, each prisoner sees 6 pictures.  The strategy is
to pass if the division of the pictures are odd numbers, and to pick the
small group if it they are even numbers.  This will succeed whenever the
original picture group is divided 4-3 (70/128 cases) or 6-1 (14/128 cases),
for a total of 84/128 cases or 65.625%.

Going into a bit more detail:

If the pictures are divided 4-3, then each prisoner will see either 3 and 3
or 4 and 2.  If they see 3-3, they won't know which group to guess.  So you
leave it to the 4-2 group.  This gives you 70/128.

If the pictures are divided 5-2, then because you are using the above
strategy, the people who see 4-2 will be wrong.

If the pictures are divided 6-1, you will never see either 3-3 or 4-2, but
rather either 5-1 or 6-0.  As per the 3 prisoner problem, you guess when
you see that all the pictures are the same, giving you these 14/128 cases.

If the pictures are divided 7-0, everyone will see 6-0 and be wrong.

Tom

Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-08 19:23:17

Tom, your approach for 7 prisoners is quite ingenious; however, it's
possible to do better yet.  As a hint, it's possible to do better than the
3-prisoner case, but the prisoners have to take into account not only the
number of F/P photos they see, but also WHOSE photos are F/P.

Author: tomc (Tom Carmichael)
Date: 2004-Jan-08 20:20:56

Can it safely be assumed that all 7 prisoners are interviewed in separate
rooms simulataneously?  (Assuming that a prisoner's picture always has the
same orientation for each showing.)  Or is time / the sequential nature of
revealing the photos essential to the solution?

Assuming everything is simultaneous, it's hard for me to see how individual
selections for individual prisoners can make a difference, but I'll ponder
more.  :-)

Tom

Author: ioconnor ()
Date: 2004-Jan-08 20:34:32

Well, I suppose the minimum is just one if you are lucky?

Two weighings if you aren't feeling lucky and want to be sure?!

I like this. I think I got it right. (Unfortunately I think I always get
them right only to be corrected later.)

The two weighing solution is too easy so I'll leave it to somebody else to
put that answer down. However if there is a 100% solution in just one
weighing let me know so I'll think about it some more before admitting
defeat.

Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-08 21:30:02

Yes, you can assume that all 7 prisoners are interviewed in separate rooms
simulataneously (with the same photos in each room).

Since the 7-prisoner case is quite complicated, I'll post another hint.

Shown below is a set of 16 binary 7-tuples, with the property that every
vector differs from every other vector in at least 3 positions.  (I won't
bother to prove this, but if you're interested, a google search on "Hamming
codes" will yield plenty of information on constructing such codes and
using them to detect and correct errors.)

0000000         0001110         0010101         0011011
0100011         0101101         0110110         0111000
1000111         1001001         1010010         1011100
1100100         1101010         1110001         1111111

The optimal solution for 7 prisoners makes use of such a list.

I'll post the solution in about 24 hours unless someone else beats me to
it.

Author: migo (Mikhael Goikhman)
Date: 2004-Jan-09 11:57:36

Michael, this is a really nice mathematical problem. Surprisingly, I
attended today our local Perl Monger lecture "String matching algorithms:
edit distance" that is pretty much in the spirit of the Hamming codes. :)

The prisoners' chances of going free in the case of 7 prisoners may be
as good as 7/8 = 0.875.

Let's mark FRONT photo to be "1" and PROFILE photo to be "0". Then for
example, 1010101 is one of the possible combination, of course there are
exactly 2^7 = 128 possible combination.

Now, any arbitrary 7 digit binary number is either (1) or (2):

(1) One of the 16 Hamming codes posted by Michael in the previous
message, like 0010101, with the probablity of 16/128 = 1/8.
(2) A non Hamming code. It should be of the distance 1 with one of the
Hamming codes. For example, if we take 1010101 then there is exactly
one Hamming code 0010101, so that the distance between these numbers
is one binary switch. The probability of this case is: 1 - 1/8 = 7/8.

The strategy that the prisoners should use is simple:

* A prisoner sees 6 photos (6 bits), he knows that his own missing bit
may be either 0 or 1. If the prisoner may construct the Hamming code,
then he does not construct it, he guesses the opposite bit.
* Otherwise (i.e. there are 2 possible ways to construct Hamming codes
by switching exactly one known bit and trying one or another own bit)
the prisoner passes.

In the case (1) above, the required number is 0% guessed, all 7 prisoners
guess it incorrectly. In case (2) above, only one of the prisoner makes
a guess and he does it correctly. To make it more visual:

(1) 1/8, Hamming code, for example: 0010101

X010101      (0010101)      guesses 1010101 incorrectly
0X10101      (0010101)      guesses 0110101 incorrectly
00X0101      (0010101)      guesses 0000101 incorrectly
001X101      (0010101)      guesses 0011101 incorrectly
0010X01      (0010101)      guesses 0010001 incorrectly
00101X1      (0010101)      guesses 0010111 incorrectly
001010X      (0010101)      guesses 0010100 incorrectly

(2) 7/8, non Hamming code, for example: 1010101

X010101      (0010101)      guesses 1010101 correctly
1X10101  (0010101 1110001)  passes
10X0101  (0010101 1000111)  passes
101X101  (0010101 1011100)  passes
1010X01  (0010101 1110001)  passes
10101X1  (0010101 1000111)  passes
101010X  (0010101 1011100)  passes

With this strategy, the probability of the correct guess is 7/8.

In the general case, if there are N prisoners, their chances of going free
may be as good as N/N+1. I.e. 99 prisoners are almost certainly free with
only one percent of failure. :) But, hey, they should be really super hyper
hard core geniuses to construct and manipulate 99-digit Hamming codes! :-)

my intuition was correct, the optimum for N-digit Hamming codes is with
N = 2^K - 1.  So, 63 super geniuses compose a more optimal problem than 99.

Author: tomc (Tom Carmichael)
Date: 2004-Jan-09 14:42:52

Just for completeness, I thought I'd throw out there a bit more about my
previous answer.  It occured to me that the prisoners can always trivially
achieve 75% simply by designating 3 specific individuals to be their
'sample group', then using the 3 prisoner strategy listed above.  So 65.625
was wrong for any number of reasons, even if it was a pretty answer.

Now if you change the conditions such that all the prisoners who were in
the smaller group (Front or Profile) needed to state such (rather than just
1 of them), my solution might be right.  ;-)

Tom

Author: bandsmer (Michael Bandsmer)
Date: 2004-Jan-09 20:57:13

Your solution is correct, Mikhael.  For n = 2^r-1 prisoners, the chances of
being freed are
1 - 1/2^r
using the Hamming-code technique, which is optimal.  (The prisoners don't
have to be super geniuses if someone shows them how to calculate the
so-called "syndrome vector", which quickly tells whether or not the
observed bits can be part of a codeword.)

For n not of the form 2^r-1, the prisoners could use Tom's approach: they
could take a subset of 2^s-1 < n prisoners and use a Hamming code of length
2^s-1.  E.g. with 5 prisoners, the first 3 prisoners could use the
3-prisoner technique for a 75% chance of freedom, with the 4th and 5th
prisoners passing.  I don't know whether this technique is always
optimal--perhaps someone can prove it or find a counterexample?
```