wu :: forums « wu :: forums - Locker Room Dilemma » Welcome, Guest. Please Login or Register. Dec 13th, 2018, 9:15pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: ThudnBlunder, Grimbal, william wu, Eigenray, towr, SMQ, Icarus)    Locker Room Dilemma « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Locker Room Dilemma  (Read 6531 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)

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
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: 13650
 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: 13650
 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:
 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:
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: 13650
 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: 2818
 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.

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 Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

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