Using your Head is Permitted

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)
Radu-Alexandru Todor (2 October 08:08)
Oded Margalit (5 October 07:55)
Daniel Bitin (6 October 20:36)
Jens Voss (10 October 06:02)
Deron Stewart (11 October 10:49)
Li Li (13 October 03:10)
Lorenzo Gianferrari Pini (15 October 03:32)
Dan Dima (30 October 02:00)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page