Author |
Topic: Locker Room Dilemma (Read 7289 times) |
|
inexorable
Full Member
Posts: 211
|
 |
Locker Room Dilemma
« on: Jan 28th, 2006, 6:15am » |
 Quote  Modify
|
Alice, Bob, Charlie, and Diane are prisoners under the supervision of warden Stan. One day the warden takes the ID cards from each prisoner and places them randomly in different lockers in a locker room. The locker room consists of four numbered lockers each with a curtain instead of a door. The curtains are marked 1, 2, 3, and 4. On the next day the prisoners will be taken, one at a time, into the locker room, where they can choose a curtain and look behind it. If they see their own ID card, they are said to be successful. Otherwise, they get to open a second curtain and again, if they see their own ID card, they are successful; otherwise they are failures. As they leave the locker room they cannot communicate with the others. And as they enter the locker room they have no way of telling if a previous prisoner was successful or has looked into any specific locker.
If all four prisoners are successful, then they will all be released; otherwise, back to the cells for everyone.
The prisoners know the protocol and can get together in advance to decide on a strategy. For example, they might decide that each should open two lockers at random. Such a strategy would mean that each prisoner succeeds with probability 1/2, and so the group of four is successful with probability 1/16, or 6.25%. Find a strategy whose probability of success is over 40%.
|
|
 IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Locker Room Dilemma
« Reply #1 on: Jan 28th, 2006, 10:29am » |
Quote Modify
|
First of all, let me write up a strategy with a 0% success rate.
Everybody chooses locker 1 first, then locker 2.
Of course, two of them will win, but the rest will fail. So, they loose.
Please note that the warden knows that the guys would choose the two girls lockers for sure. After all, they're guys, and if they've been in prison for a while, they'd risk anything to look in those lockers. Thus, the warden just switched them.
And, the same goes for the girls. So, he switched the girls locker ID's too...
Easy...
But, what if the warden is just stupid, and didn't think of that? What if the distribution is totally random?
Well... every locker should be chosen twice, max. Because? It's about averages. Hard to explain, I just got this feeling.
Let's just assume, totally for laughs, everybody would pick the same curtain twice... Of course this would have a 1/256th success rate.
So, we're looking for a way, to walk through all 4!
We need to test 4!^3 situations, and note the success rate!
In essence:
First choice: Array(a,b,c,d)
Second choice: Array(e,f,g,h)
Right Answer(i,j,k,l)
Then, for every first,second-combination, look if you'd have succes, with all Richt-combinations... If so, increment the internal success counter with 1. Keep track of the highest success-combo. If the new idea is better, print & store it.
At the end, echo the most succesfull combo, and the success-score.
I'll get coding now 
----
edit: Might I say that you're asking us to do the impossible. Or, am I wrong, like always, and have I made an error in my code 
|
| « Last Edit: Jan 28th, 2006, 11:32am by Sjoerd Job Postmus » |
IP Logged |
|
|
|
ChunkTug
Full Member
Gender: 
Posts: 166
|
|
Re: Locker Room Dilemma
« Reply #2 on: Jan 28th, 2006, 12:56pm » |
Quote Modify
|
As a first guess...
| hidden: | A checks 1, B checks 2, C checks 3, D checks 4.
If you see your card, good. If not go to the locker corresponding to that card. This should prevent anyone two who were incorrect with their first guess ending up at the same locker their second guess.
This will end up in all four being successful 10 out of 24 times. 1 when all four are right on their first guess. 6 when 2 are right on their first guess. 3 when none are right on their first guess, but the cards have been pairwise swapped. |
|
| « Last Edit: Jan 28th, 2006, 6:12pm by ChunkTug » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Locker Room Dilemma
« Reply #3 on: Jan 28th, 2006, 1:35pm » |
Quote Modify
|
on Jan 28th, 2006, 12:56pm, ChunkTug wrote:
| hidden: | | If you see your card, good. If not go to the locker corresponding to that card. |
|
|
Probably that is what was meant. But... the riddle says The curtains are marked 1, 2, 3, and 4. It doesn't say Alice, Bob, Charlie, and Diane... 
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Locker Room Dilemma
« Reply #4 on: Jan 29th, 2006, 12:31am » |
Quote Modify
|
on Jan 28th, 2006, 1:35pm, JocK wrote:| Probably that is what was meant. But... the riddle says The curtains are marked 1, 2, 3, and 4. It doesn't say Alice, Bob, Charlie, and Diane... |
|
Although I'm not a fan of treating people like numbers, maybe, just maybe, beforehand they could choose a number representing each one of them?
Probably best not to choose an obvious alphabetic numbering, as the intentions of this vicious warden are not to be trusted too much.
In the good old days before the existence of pseudo-random generators, we used straws of different lengths which were a great invention...
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Locker Room Dilemma
« Reply #5 on: Jan 29th, 2006, 2:26am » |
Quote Modify
|
on Jan 28th, 2006, 12:56pm, ChunkTug wrote:As a first guess...
| hidden: | A checks 1, B checks 2, C checks 3, D checks 4.
If you see your card, good. If not go to the locker corresponding to that card. |
|
|
Ah, ok... I interpreted this inconsistently.
So, upfront they each get assigned a distinct locker for their initial try, and any person who finds the card of a fellow prisoner on the first try, choses on the second try the locker that was (or will be) checked initially by that very fellow prisoner.
Cute solution ChunkTug.
|
| « Last Edit: Jan 29th, 2006, 2:31am by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: Locker Room Dilemma
« Reply #6 on: Feb 1st, 2006, 3:17am » |
Quote Modify
|
Suppose there are 2k prisoners and each can look into k lockers. what wud be the strategy that is asymptotically positive as k goes to infinity?
|
|
IP Logged |
|
|
|
sideshowmel
Newbie
Gender:
Posts: 3
|
|
Re: Locker Room Dilemma
« Reply #7 on: Apr 28th, 2006, 2:17pm » |
Quote Modify
|
For 2k prisoners we can modify the solution as follows:
| hidden: | | Start at your locker. If you see a card that is not yours, go to the locker corresponding to that card. If that's still not your card, go to the locker corresponding to the new card, and continue this way until you find your card or you run out of chances. |
The probability of success can then be calculated as follows:
| hidden: | The card inside each locker "points" to another locker (or possibly back to itself). Therefore each locker must be part of some "cycle" of lockers, each pointing to another, until the original locker is reached. Our methods merely takes us along the paths of one these cycles, so we will succeed as long as there is no cycle longer than k. Let us count the number of permutations that lead to failure.
Assume there is a cycle larger than k. Let x>k designate the size of this largest cycle. The number of permutations with largest cycle x is given by:
2kCx * (x-1)! *(2k-x)! =(2k)!/x
So the total probability of failure is Sum x=k+12k 1/x
This is the "tail" of the harmonic series, so it's approximated by ln(2k) - ln(k) = ln(2), and the probability of success approaches 1-ln(2), or about .3068. |
|
|
IP Logged |
|
|
|
Trebla
Newbie
Gender:
Posts: 16
|
|
Re: Locker Room Dilemma
« Reply #8 on: May 23rd, 2006, 11:50am » |
Quote Modify
|
I think we have to assume that they go in some determined order (or at least they are able to determine what their location in the order is).
So taking it as A, B, C, D... p(a) = 50% no matter what.
Given that, p(B) * p(C) * p(D) must be >= 80%.
Another note, it's unclear to me if a person takes their ID card with them in the event they are right, I was assuming this was the case. This kind of kills the follow the card theory... C gets in, opens locker 3 and it's empty... well crap, was it A or B that found his card there? No way to tell.
Assuming you leave your card in your locker if you find it, the aforementioned theory gives"
ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA
In which there are 10/24 successful combinations... greater than 40%
Only 2/12 cases where A finds his will the others not find theirs... I had to sketch it out to believe it.
|
|
IP Logged |
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: Locker Room Dilemma
« Reply #9 on: Sep 1st, 2007, 3:04pm » |
Quote Modify
|
The first two look into 1 and 2, the next two look in 3 and 4. 50% success probability.
|
| « Last Edit: Sep 1st, 2007, 3:05pm by srn437 » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Locker Room Dilemma
« Reply #10 on: Sep 2nd, 2007, 7:13am » |
Quote Modify
|
on Sep 1st, 2007, 3:04pm, srn347 wrote:| The first two look into 1 and 2, the next two look in 3 and 4. 50% success probability. |
|
Seems more like ~16%
There's 1/4 chance that the first curtain has ID 1 and then 1/3 chance the second curtain has ID2, which multiplies to 1/12. But you can switch the two ideas around, so that adds to 1/6th chance ~ 16%
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: Locker Room Dilemma
« Reply #11 on: Sep 2nd, 2007, 2:37pm » |
Quote Modify
|
on Sep 2nd, 2007, 7:13am, towr wrote:
Seems more like ~16%
There's 1/4 chance that the first curtain has ID 1 and then 1/3 chance the second curtain has ID2, which multiplies to 1/12. But you can switch the two ideas around, so that adds to 1/6th chance ~ 16% |
|
~16%? You mean slightly more. Approximately 162/3%. So we can clarrify for srn347, this is rounded to 17%. And yes, it goes on forever.
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: Locker Room Dilemma
« Reply #12 on: Sep 2nd, 2007, 3:37pm » |
Quote Modify
|
Oh. Maybe there aren't any.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Locker Room Dilemma
« Reply #13 on: Sep 3rd, 2007, 1:48am » |
Quote Modify
|
on Sep 2nd, 2007, 2:37pm, mikedagr8 wrote:| ~16%? You mean slightly more. |
|
I mean exactly ~16%; i.e. exactly "approximately 16%". Which may be up to 1% more than 16%.
Quote:1/6th is exactly 16 2/3%. To say it is approximately so is slightly misleading.
|
| « Last Edit: Sep 3rd, 2007, 1:49am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: Locker Room Dilemma
« Reply #14 on: Sep 3rd, 2007, 1:52am » |
Quote Modify
|
Quote:| 1/6th is exactly 162/3%. To say it is approximately so is slightly misleading. |
|
Oh, I know it is just that, but we seem to have had a little problem with a certain member not understanding that when a fraction is turned into a decimal, and repitition occurs, you can never get it 100% accurate, so we leave it in the fraction form.
I was just trying to make it easier for their sake.
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
srn437
Newbie
the dark lord rises again....
Posts: 1
|
|
Re: Locker Room Dilemma
« Reply #15 on: Sep 3rd, 2007, 8:47pm » |
Quote Modify
|
Does it matter if its 16% or 50/3%? No. What if a and b choose 1 and 2, c chooses 1 and 3, and 4 chooses 1 and 4?
|
|
IP Logged |
|
|
|
mikedagr8
Uberpuzzler
A rich man is one who is content; not wealthy.
Gender:
Posts: 1105
|
|
Re: Locker Room Dilemma
« Reply #16 on: Sep 4th, 2007, 12:39am » |
Quote Modify
|
on Sep 3rd, 2007, 8:47pm, srn347 wrote:| Does it matter if its 16% or 50/3%? No. What if a and b choose 1 and 2, c chooses 1 and 3, and 4 chooses 1 and 4? |
|
There is a HUGE difference. One is 16%, the other is 16662/3%. Try learning the basics, before you advance.
|
|
IP Logged |
"It's not that I'm correct, it's that you're just not correct, and so; I am right." - M.P.E.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Locker Room Dilemma
« Reply #17 on: Sep 4th, 2007, 1:24am » |
Quote Modify
|
on Sep 3rd, 2007, 8:47pm, srn347 wrote:| What if a and b choose 1 and 2, c chooses 1 and 3, and 4 chooses 1 and 4? |
|
That would work only 2 out of 24 times. There is no point in c and d picking 1, when a and b pick from 1 and 2 (because if either of a and b is wrong, they all lose anyway)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Locker Room Dilemma
« Reply #18 on: Oct 15th, 2012, 5:03am » |
Quote Modify
|
on Sep 4th, 2007, 12:39am, mikedagr8 wrote:
There is a HUGE difference. One is 16%, the other is 16662/3%. Try learning the basics, before you advance. |
|
>>Thread Necromancy!<<
That depends whether you interpret (50/3) as a number then stick a percent-sign on the end, or interpret it as a ratio and apply a to-percentage operator to convert it to a percentage.
If you type {5}{0}{/}{3}{%} into a calculator, you may well get "1666.6667" as the answer. As a mathematician, I have no problem accepting 50/3 as the precise magnitude of a percentage.
I'm also less than thrilled by people sticking fractions as superscripts when they don't mean to raise something to a fractional power - to me, 16662/3 looks like ~140.535 rather than ~1666.6667
Ultimately, what matters is that others can follow your notation - provided what you intend is clear, how you express it is irrelevant.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print