## October 2014 solution

This month's riddle was a classic which has been making the rounds for many years. The solution is that it is possible to simulate a dice with any number of sides, n, with just two coins. This was shown by this month's solvers in a dazzling variety of ways. The following is the first solution I have heard for the problem. It uses one coin that is fair and one coin that has probability 1/n of falling on heads, making for a very elegant choice of coin probabilities.

Suppose you throw the 1/n coin once and then the fair coin k times. This action divides the probability space to 2k pieces of probability 1/2kn and 2k pieces of probability (n-1)/2kn. Let us refer to the former as A-type pieces and the latter as B-type pieces. The question is: can these pieces be joined together in order to form n pieces of total probability 1/n each?

We can, for example, take a of the A-type pieces and b of the B-type pieces to form the first slice. For this to work, we need to have a+(n-1)b=2k. For example, we can have b=2k div (n-1) and a=2k mod (n-1). Let's call that the canonical (a,b) combination. There are no solutions that use a smaller a value than the canonical combination, but decreasing b is always possible, given a large-enough supply of A-type pieces: to reduce b by one, we compensate by increasing a by n-1.

Suppose, now, that we try to map as many of the n target pieces as possible with the canonical (a,b) combination. If nothing stops us then we are done, but if something does stop us, it will be that we've run out of either enough A-types or enough B-types. As we have seen, running out of B-types is not a problem, as we can always tile the probability space with less of them (including with none of them) by replacing them with the appropriate number of A-types. Running out of As, however, is something we'd like to avoid.

The solution is to make sure that ab. As we have started with an equal number of A-types and B-types, choosing an (a,b) combination that uses at least as many of the B-types as of the A-types guarantees us that A-types will not run out first.

If we are able to find an (a,b) combination with ab, the problem is solved: we begin by creating slices with our chosen combination until B-types run out. From that point on, we make up the missing B-types by replacing them with the appropriate number of A-types. Because all our pieces have probabilities that sum up to 1, the number of A-types will clearly be exactly enough to complete the last piece.

We are now left with the question of how to ensure ab. Recall that in the canonical combination we have chosen a to be 2k mod (n-1). For this reason we are guaranteed a<n-1. By choosing a large enough k -- such as a k value for which 2k≥(n-1)2 -- we have that our b value, namely 2k div (n-1), satisfies bn-1. Therefore, ba as required, and we are done.

Q.E.D.