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! :-) I had some suspicion about 99-digit Hamming codes, so I googled this and 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 Wow. Now that's an answer! 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?