posted
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 ]
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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.
Posts: 5656 | Registered: Oct 1999
| IP: Logged |
posted
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.]
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
Do the seekers have to verify to the WalletMaster that they have found their wallet before admittance to the third room?
Posts: 2022 | Registered: Mar 2004
| IP: Logged |
posted
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.
Posts: 5957 | Registered: Oct 2001
| IP: Logged |
posted
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.
Posts: 2022 | Registered: Mar 2004
| IP: Logged |
posted
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%.
posted
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.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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%.
posted
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.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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.
Posts: 2022 | Registered: Mar 2004
| IP: Logged |
posted
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.
Posts: 8741 | Registered: Apr 2001
| IP: Logged |
posted
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. Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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).
Posts: 6213 | Registered: May 2001
| IP: Logged |
posted
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. Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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.
Posts: 8741 | Registered: Apr 2001
| IP: Logged |
posted
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.
Posts: 2022 | Registered: Mar 2004
| IP: Logged |
posted
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.
Posts: 6213 | Registered: May 2001
| IP: Logged |
posted
if they're truly randomly distributed, it wouldn't help at all. Unless i'm misunderstanding the nature of randomness.
Posts: 8741 | Registered: Apr 2001
| IP: Logged |
posted
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
Posts: 2022 | Registered: Mar 2004
| IP: Logged |
posted
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.
posted
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.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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.
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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?
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
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.
Posts: 3003 | Registered: Oct 2004
| IP: Logged |
posted
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. ]
Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
The "everyone say blue" won't work very well if there are only 3 blue hats. That's why I asked about numbers.
Posts: 21182 | Registered: Sep 2004
| IP: Logged |
posted
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.
Posts: 5656 | Registered: Oct 1999
| IP: Logged |
posted
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.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
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? Posts: 1810 | Registered: Jan 1999
| IP: Logged |
posted
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...
Posts: 5656 | Registered: Oct 1999
| IP: Logged |
posted
I am more shooting for the strategy to have most people live on average. Not the minimum. Its fun thinking about both however.
Posts: 5656 | Registered: Oct 1999
| IP: Logged |
posted
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...
Posts: 624 | Registered: Mar 2005
| IP: Logged |
posted
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.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
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*
Posts: 6213 | Registered: May 2001
| IP: Logged |
Printer-friendly view of this topic
![[Wink]](wink.gif)
![[No No]](graemlins/nono.gif)
![[Wave]](graemlins/wave.gif)
![[Smile]](smile.gif)
![[Razz]](tongue.gif)
]
![[Mad]](mad.gif)
