Author 
Topic: Locker Room Dilemma (Read 6531 times) 

inexorable
Full Member
Posts: 211


Locker Room Dilemma
« on: Jan 28^{th}, 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 28^{th}, 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,secondcombination, look if you'd have succes, with all Richtcombinations... If so, increment the internal success counter with 1. Keep track of the highest successcombo. If the new idea is better, print & store it. At the end, echo the most succesfull combo, and the successscore. 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 28^{th}, 2006, 11:32am by Sjoerd Job Postmus » 
IP Logged 



ChunkTug
Full Member
Gender:
Posts: 166


Re: Locker Room Dilemma
« Reply #2 on: Jan 28^{th}, 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 28^{th}, 2006, 6:12pm by ChunkTug » 
IP Logged 



JocK
Uberpuzzler
Gender:
Posts: 877


Re: Locker Room Dilemma
« Reply #3 on: Jan 28^{th}, 2006, 1:35pm » 
Quote Modify

on Jan 28^{th}, 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.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



JohanC
Senior Riddler
Posts: 460


Re: Locker Room Dilemma
« Reply #4 on: Jan 29^{th}, 2006, 12:31am » 
Quote Modify

on Jan 28^{th}, 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 pseudorandom 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 29^{th}, 2006, 2:26am » 
Quote Modify

on Jan 28^{th}, 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 29^{th}, 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.
x^{y}  y = x^{5}  y^{4}  y^{3} = 20; x>0, y>0.



inexorable
Full Member
Posts: 211


Re: Locker Room Dilemma
« Reply #6 on: Feb 1^{st}, 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 28^{th}, 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: _{2k}C_{x} * (x1)! *(2kx)! =(2k)!/x So the total probability of failure is Sum _{x=k+1}^{2k} 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 1ln(2), or about .3068. 


IP Logged 



Trebla
Newbie
Gender:
Posts: 16


Re: Locker Room Dilemma
« Reply #8 on: May 23^{rd}, 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 1^{st}, 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 1^{st}, 2007, 3:05pm by srn437 » 
IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13650


Re: Locker Room Dilemma
« Reply #10 on: Sep 2^{nd}, 2007, 7:13am » 
Quote Modify

on Sep 1^{st}, 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 2^{nd}, 2007, 2:37pm » 
Quote Modify

on Sep 2^{nd}, 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 16^{2/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 2^{nd}, 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: 13650


Re: Locker Room Dilemma
« Reply #13 on: Sep 3^{rd}, 2007, 1:48am » 
Quote Modify

on Sep 2^{nd}, 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 3^{rd}, 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 3^{rd}, 2007, 1:52am » 
Quote Modify

Quote:1/6th is exactly 16^{2/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 3^{rd}, 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 4^{th}, 2007, 12:39am » 
Quote Modify

on Sep 3^{rd}, 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 1666^{2/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: 13650


Re: Locker Room Dilemma
« Reply #17 on: Sep 4^{th}, 2007, 1:24am » 
Quote Modify

on Sep 3^{rd}, 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: 2818


Re: Locker Room Dilemma
« Reply #18 on: Oct 15^{th}, 2012, 5:03am » 
Quote Modify

on Sep 4^{th}, 2007, 12:39am, mikedagr8 wrote: There is a HUGE difference. One is 16%, the other is 1666^{2/3}%. Try learning the basics, before you advance. 
 >>Thread Necromancy!<< That depends whether you interpret (50/3) as a number then stick a percentsign on the end, or interpret it as a ratio and apply a topercentage 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, 1666^{2/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 



