posted
I googled it to confirm - we're correct, Pops.
The reason it works is that everyone has access to the information in front of them. This method provides the second person with the one bit of information he doesn't have.
The first guy kind of gets it in the shorts, though.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
Each prisoner says "<red or blue -- the color of the hat of the prisoner in front of him>" then "no, I meant <red or blue -- the color that the guy behind him said first>"
And the only ones who die are those who are thrown off the bridge...
OK, here's puzzle number three (after this one I'll have to search for more, but this one's harder, so it might take longer).
Another group of n prisoners, each with a red or blue hat, same deal as before. This time the prisoners are arranged in a circle, so each one can see the other hats, but not his own. At a signal from the guards, each prisoner simultaneously guesses the color of his own hat. Again, correct guesses go free, incorrect ones are executed.
The prisoners can naturally devise a strategy beforehand, but this time the guards are paying attention, so we can expect the worst-case scenario for any given strategy. Which strategy maximizes the guaranteed number of survivors?
posted
The coin flipping thing throws something of a monkey wrench into things, since the last person in the line could go first, and the first person could then go next. In reality (as this puzzle is obviously not a real part of) the prisoners would ultimately devise a method for undetectable communication, as I suggested earlier (belching was a suggestion). Such a method would ensure the survival of all prisoners. But since we're talking problem solving here...I guess my "out of the box" thinking isn't welcome
Anyway. I always come up with off the wall answers for these questions, so I'm going to leave it up to the statistic lovers here
Edit: HA! I didn't understand the solution that was given. Call me stupid, please Posts: 3003 | Registered: Oct 2004
| IP: Logged |
posted
I appreciate your out of the box thinking, Boris. It means I have to come up with clever guards. Posts: 1810 | Registered: Jan 1999
| IP: Logged |
quote:if the distribution is 98% red hats, how does the Dag/Moose method work?
OK, say there are 98 red and 2 blue.
If the first guy to speak sees 1 blue, he'll say blue.
The next guy either sees 1 or 0 blue. If zero, there's an even number. He knows it was odd. So his must have been a blue. So he says "blue" and lives. The next guy would know that the man behind him had a blue had, so his must be red (else the first guy would have told him there was an even number of blue to start).
Same way works in reverse.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
I think the prisoners could guarantee living out the day by calling their lawyers and having CNN do an expose on cruel and unusual punishment. Blue and red hats indeed! It's bad enough with the orange jump suits...
Alternatively, they could overpower the guards and shove those nasty hats down their throats.
Posts: 22497 | Registered: Sep 2000
| IP: Logged |
posted
Hmm. Everybody could agree to only make eye contact with someone with a red hat. So look around the circle and if no one is looking back at you, you're blue. Or unpopular.
Posts: 624 | Registered: Mar 2005
| IP: Logged |
quote:Another group of n prisoners, each with a red or blue hat, same deal as before. This time the prisoners are arranged in a circle, so each one can see the other hats, but not his own.
Can't they all see each other? Am I reading this wrong? Or did you think I meant for the 2nd puzzle? Maybe I'm confused...
Posts: 624 | Registered: Mar 2005
| IP: Logged |
posted
Yes, they can all see each other. But, no communication, except for you out-of-box thinkers. If you insist on that, I'll have the guards put you in solitary.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
I think these guards need to be more creative. Really, how easy is it going to be to process n prisoners all saying something at the same time Posts: 3003 | Registered: Oct 2004
| IP: Logged |
posted
Okay, serious answer time. Probably wrong, but heck. This is the kind of thing that requires multiple case solutions. Example, assuming that the numbers are not exactly equal, it is possible to say that the prisoners should say the color that is most common. At a minimum, that gives 50% However, if the number of hats of each color is...umm...Okay. My brain just died. Thanks a lot Mike Posts: 3003 | Registered: Oct 2004
| IP: Logged |
posted
[edit: This was to Boris] No problem. At least I didn't try explaining recursion in lambda calculus to you.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
OK, that's it, kojabu! Into solitary with you!
The rules have just changed: the guards put each prisoner into a special cell. These cells open out into a circular room, and there is a small one-way mirror in the door of each cell. This way the prisoners can see into the center room and all the doors except their own. Then the guards nail the hats to the doors above the one-way mirrors. No signals, dammit!
Oh, and the prisoners write down their answers. Assuming they can write, of course.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
Dangit! There goes my other solution. I was going to have them say "Rue" if the hat to their right was blue, and "bled" if red. They'd have to re-do the test because they wouldn't know what they'd each said. It's like that mysterious TF letter on true-false quizzes that always pops up. Works every time.
Posts: 624 | Registered: Mar 2005
| IP: Logged |
posted
Oh, right, to answer Boris's serious proposal: suppose there are 8 prisoners and an equal number of red and blue hats. That would be a pretty poor worst-case scenario.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
Follow along, kaio. If you can guarantee 34 (or more) survivors in the above scenario, say so.
Posts: 6213 | Registered: May 2001
| IP: Logged |
posted
Unless there is a foolproof way of saving greater than 50% of the prisoners, the guards must arrange the prisoners in a particular way to avoid the 50% release rate due to what I will call the majority solution (guess whichever hat is more common). Let's say the prisoners have agreed to implement the majority solution, unless certain conditions are met.
Okay, so there's either an even number or an odd number of prisoners.
Case 1: N is odd. In order to prevent the majority solution, the hats must be nearly evenly divided. N/2 plus or minus .5, to be exact. In this case, if the prisoners have decided on the majority solution ahead of time, all of the minority prisoners will die. The majority prisoners will see equal numbers of colors, and will have to go with a different plan. The question is, how many majority prisoners could be saved at this point?
Case 2: N is even. To prevent the majority solution, the number of hats must be exactly evenly divided. N/2 in either case. Presumably, if N is even, the prisoners will have decided ahead of time that if they see N/2 of one kind of hat and N/2-1 of a different kind, then they will not implement the majority solution. At this point, it is still theoretically possible to save all of the prisoners.
Phase II: The prisoners could then look at pairs of hats across from each other. If the majority are same-color pairs, guess the color across from you. However, it is possible for the guards to have the same number of same-color and opposite-color pairs, and in fact the guards will be forced to do this in order to prevent the phase II majority solution.
Phase III: Next the prisoners can decide based on the color of the hat to the left. There are N-2 visible possibilities; either the hat is the same as the one on its left, or it is different from the one on its left. If most of the hats are the same as the color on their left, pick the same as the color on your left. Now, if the hats are set up going RR BB RR BB and so on, the prisoners will see the same number of same and opposite pairs. However, if the number of prisoners is divisible by 4, as this pattern requires, the Phase II solution would have worked. Additionally, the prisoners could be ordered in an alternating pattern, which would cause them all to make the incorrect choice -- but then Phase II would have worked, since everyone would be across from the opposite color. It's possible that there's another way to arrange the hats to make sufficient numbers guess incorrectly, but right now I'm not awake enough to figure that out. Therefore, I think if there's an even number of prisoners, at least 50% can save themselves.
I don't think I'm up to working out the odd number case.
Posts: 3546 | Registered: Jul 2002
| IP: Logged |
posted
Actually, I just realized that the guards could set up the even solution a little differently. They could have B = R + 2. Guaranteed to kill almost 50% of the prisoners, and then it would be difficult for the majority (not knowing whether it's a B = R or a B = R + 2 scenario) to all guess correctly.
Therefore, the best situation for the guards if N is even is probably to set up the B = R + 2 scenario. Most likely, only half the majority prisoners will be guanteed to live, making the guaranteed survival rate only about 25%.
Posts: 3546 | Registered: Jul 2002
| IP: Logged |
posted
Except what I plan to do is tap once on my neighbor's cell if his hat is blue and twice if it's red. Surely the guards can't watch *everyone* while they're in solitary.
Posts: 3546 | Registered: Jul 2002
| IP: Logged |
posted
You might not be able to guarantee that prisoner A lives, but you can guarantee that if prisoner A dies then prisoner B lives, and vice versa.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
For any given value of 2, there are an equal number of values possible for 1. You have no other information.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
And yet there exists a strategy such that no matter which of those four possibilities occurs, either prisoner A guesses right or prisoner B does. Here's a hint: the two prisoners don't use the same algorithm. And another hint: the strategy also guarantees that one of the prisoners is executed.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
If there are two prisoners and one of them says the color of the other guys hat. He has a 50/50 chance of being right and the other guy will be right.
So with the circle, do they say these outloud or is it still written?
Posts: 2867 | Registered: May 2005
| IP: Logged |
posted
OK so person A says colour(B) and person B says not(colour(A)). Then A lives if colour(A) = colour(B) and B lives if not(colour(A)) = colour(B), and exactly one of those has to be true. That boosts the minimum to 50% on an even number people if they pair up or just under for odd...
Posts: 148 | Registered: Feb 2000
| IP: Logged |
posted
kojabu, I'm not sure I follow. The answers are given simultaneously. So it doesn't matter whether they say them out loud or write them down. We're looking for a strategy that doesn't rely on communication between prisoners.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
Printer-friendly view of this topic
![[ROFL]](graemlins/rofl.gif)
]
![[Razz]](tongue.gif)
![[Smile]](smile.gif)
![[Big Grin]](biggrin.gif)
![[Mad]](mad.gif)
![[Wink]](wink.gif)
