Problem of the Week 1044

No Teamwork Allowed

Alice and Bob, who are prisoners under the supervision of warden Charlie, are in separate rooms and cannot communicate with each other. Charlie 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 Charlie'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 Alice and Bob follow to maximize the probability of success?

Note: The coin is a perfect 50-50 coin.

Extra credit: Solve this for n prisoners.

Source: Martin Erickson, Math Mag, 297-300, Oct 2005.

© Copyright 2005 Stan Wagon. Reproduced with permission.