wu :: forums
wu :: forums - Locker Room Dilemma

Welcome, Guest. Please Login or Register.
Sep 18th, 2018, 8:19am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, Eigenray, Grimbal, towr, Icarus, SMQ, william wu)
   Locker Room Dilemma
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Locker Room Dilemma  (Read 6516 times)
inexorable
Full Member
***





   


Posts: 211
Locker Room Dilemma  
« on: Jan 28th, 2006, 6:15am »
Quote Quote Modify 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 Quote Modify 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 Tongue
----
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 Wink
« Last Edit: Jan 28th, 2006, 11:32am by Sjoerd Job Postmus » IP Logged
ChunkTug
Full Member
***






   


Gender: male
Posts: 166
Re: Locker Room Dilemma  
« Reply #2 on: Jan 28th, 2006, 12:56pm »
Quote Quote Modify 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: male
Posts: 877
Re: Locker Room Dilemma  
« Reply #3 on: Jan 28th, 2006, 1:35pm »
Quote Quote Modify 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...  Huh
 
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 Quote Modify 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...  Huh

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: male
Posts: 877
Re: Locker Room Dilemma  
« Reply #5 on: Jan 29th, 2006, 2:26am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 3
Re: Locker Room Dilemma  
« Reply #7 on: Apr 28th, 2006, 2:17pm »
Quote Quote Modify 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: male
Posts: 16
Re: Locker Room Dilemma  
« Reply #8 on: May 23rd, 2006, 11:50am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13638
Re: Locker Room Dilemma  
« Reply #10 on: Sep 2nd, 2007, 7:13am »
Quote Quote Modify 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: male
Posts: 1105
Re: Locker Room Dilemma  
« Reply #11 on: Sep 2nd, 2007, 2:37pm »
Quote Quote Modify 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 Quote Modify Modify

Oh. Maybe there aren't any.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13638
Re: Locker Room Dilemma  
« Reply #13 on: Sep 3rd, 2007, 1:48am »
Quote Quote Modify 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%. Wink
Quote:
Approximately 162/3%.
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: male
Posts: 1105
Re: Locker Room Dilemma  
« Reply #14 on: Sep 3rd, 2007, 1:52am »
Quote Quote Modify 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. Wink
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 Quote Modify 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: male
Posts: 1105
Re: Locker Room Dilemma  
« Reply #16 on: Sep 4th, 2007, 12:39am »
Quote Quote Modify 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: male
Posts: 13638
Re: Locker Room Dilemma  
« Reply #17 on: Sep 4th, 2007, 1:24am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Locker Room Dilemma  
« Reply #18 on: Oct 15th, 2012, 5:03am »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board