Call a biased coin a p-coin if it comes up heads with probability p and tails with probability 1-p. We say that a p-coin simulates a q-coin if by flipping a p-coin repeatedly (some fixed finite number of times) one can simulate the behavior of a q-coin.

For example, a fair coin can be used to simulate a 3/4-coin by using two flips and defining a pseudo-head to be any two-flip sequence with at least one real head. The chance of a pseudo-head coming up is 3/4, so we have simulated a 3/4-coin.

1. Find a rational value p such that a p-coin can simulate both a 1/2-coin and a 1/3-coin, or prove that no such value exists.

2. Find an irrational value p such that a p-coin can simulate both a 1/2-coin and a 1/3-coin, or prove that no such value exists.

Part II:

Done!  Either a (1/2 - sqrt(1/12))-coin or a (1/2 + sqrt(1/12))-coin
can be used to simulate both a 1/2 and a 1/3 coin.  One way is:

Flip twice.  Define one head out of two flips as a simulated head.  This has probability 1/3 and simulates a 1/3 coin.  (See previous post).

Flip three times.  Define all heads or all tails as a simulated head.  This has a probability of 1/2, and simulates a 1/2 coin.  (Using a (1/2 + sqrt(1/12))-coin, the probability of all heads is 1/4 + (5/6)sqrt(1/12) and the probability of all tails is 1/4 - (5/6)sqrt(1/12)   ).

I suspect that lots of other irrational coins will also do the trick, and I know that these two coins can simulate lots of other rational coins.

Part I: I believe that this is impossible.  See my (inadvertently) untitled post of 2/18/2005.

Good problem, David.  Since I can solve it, I rate it a 4.
I save a rating of 5 for those puzzles where I am forced to give up and look it up.

By the way, I seem to be writing for posterity here, since everybody else has lost interest in this problem.

Posted by Steve Herman on 2005-02-21 15:34:46