What follows is a puzzle. It has an elegant solution that is not too difficult to find, but it is not immediately obvious why the solution is correct. Here we go:
There is a group of 100 people, whom we will call seekers. Each seeker has a wallet, which they give to the Wallet Master. The Wallet Master goes to a room which we will call the locker room, which happens to have 100 lockers in it, and puts one wallet in each locker. He chooses the order at random. The 100 people gather in a waiting area adjoining the locker room. One at a time, the Master admits them to the locker room, where they can look inside up to 50 lockers. Once the seeker is finished, the Master escorts him to a third room and admits the next person. The seekers are not allowed to change the state of the wallets or otherwise pass information to those who have not yet entered the locker room. The seekers are allowed to confer before the wallets are taken in order to devise a strategy that maximizes the likelyhood that every seeker finds his own wallet. What is the optimal strategy and what is the probability of success?
[ June 02, 2005, 10:34 PM: Message edited by: Mike ]
Posted by dean (Member # 167) on :
Are the lockers left open when a person finds and takes his own wallet?
Posted by Xavier (Member # 405) on :
I was thinking that too dean, but then I figured that ANYTHING which gives the next person a clue to what lockers were looked in would fall under the "The seekers are not allowed to change the state of the wallets or otherwise pass information to those who have not yet entered the locker room." clause.
Posted by Mike (Member # 55) on :
The lockers are not left open (this would be a way of passing information to subsequent seekers, which is not allowed). Also, when a person finds his wallet he leaves it there untouched. After all, the presence of that wallet might be useful to the seekers who come after.
[Edit: Xavier is correct.]
Posted by aspectre (Member # 2222) on :
100%. Stuff the WalletMaster into a locker before he grabs the wallets.
Posted by Mike (Member # 55) on :
After he grabs the wallets, actually. That way you know where to look.
But, I'm sure you know that that's not what I had in mind. Posted by punwit (Member # 6388) on :
Do the seekers have to verify to the WalletMaster that they have found their wallet before admittance to the third room?
Posted by advice for robots (Member # 2544) on :
I would imagine if the seekers paired up into 50 pairs beforehand, each pair could check all 100 lockers and find each other's wallets, and then compare notes afterwards.
Posted by punwit (Member # 6388) on :
If they don't have to claim a wallet until the exercise is complete I'd suggest that they look in the locker that corresponds to their place in line. Ascertain whose wallet is in that locker and exchange info in the third room.
Posted by Papa Moose (Member # 1992) on :
How about the first seeker takes really careful note of the wallet in the first locker. Then the second seeker takes really careful note of the wallet in the second locker. On through to 100. Once they're all in room #3, they in turn describe the wallet that was in their locker, and the seeker who recognizes it as his own takes note of the locker number. When done, each of the 100 seekers knows where his wallet is. Success rate is 100%.
[Edit -- dangit, punwit!]
Posted by Mike (Member # 55) on :
The seekers must actually open the locker (as one of their allotted 50) that contains their wallet. So, effectively yes, they have to verify with the Wallet Master before admittance to the third room.
Posted by Mike (Member # 55) on :
Papa: as part of the strategy, to make things easier, they can arrange to clearly label all the wallets. Say, by number, 1 to 100.
Posted by Papa Moose (Member # 1992) on :
In that case I'm curious as to how you get anything other than 50%. Unless....
They make a list that is kept in the first room. When a person goes in, they check lockers at a predetermined rate (one per minute, for example). If the seeker finds his wallet, then he spends less time before the Wallet Master comes back to room #1, so the remaining seekers can calculate, based on time spent, which locker held the previous seeker's wallet. The next seeker knows to skip the indicated locker(s).
I don't feel like taking the time to figure out what the success rate becomes, but it should be an improvement over 50%.
--Pop
Posted by punwit (Member # 6388) on :
Well you beat me that time, Pop. I was gonna suggest some sort of time lapse scenario.
Posted by Mike (Member # 55) on :
Random guessing would actually be much, much less than 50%. It'd be 1/2^100. Best case is just over 25%, IIRC.
Timing tricks like that count as passing information, so are not allowed. That said, the Wallet Master is a wily fellow, and resourceful. Good at evesdropping, too. He can easily take precautions against such a strategy.
Posted by punwit (Member # 6388) on :
What if the first one in looks until he finds the number 1 wallet, the second looks until he finds the number 2 wallet. This should provide clues for those who hold those numbers. I'm also not sure of the success ratio.
Posted by Strider (Member # 1807) on :
if each person must verify with the wallet master that they have infact located their own wallet, and they can only open up to 50 lockers, then isn't there a very strong likelyhood that any individual person will not be able to find his or her wallet.
No matter what kind of plan is created, the first person who walks into that room only has a 50/50 chance of finding his wallet. And I can't seem to think of a way for anyone to do any better.
Posted by Mike (Member # 55) on :
Nevertheless, such a way exists. Here's one thing you might not have taken into account: there is no reason the seeker must decide all at once which lockers to open.
And with that, I'm heading home. Will check back later. Posted by Papa Moose (Member # 1992) on :
Yeah -- without any communication, the chances don't change from 50% for each person. I think whatever method you're using to achieve 25% does pass information in some manner (or calculates the probabilities wrong).
Posted by Papa Moose (Member # 1992) on :
If the order of wallets is random, I still think that makes no difference, Mike.
Posted by Mike (Member # 55) on :
Nope, no tricks, no incorrect calculations. No information passing (person to person) is necessary. Using the information you gain by looking inside lockers, however, is vital. And I really am leaving now. Posted by Strider (Member # 1807) on :
well, the only thing i can think of is that you're hinting that the distribution of wallets is not entirely random. and that by opening up a few lockers and keeping track of which numbered wallets are inside you could develop some sort of method to determine where other wallets are located, i.e.-certain number will not be close to other numbers, etc...
But since you stated originally that all the wallets are randomly distributed, I don't see how this is possible.
Posted by punwit (Member # 6388) on :
He's indicating a plan by the seekers to check certain lockers based on the #'s found on the wallets. I'm not sure how that helps but I'll keep grinding at it.
Posted by Papa Moose (Member # 1992) on :
Ok, I can see this increasing odds, but not by all that much necessarily.
You start with the locker of your wallet number. If your wallet is there, you're done. If not, you open the locker whose number is on the wallet you just saw. Continue until you find your wallet or hit 50 turns.
Through the random placement of the wallets, there's a chance that at least one wallet will be in its own locker -- possibly more. This removes those from the lockers anyone else would open. Also, there's probably a reasonable chance that smaller "circles" are created, and if one of those circles is fewer than 50 in length, then everyone in the circle finds his own wallet. Of course, any circle over 50 guarantees that nobody in that circle will find his own. But based on the random assortment, the chances that no circle of more than 50 numbers is created must be around 25% based on Mike saying that's the best case -- but I ain't checking it.
Posted by Strider (Member # 1807) on :
if they're truly randomly distributed, it wouldn't help at all. Unless i'm misunderstanding the nature of randomness.
Posted by punwit (Member # 6388) on :
I'm not sure how this would increase the odds but if the first seeker checked the first locker, looked at the number on the wallet and then went to the corresponding locker and checked that number... The second seeker went to the second locker and looked at the number on that wallet... and so on.... Would that increase the odds?
edit,You beat me again, Pop
Posted by Papa Moose (Member # 1992) on :
Yeah -- you might be. But like I said, I'm not calculating it.
It's like the fact that if you have 30 people in a room, chances are that two of them have the same birthday, even though 30 is less than 10% of 365 (or 366).
I could probably figure out what exactly the chances are, but I really don't feel like doing the math.
--Pop
Posted by Mike (Member # 55) on :
Ding ding ding! And Papa Moose finds the correct strategy!
To get an intuitive idea on how this increases the odds, try it with only 4 seekers, each allowed to look at two lockers. There are only 24 possible arrangements of wallets in the lockers, each equally likely, so it is each to check. All four should find their wallets 41 and 2/3 percent of the time.
It is harder to get an exact number for 100 seekers. This page gives some formulas that should be helpful. The basic idea of why it works is this: the location of the wallets defines a permutation. Permutations can be expressed as a product of cyclic permutations (where, for example, 4 is mapped to 7 is mapped to 3 is mapped to 4, for a cycle of length 3). If the permutation defined by the location of the wallets has no cycles longer than 50, which turns out to be not unlikely, then everyone finds his wallet.
Posted by Mike (Member # 55) on :
Of course, the Wallet Master knows that the seekers will be employing this strategy, so he may arrange the wallets such that there are cycles longer than 50. Or he would if I didn't say earlier that he chooses randomly. Suppose he does, though. Can anyone give me a way to get around that?
-----
quote:Originally posted by punwit: I'm not sure how this would increase the odds but if the first seeker checked the first locker, looked at the number on the wallet and then went to the corresponding locker and checked that number... The second seeker went to the second locker and looked at the number on that wallet... and so on.... Would that increase the odds?
edit,You beat me again, Pop
Hmm. I think this actually doesn't increase the odds for any individual seeker, which is one of the weird things about the strategy. Instead, it makes it more likely that they all succeed or that a large number (at least 51) fail. It is impossible, for example, for only 1 seeker to fail, or only 50.
Posted by Mike (Member # 55) on :
Here's another one. And we'll raise the stakes a little bit, too.
This time we have n prisoners. The prison guards line the prisoners up and give each one a hat, which is colored either red or blue. The prisoners are facing along the line so that each one can see the colors of the hats in front of him, but not the color of his own hat nor the colors of the hats behind him. Starting at the back of the line, each prisoner guesses the color of his hat out loud. Once all prisoners have guessed, those who guessed correctly are set free and those who guessed incorrectly are executed.
The prisoners are allowed to confer ahead of time to decide on a strategy. What strategy maximizes the guaranteed number of prisoners freed?
Posted by ketchupqueen (Member # 6877) on :
Do we know how many of the hats are red and how many blue? Are they half and half?
Posted by Boris (Member # 6935) on :
"Everyone just say ,'Blue'"
Or there's always the prison communication system. If the person in front of you must answer and the hat is red, you must belch.
Posted by Mike (Member # 55) on :
The guards can arrange things however they want. They could flip a coin for each prisoner, for example. Or they could decide to give everyone a red hat. Which they probably would do if they overheard Boris's suggestion and they were feeling particularly sadistic that day. So, you have to consider the worst-case scenario and minimize the executions in that case.
[Edit for Boris's edit: good thought. Cheating, though. The guards are listening in, and will shoot at the first sign of belching. ]
Posted by ketchupqueen (Member # 6877) on :
The "everyone say blue" won't work very well if there are only 3 blue hats. That's why I asked about numbers.
Posted by Xavier (Member # 405) on :
Without thinking too hard about this, what if the person in back of the line picks the color which is the most present in front of him. That would work pretty well I think. Plus if there is an even amount of people ahead of you, you know that you will live if you pick what the guy behind you did.
There's a flaw here though. Its a decent solution, but I don't think its the best one.
Posted by Xavier (Member # 405) on :
The "everyone say this color" is pretty crappy. n/2 with an average distribution.
Posted by Dagonee (Member # 5818) on :
If the distribution of colors is known, then the last one counts everyone in front and knows his own color exactly. If everyone keeps count, they'll know everyone has gotten it right. 100% will live.
If the distribution is not known, then the one in back says the color of the guy in front. Then that guy says his own color (the color just said). The third guy says the color of the guy in front, and the fourth says the color he just discovered. Half the prisoners live automatically. The other half live half the time (the chance of two hats in a row being the same are 50/50).
So n/2 * 1 + n/2 * .5 = 75% will be expected to live.
Posted by Enigmatic (Member # 7785) on :
The best strategy in both of these situations is to develop clairvoyance before the start of the excercise.
Or to not keep any money in your wallet, so you can just leave without wasting all your time waiting in line.
Or to not get arrested.
--Enigmatic (has all the answers)
Posted by Dan_raven (Member # 3383) on :
Easy. Every other prisoner says the color of the hat in front of him.
They have a 50/50 chance of being right and the person in front of them have a 100% chance of being right.
Should have 75% of the prisoners go free.
Posted by Mike (Member # 55) on :
Nice. That guarantees (n - 1)/2 (n odd) or n/2 (n even). But you can do better. Posted by Dagonee (Member # 5818) on :
Who was that "nice" aimed at, Mike?
And Dan: Too late Posted by Mike (Member # 55) on :
Dan, good thought. Guaranteed minimum is still 50%, though. You can do better.
Edit: I am slow at posting, clearly. Our best strategy still has worst-case around 50%. Not good enough. What if you were one of those prisoners? Posted by Xavier (Member # 405) on :
Okay, I think that's where I was going with mine... But what about the every other guy? Can we figure out how that guy has a better chance of living? Perhaps he says the color which is the most present in front of him? For uneven distributions, I think he will live much more. I think I will program this actually...
Posted by Dagonee (Member # 5818) on :
Oh, sure. Compliment Mr. Danny Come Lately.
Do we know the distribution or not?
Posted by Xavier (Member # 405) on :
I am more shooting for the strategy to have most people live on average. Not the minimum. Its fun thinking about both however.
Posted by Mike (Member # 55) on :
You guys are too fast, dammit!
Dag, no we don't know the distribution, see my post above about flipping coins or choosing all red.
Xavier, you can actually guarantee n - 1 live. So screw the averages. Posted by Astaril (Member # 7440) on :
Man, I need to type faster. I just came up with the 75% solution too, but it took me 10 minutes to type out and now I'm 3rd in line with it! Well, back to thinking...
Posted by Dagonee (Member # 5818) on :
OK, first person counts number of blue hats. If it's even, he says red. If it's odd he says blue.
Next person counts blue hats. If his hat is blue, then the odd/even will have switched. If not, then it will be the same. So he knows his color.
Since we know the second guy got it right, everyone else should be able to do the same thing. But it's a lot to keep track of - I doubt it could be done correctly for even 10 prisoners in practice. And if only one person screws up, he and everyone after him dies.
I was trying a prime factorization thingy and realized all you needed was to factor by 2.
Edit: minimum success is n-1, and I think the first guy has a 50% chance.
Posted by Papa Moose (Member # 1992) on :
The first person's guess is based on whether or not there are an even or odd number of blue hats. If there are an even number of blue hats in front of him, he guesses blue, otherwise red. Every person in front of him can accurately determine the color of his own hat.
I can edit in the manner in which this is done, but I want to post the answer.
Edit -- Because otherwise Dagonee will beat me to it.
Edit 2 -- I want it known that I thought of my answer (the even/odd part) pretty much immediately, but I spent too much time actually reading the thread before posting my answer. Nonetheless, Dag gets credit. *sigh*
Posted by kojabu (Member # 8042) on :
man I used to know the answer to this.
Posted by Dagonee (Member # 5818) on :
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.
Posted by Bob_Scopatz (Member # 1227) on :
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...
AAAAAAAAaaaaaaaaaahhhhhhhhhh...
Posted by Dagonee (Member # 5818) on :
Are these African or European prisoners?
Posted by Mike (Member # 55) on :
Dag is correct! (You are too, Pop.)
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?
[Edit: Bob: ]
Posted by Bob_Scopatz (Member # 1227) on :
I don't know.
AAAAAAAAaaaaaaaahhhhhh....
I have a question, if the distribution is 98% red hats, how does the Dag/Moose method work?
Posted by Boris (Member # 6935) on :
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 Posted by Mike (Member # 55) on :
I appreciate your out of the box thinking, Boris. It means I have to come up with clever guards. Posted by Dagonee (Member # 5818) on :
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.
Posted by Bob_Scopatz (Member # 1227) on :
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.
Posted by Astaril (Member # 7440) on :
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.
Posted by Boris (Member # 6935) on :
I think they're in a straight line. No eye contact is possible.
edit: Hey, cool. This is my Christopher Columbus post (#1492)
edit 2: Boris = stupid. Didn't see the new puzzle Posted by kojabu (Member # 8042) on :
in the new one they're in a circle
Posted by Astaril (Member # 7440) on :
Oh.
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...
Posted by Bob_Scopatz (Member # 1227) on :
Dag...Oh...never mind. I wasn't thinking.
Posted by Mike (Member # 55) on :
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.
Posted by Boris (Member # 6935) on :
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 Posted by Boris (Member # 6935) on :
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 Posted by kojabu (Member # 8042) on :
No winks on the side? I'm sure that could get by the guards.
Posted by Mike (Member # 55) on :
[edit: This was to Boris] No problem. At least I didn't try explaining recursion in lambda calculus to you.
Posted by Mike (Member # 55) on :
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.
Posted by Astaril (Member # 7440) on :
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.
Posted by Mike (Member # 55) on :
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.
Posted by Papa Moose (Member # 1992) on :
I can guarantee 33 survivors. Is it possible to do better than that?
Posted by kaioshin00 (Member # 3740) on :
34 survivors?
Posted by Papa Moose (Member # 1992) on :
Follow along, kaio. If you can guarantee 34 (or more) survivors in the above scenario, say so.
Posted by Boris (Member # 6935) on :
I can guarantee that these guards are really just sadistic jerks.
Posted by Shigosei (Member # 3831) on :
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.
Posted by Shigosei (Member # 3831) on :
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%.
Posted by Shigosei (Member # 3831) on :
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.
Posted by Mike (Member # 55) on :
Consider the case where n = 2. Can you guarantee that one of the prisoners lives?
Posted by Dagonee (Member # 5818) on :
No, you can't, not if no information can be transmitted and the selection must be simultaneous.
If you see red, it tells you nothing about your hat. There's no other information to be had.
Posted by Mike (Member # 55) on :
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.
Posted by Dagonee (Member # 5818) on :
Not if they can't convey information.
There are four possibilities:
1-R, 2-R 1-B, 2-B 1-R, 2-B 1-B, 2-R
For any given value of 2, there are an equal number of values possible for 1. You have no other information.
Posted by Mike (Member # 55) on :
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.
Posted by kojabu (Member # 8042) on :
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?
Posted by Sean (Member # 689) on :
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...
Posted by Mike (Member # 55) on :
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.
Posted by kojabu (Member # 8042) on :
Ahhh I forgot that little part.
Posted by Mike (Member # 55) on :
Sean is correct!
Now, can you prove that this is the best you can guarantee?
![[Wink]](wink.gif)
![[No No]](graemlins/nono.gif)
![[Wave]](graemlins/wave.gif)
![[Smile]](smile.gif)
![[Razz]](tongue.gif)
]
![[Mad]](mad.gif)
![[ROFL]](graemlins/rofl.gif)
]
![[Big Grin]](biggrin.gif)