## October 2014 riddle

A dice that has n sides is, conceptually, a device that allows one to allot a number between 1 and n, each with probability 1/n. For example, the cubic dice, the most common dice, does this with n=6.

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:

Yuping Luo (2 October 04:33)
Elegant and original solutions can be submitted to the puzzlemaster at riddles brand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.