wu :: forums - Print Page


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

        riddles >> hard >> strategy  for escape of osama and saddam
        
(Message started by: inexorable on Dec 14^th, 2005, 7:52pm)

Title: strategy for escape of osama and saddam
Post by inexorable on Dec 14^th, 2005, 7:52pm

Osama and saddam, who are prisoners under the supervision of warden GWB, are in separate rooms and cannot communicate with each other. GWB meets with them individually, gives each a penny, and offers to free them if they succeed in the following task.

On the next day they are to appear together in GWB's office, and each is to hold out a closed fist which either contains, or does not contain, the penny. They open their fists simultaneously and anyone holding a coin must flip it. They will be released if there is at least one flip and if all flips are heads.

What strategy should osama and saddam follow to maximize the probability of success?
Ps:-you can assume that each know that other one is smart, and approaches problem probabilistically

Title: Re: strategy for escape of osama and saddam
Post by Neelesh on Dec 14^th, 2005, 11:51pm

What if both of them caarry the coin and close the fist in such a way that on opening it, tail is up, and then they flip the coin so that head is up?

I am sure I am missing something.

Title: Re: strategy for escape of osama and saddam
Post by inexorable on Dec 15^th, 2005, 6:11am

on 12/14/05 at 23:51:58, Neelesh wrote:

What if both of them caarry the coin and close the fist in such a way that on opening it, tail is up, and then they flip the coin so that head is up?

flip here means tossing the coin.

Title: Re: strategy for escape of osama and saddam
Post by rmsgrey on Dec 15^th, 2005, 9:01am

I reckon their ideal strategy is:

[hideb]independently calculate the value, p, which maximises their probability of escape if each of them independently produces the penny with probability p. Doing so is easy enough - the probability of escape is a quadratic in p - and gives p=2/3[/hideb]

Probability of escape: [hide]1/3[/hide]

Title: Re: strategy for escape of osama and saddam
Post by inexorable on Dec 16^th, 2005, 6:39am

can this be generalised to n prisoners?

Title: Re: strategy for escape of osama and saddam
Post by JocK on Dec 16^th, 2005, 10:20am

No, although Saddam seemed to have a number of duplicates, there s only one Saddam and one Osama... (just the thought of it! :-/ )

Title: Re: strategy for escape of osama and saddam
Post by JocK on Dec 16^th, 2005, 10:59am

So: n prisoners appear together, and each is to hold out a closed fist which either contains, or does not contain, the penny. They open their fists simultaneously and anyone holding a coin must toss it. They will be released if there is at least one toss and if all tosses produce heads.

The optimal strategy for each of them is to hold a penny with probability P = [hide](2^1/(n+1) - 1) / (2^1/(n+1) - 1/2)[/hide].

The resulting probability for release is (1-p)^n-1.