Using your Head is Permitted

You don't actually need a dice to attain this effect. For example, a cubic dice can be simulated by two coins: one fair coin, with 1:1 probability of landing on heads vs. tails, and the other a biased coin, with 1:2 probability.

To determine the value of a dice throw, first toss the biased coin. If it lands on heads (which happens with probability 1/3), set i=1. If not, throw the fair coin. If it lands on heads, set i=2; otherwise, set i=3. Now, throw the fair coin again, and if it lands on heads add 3 to i. The final value of i is the value returned by our simulated dice. It is not difficult to ascertain that each of the values from 1 to 6 is attained in this way with probability 1/6.

This is, of course, not the only way to simulate a cubic dice, and the algorithm is given here merely as an illustration. The main feature to note about this algorithm is that it terminates in finite, bounded time (i.e., total number of coin tosses), always, regardless of the result of any coin tosses. This is a feature we will require of all simulations.

This month's question: is it always possible to simulate an n-sided dice with only 2 coins? If so: which coins should you use? Describe an algorithm that performs this simulation (recalling that it must terminate in bounded time). You are allowed to pick a different pair of coins for each n.

If it is not always possible to create such a simulation for every n: find a value of n for which it is not possible and prove impossibility for it.

List of solvers: