To show that no *n*-sided dice can be simulated by a single, rational,
biased coin, consider a coin whose odds are *p*:*q* of falling on
'heads' vs. 'tails' (by which we mean that the probability of falling on
'heads' is *p*/(*p*+*q*)). Without loss of generality, let us
assume that *p*>*q*. Furthermore, the odds are given here in fully
reduced form, so *p* and *q* are known to be co-prime.

Suppose to the contrary that one was able to simulate an *n*-sided dice
using such a coin by tossing it *a* times for some *a*. There are
2^{a} possible outcomes for the coin tosses, and we need to group
these into sets so that the total probability in each set equals 1/*n*. In
particular, the total probability in every set must be equal.

Each of the possible coin-toss outcomes occurs at probability
*p*^{i}*q*^{(a-i)}/(*p*+*q*)^{a},
where *i* is the number of times the coin falls on 'heads' in the outcome.
Let us multiply all probabilities by (*p*+*q*)^{a} to
obtain integers, and then consider the result modulo *p*. For all events,
the result is zero, except for the event where *i*=0 (the coin fell
*a* times on 'tails'), where the result is
*q ^{a}*≠0 (mod

Whichever way we sum these events, the result in modulo *p* will continue
to be zero for all subsets, except for the one subset that includes the
'all-tails' event, which will have *q ^{a}*≠0 (mod

In particular, it cannot be true that all sets have the same sum.

For completion, we add
that using the fair coin one cannot simulate any dice where *n* is not
a power of two, because the probability sum of any set of possible outcomes when
tossing the fair coin is a rational with a lowest denominator that is a power of
2. In particular, it cannot be 1/*n*.

We will assume *n*>2. For *n*=2, merely choose *p*=sqrt(1/2),
and simulate the dice (which is the fair coin in this case) by tossing it
twice and checking if both outcomes are 'heads'.

Suppose that we toss the coin *a* times. This results in
2^{a} distinct possible outcomes, which we will now collate into
sets.

For every *i* between 0 and *a*, there are exactly
*c _{i}*=

Clearly, each output between 1 and *n*-1 has the same probability. We
will show that with an appropriate choice of *a* and *p*, the
probability of an *n* output can be made equal to the other probabilities.

First, note that it is always possible, by choosing a sufficiently large
*a*, to make the number of events labelled *n* be smaller than
2^{a}/*n*. To see this, consider that for each of the
*a*+1 possible *i* values, at most *n*-2 events will be labelled
*n*, for a total of (*a*+1)(*n*-2). For this to be smaller
than 2^{a}/*n* we need

This means that asymptotically an *a* value on the order of
2 ceil(log_{2}*n*) should work, but let's use
*a*=4 ceil(log_{2}*n*), instead. Let us verify that
this value of *a* does, indeed, meet the condition of the equation.

We have 2^{a}≥*n*^{4}, and
*n*^{2}>*n*^{2}-2*n*, so a sufficient
condition is

or

This means our chosen *a* works for all *n* values, given our
assumption that *n* is greater than 2.

Under this choice of *a*, we have that the number of events labelled
*n* is,
in total, less than 1/*n* of the total number of possible outcome events.
In
other words, if we choose *p*=1/2, using the fair coin, a label of
*n* will be output at too low a probability (because when using a fair
coin, each outcome is of equal probability). However, suppose that we choose
*p*=0, instead. Then, at probability 1, the output will be all-tails,
which is a possibility labelled *n*, so *n* will be output at too
high a probability.

The probability of outputting *n* is clearly a continuous function of
*p*, so there must exist a value of *p* between 0 and 1/2 for which
every label is output with equal probability, thus concluding our construction.

As for the bonus question:

Regardless of how many coins we use or what their probabilities are (including
whether they are rational or irrational), *a* coin tosses result in
exactly 2^{a} possible outcomes. For some grouping of these
outcomes to yield *n* sets with a total probability of 1/*n* each,
the original number of outcomes must be at least *n*. Hence we have
*a*≥ceil(log_{2} *n*) as an absolute lower bound for any
strategy. Our construction is within a
factor of 4 from this optimum (and asymptotically 2).

Further reading:

When I published the October riddle, I said that it was a "classic" riddle, meaning that it's been around for so long that its origin has been lost. Turns out, I was wrong about this: the origin was not lost. Amir Sarid sent me the following link to what appears to be the origin of this riddle, and where many of its natural follow-ups are discussed, such as the one featured as this month's riddle.