CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content |Store| Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "another question about prisonners"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #641
Reading Topic #641
iliaden
Member since Aug-14-05
Sep-29-05, 10:02 PM (EST)
Click to EMail iliaden Click to send private message to iliaden Click to view user profileClick to add this user to your buddy list  
"another question about prisonners"
 
   I found another problem about prisoners.

10 people are placed in a row, so that every one sees everyone who is in front of him (the second one sees only the first; the 10th sees everybody). A hat, either white or black, is placed randomly on the head of each prisoner, so nobody can see his own. In order, starting with the last one, each prisonner is given the chance to guess the color of his hat. If (s)he guesses correctly, (s)he is set free. If not, (s)he is killed. The goal is to save as many prisonners as possible.

I have a solution, that is quite simple:
The 10th prisonner names the color of the 9th prisoner's hat. He has 50% chance of survival, but the 9th has a 100% probability of survival. Then, the 8th prisonner names the hat of the 7th. Again, he has 50% chance of staying alive, but the next one has a 100% probability of survival. Follow the same pattern for the 6th and 5th prisonners; 4th and 3rd; and 2nd and 1st prisonners. Using this solution, 5 prisonners stay alive no matter what, and 5 others have 50% of chance of survival.

I believe that it is possible to keep the 9 first (or last) prisonners alive no matter what, and the 10th would have 50%, because he can't recieve any data from behind.

Please help!


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Sep-30-05, 06:30 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
1. "RE: another question about prisonners"
In response to message #0
 
   >
>I believe that it is possible to keep the 9 first (or last)
>prisonners alive no matter what, and the 10th would have
>50%, because he can't recieve any data from behind.
>
>Please help!

I think I see a way to do this. The key is to pass as much information as possible forward, and the problem is that in your solution, only half of the prisoners pass information forward. The hard part is that the prisoners seem to have a choice: pass information forward OR save themselves. But it is possible to do both! The method makes use of "white hat parity," i.e., the oddness or evenness of the number of white hats.

Let prisoner number 10 say "white" if he sees an odd number of white hats, otherwise he says "black". Then he has a 1/2 chance of going free. Then prisoner 9 counts the white hats he sees in front of him, and if he agrees with prisoner 10 about the parity, he knows his must be black, so he says "black," otherwise he says "white." But this not only saves prisoner 9, it also tells prisoner 8 what to expect: Since 8 heard what 9 and 10 said, he knows what parity 10 saw, and also knows whether 9 saw the same. Therefore he knows what parity to expect, and just as before, if he counts the white hats he sees and comes up with the same parity as 9 did, he knows his hat is black, otherwise it is white. This clearly works for all the prisoners.

A simple way to state this rule is: Every prisoner starts by predicting even parity, and switches this predicted parity every time he hears the word "white." He then counts the white hats he can see to find his observed parity. If it agrees with the prediction, he says "black," otherwise he says "white."

There is of course no way to guarantee saving prisoner 10, but all others can be guaranteed saved by this method. Thanks for an interesting puzzle.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
sfwc
Member since Jun-19-03
Oct-01-05, 07:23 AM (EST)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
2. "RE: another question about prisonners"
In response to message #1
 
   A minor generalisation; suppose that instead of being coloured black or white the hats were coloured with the seven colours of the rainbow. Same problem.

Thankyou

sfwc
<><


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Oct-03-05, 06:23 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
3. "RE: another question about prisonners"
In response to message #2
 
   This does make it considerably harder in the sense that each prisoner needs much more information, yet also it becomes easier in the sense that with 7 color names, each prisoner can also pass on much more information. As before, parity is the way to go, I think, because each prisoner only needs to make a binary decision for each of the colors. Therefore, passing forward parity information for each color will solve the problem.

Seven colors is almost enough to pass forward 3-bit parity, but not quite. A simple scheme to pass 2-bit parity forward would be to number the colors ROYGBIV = 0123456, think of the numbers expressed as binary digits, and let the first prisoner call out a number that encodes the parity of R and O, so the guess would mean:

R = 000 --> R even, O even
O = 001 --> R odd, O even
Y = 010 --> R even, O odd
G = 011 --> R odd, O odd
B = 100 --> R even, O even
I = 101 --> R odd, O even
V = 110 --> R even, O odd

The last 3 are redundant, so one could set up an interpretation under which ROY indicate that Y is even and BIV indicate that Y is odd parity. G cannot be used to tell the parity of Y, because there is no possibility of sending the message 111, so the highest bit of G cannot convey any information. In this way, the first prisoner would convey the parity of R and O every time, and in 3/4 of cases (assuming a random distribution of hat colors) would also convey the parity of Y. One could say, in a probabilistic sense, that he passes 2.75 parity bits forward.

What does the next prisoner do? He counts the hats he sees, and if he notices a difference from one of the conveyed parities, he knows his hat is what made the difference, so that is his color. He states his color, and all further prisoners update their knowledge of the parity of that color. The prisoners continue in this way until it happens that a prisoner does not note any parity differences. In that case, he must have a hat color for which parity information is not yet available, so he is in the same position as the first prisoner.

There is one difference: he knows he does not have one of the colors with parity information, so he is not going to guess one of those unless he is very altruistic, because he would forfeit his own chance at freedom. There is nothing he can do to improve his own chances, but he can again guess a color that will encode the parity of the next 2 hat colors, by naming one of the remaining 5 (or, 3/4 of the time, 4) hat colors. The other prisoners further along the line know the list of colors that have defined parities, so as soon as they hear this prisoner state a color name that is not on the list, they know that new information is coming, and they know how to interpret it:

If 4 colors remain,

G = 000 --> G even, B even
B = 001 --> G odd, B even
I = 010 --> G even, B odd
V = 011 --> G odd, B odd ;

while if 5 colors remain,

Y = 000 --> Y even, G even, B even
G = 001 --> Y odd, G odd
B = 010 --> Y even, G even
I = 011 --> Y odd, G even
V = 100 --> Y even, G odd, B odd .

Therefore, this prisoner can pass on 2 (or, 1/4 of the time, 3) bit parity. At this point, either there are 2 colors left without parities, I and V, which happens (3/4)*1 + (1/4)*(1/4) = 13/16 of the time; or else there are 3 colors left without parities, B, I, and V, which happens of course 3/16 of the time.

The next unlucky prisoner who doesn't note a parity difference has either 2 or 3 hat colors to work with. The case of 2 colors is just the original problem at the start of this thread, and the solution there is clearly just a special case of this solution: if the prisoner sees an even number of I=indigo hats, he calls out "indigo." Note that it is not necessary to encode parity for the last color, V=violet, because at this point, if a prisoner does not detect any parity differences in ROYGBI, the color of his hat must not be on that list, so it must be V. Prisoners further along the line do not need to update their parity lists when they hear "violet" for this reason, so V is treated just like "black" in the original problem.

If there are still 3 colors, the prisoner can say:

B = 00 --> B even, I even
I = 01 --> B odd
V = 10 --> B even, I odd,

which will define the parity of B and 1/2 of the time also the parity of I. The remaining 1/2 of the time, one more prisoner will be unlucky and have to determine the parity of I.

I have deliberately gone into lots of detail here, to illustrate the process. The summary answer is this:

If there are n hats without parity yet assigned, number them 0 through n-1, and encode parities for the next m hats by the digits of a binary number c, and call out the color with number c. What is m? Let k = integer part of log_2(n), and let l = n - 2^k. Then m is either k or k+1, depending on whether the bit pattern differing from that of c in just the highest bit also occurs among the binary numbers from 0 to n-1. If it does, then m=k+1 because an additional parity bit can be passed. This will happen in l cases out of 2^k. (Note: the ability to pass information in the highest bit is conditioned on the pattern of the lower bits, so the probability is NOT 2l/n. We are not looking at the whole bit pattern; the probability question is: for a given pattern of lower bits, are there or are there not two different high bits in our number list? There are exactly l bit patterns for which this is true.)

All prisoners further down the line can therefore deduce both which parities have been defined thus far, and what those parities are. If a prisoner detects no difference between the parities he deduces from the previous prisoners' choices, he uses the method above to choose a hat color. If he does detect a difference, the parity that differs is his hat color, and he calls it out.

Some notes about assumptions:

1) I have assumed that no prisoner will willingly sacrifice himself, but is happy to pass on as much information as he can. If the first few prisoners are willing to sacrifice themselves, then there is a simpler strategy: for n hat colors, the first prisoners each encode k parities until all but one color has a parity, then all prisoners just look for parity changes. This will sacrifice 1 + integer part of n/k prisoners with probability (n-1)/n, which gives an expected number of int((n+k)/k)*(n-1)/n, which for large n is roughly n/k.

2) In the actual strategy, the expected number of prisoners lost is harder to compute in general, because the formula is recursive. In each particular case, however, it is easy to calculate: Assume all 7 colors actually occur. Then one can make a decision tree, where the nodes are the number of hats without parity yet, parentheses are probabilities that that prisoner will be lost, and branches are labeled with probabilities of reducing the parity that much:


7 (6/7)
/ \
1/4 / \ 3/4
/ \
/ \
/ \
5 (4/5) 4 (3/4)
/ \ /
/ \ /
3/4 / \ / 1
/ 1/4 \ /
/ \ /
(2/3) 3 --------- 2 (1/2)
\ 1/2 /
\ /
1/2 \ / 1
\ /
\ /
1 (0)


In this case, the expected number lost is
6/7 + 1/4*4/5 + 3/4*3/4 + 1/4*3/4*2/3 + 1/4*1/4*1/2 + 3/4*1*1/2 = 2.151. Those lost are only among the unlucky prisoners who do not see parity differences; all other prisoners are saved. It'should be clear that the number of unlucky prisoners is roughly log_2(n), each of whom has a probability of being lost which is less than 1 (in fact it is 1- 1/(current number of hats without parities)). This gives an approximate upper bound of log_2(n) on the number of prisoners lost, independent of the total number of prisoners.

Well, I must say that this was considerably more elaborate than the first solution. I do not know whether this is optimal in terms of number of prisoners saved, but it must be pretty close, since it passes the maximum amount of information forward (or at any rate, the maximum amount that I can see how to pass).

--Stuart Anderson



  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
sfwc
Member since Jun-19-03
Oct-05-05, 04:37 PM (EST)
Click to EMail sfwc Click to send private message to sfwc Click to view user profileClick to add this user to your buddy list  
4. "RE: another question about prisonners"
In response to message #3
 
   >Well, I must say that this was considerably more elaborate
>than the first solution. I do not know whether this is
>optimal in terms of number of prisoners saved, but it must
>be pretty close, since it passes the maximum amount of
>information forward (or at any rate, the maximum amount that
>I can see how to pass).
It is indeed a formidable strategy. Nevertheless, it is not optimal. In fact, the optimal solution is rather simpler. Happy hunting.

Thankyou

sfwc
<><


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Oct-06-05, 10:10 AM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
5. "RE: another question about prisonners"
In response to message #4
 
   >It is indeed a formidable strategy. Nevertheless, it is not
>optimal. In fact, the optimal solution is rather simpler.
>Happy hunting.

Yes, now I see it. This is a fine example of what happens when I get fixated on a particular feature of the original solution (parity) and try to generalize the solution based on that feature. A better approach would have been to rethink ALL of my assumptions and try to find the proper generalization of the original solution. Of course it is a truism that there are many ways to generalize any particular concept; the trick is to find the most felicitous one.

In this case, counting "white hat parity" can be thought of as assigning a value of 1 to white hats and 0 to black hats, then counting the white hats modulo2. The proper generalization is obvious when the original solution is described in this way: Simply assign values 0 through 6 to the hats, and sum the values modulo 7.

The first prisoner does this with no outside knowledge, so he has a 1/7 chance of going free. After prisoner 1 is gone, focus on only the set of remaining prisoners. Each succeeding prisoner sums (modulo 7) the values of all the colors he SEES together with all the colors he HEARS. This accounts for all the hats except his own. Subtracting this modulo 7 from the value stated by prisoner 1 gives the value of the current prisoner's hat.

This is pretty clearly optimal, since every prisoner except the first is saved, and the first has only a 6/7 chance of being lost. I think I would have solved this faster if I had started with the 7 color problem instead of trying to work up to it from the 2 hat problem.

Thank you for yet another interesting puzzle.

--Stuart Anderson


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK