wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Locker Room Dilemma
        
(Message started by: inexorable on Jan 28th, 2006, 6:15am)
Title: Locker Room Dilemma
Post by inexorable on Jan 28th, 2006, 6:15am
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%.
Title: Re: Locker Room Dilemma
Post by Sjoerd Job Postmus on Jan 28th, 2006, 10:29am
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 :P
----
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 ;)
Title: Re: Locker Room Dilemma
Post by ChunkTug on Jan 28th, 2006, 12:56pm
As a first guess...

[hideb]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.[/hideb]
Title: Re: Locker Room Dilemma
Post by JocK on Jan 28th, 2006, 1:35pm

on 01/28/06 at 12:56:36, ChunkTug wrote:
[hideb]If you see your card, good. If not go to the locker corresponding to that card.[/hideb]



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...  ???
Title: Re: Locker Room Dilemma
Post by JohanC on Jan 29th, 2006, 12:31am

on 01/28/06 at 13:35:02, 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...
Title: Re: Locker Room Dilemma
Post by JocK on Jan 29th, 2006, 2:26am

on 01/28/06 at 12:56:36, ChunkTug wrote:
As a first guess...

[hideb]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.[/hideb]


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 [hide]that was (or will be) checked initially by that very fellow prisoner.[/hide]

Cute solution ChunkTug.
Title: Re: Locker Room Dilemma
Post by inexorable on Feb 1st, 2006, 3:17am
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?
Title: Re: Locker Room Dilemma
Post by sideshowmel on Apr 28th, 2006, 2:17pm
For 2k prisoners we can modify the solution as follows:
[hideb]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.[/hideb]

The probability of success can then be calculated as follows:
[hideb]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. [/hideb]
Title: Re: Locker Room Dilemma
Post by Trebla on May 23rd, 2006, 11:50am
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"
[hide]
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.
[/hide]
Title: Re: Locker Room Dilemma
Post by srn347 on Sep 1st, 2007, 3:04pm
The first two look into 1 and 2, the next two look in 3 and 4. 50% success probability.
Title: Re: Locker Room Dilemma
Post by towr on Sep 2nd, 2007, 7:13am

on 09/01/07 at 15:04:37, 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%
Title: Re: Locker Room Dilemma
Post by mikedagr8 on Sep 2nd, 2007, 2:37pm

on 09/02/07 at 07:13:53, 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.
Title: Re: Locker Room Dilemma
Post by srn347 on Sep 2nd, 2007, 3:37pm
Oh. Maybe there aren't any.
Title: Re: Locker Room Dilemma
Post by towr on Sep 3rd, 2007, 1:48am

on 09/02/07 at 14:37:06, 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.
Title: Re: Locker Room Dilemma
Post by mikedagr8 on Sep 3rd, 2007, 1:52am

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. ;)
Title: Re: Locker Room Dilemma
Post by srn347 on Sep 3rd, 2007, 8:47pm
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?
Title: Re: Locker Room Dilemma
Post by mikedagr8 on Sep 4th, 2007, 12:39am

on 09/03/07 at 20:47:55, 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.
Title: Re: Locker Room Dilemma
Post by towr on Sep 4th, 2007, 1:24am

on 09/03/07 at 20:47:55, 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)
Title: Re: Locker Room Dilemma
Post by rmsgrey on Oct 15th, 2012, 5:03am

on 09/04/07 at 00:39:29, 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.


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