Imagine you are trapped in a post-apocalyptic world and only have a single d20 at your disposal, nothing else whatsoever. What is the ideal way of emulating all other common dice types (d4, d6, d8, d10, d12, d%) using just this d20 and arbitrarily complicated math?
I realize there's an easy way to make due with a single d6 (using the same d6 also for a coin-like mechanic), but I was wondering if this also works with a d20, and what the criteria are for this to work with a dN, if there is any research on the matter.
Let me preface this by defining a few pointers:
"ideal" = as few d20 rolls as possible.
"emulating" means mapping output from one or more d20 rolls to whichever die you want to emulate, while maintaining statistical accuracy – each possible output for the desired die must be equally likely.
"to map" a number X to an interval [1; B] means to apply an operation of the following form:
$$ dB = X – B \times \textbf{int}\left[\frac{X – 1}{B}\right] $$
where the int[] operation demands rounding down (truncation, since the argument will never be negative for the given problem).
Here's what I have so far, in order of complexity:
Single roll \$X\$: d10 = \$[X]\$ if \$[X \leq 10]\$, else: \$[X – 10]\$
Single roll \$X\$: d% is equivalent to d10.
Single roll \$X\$: \$\textbf{d4} = X – 4 \times \textbf{int}\left[\displaystyle{\frac{X – 1}{ 4}}\right]\$
Two rolls \$X\$, \$Y\$: d8 = \$[X]\$ if \$[X \leq 8]\$, or \$[X – 8]\$ if \$[9 \leq X \leq 16]\$. Alternatively, for \$[X > 16]\$, d8 = \$[Y]\$ if \$[Y \leq 8]\$, or \$[Y – 8]\$ if \$[9 \leq Y \leq 16]\$. Alternatively, if both \$[X > 16]\$ and \$[Y > 16]\$, d8 = \$[X – 16]\$ if \$[X+Y]\$ = even, else: \$[X – 12]\$.
Three+ rolls \$X\$, \$Y\$, \$Z\$: \$\textbf{d6} = X – 6 \times \textbf{int}\left[\displaystyle{\frac{X – 1}{6}}\right]\$ if \$[X \leq 18]\$. If not, check the same for \$Y\$. If not, check the same for \$Z\$. If \$\left\{X, Y, Z\right\}\$ in \$\left\{19, 20\right\}\$ (which has a 1/1000 chance of happening), map the combination to \$[1;6]\$. However, I don't think it is possible to reliable get this mapping even when adding more and more dice rolls. Of course, it will get vastly unlikely rather quickly, but there does not seem to be a reliable way of using binary values to map to 6 reliably, seeing as it is a product of two primes. What is the lowest number of dice rolls required to achieve a 100% successful outcome, if it is possible at all?
The same issue applies to the d12, which can be constructed trivially from a d6 by rolling a d20 like a coin toss, then either using the initial d6 value or d6+6. This might not, however, be the ideal solution for this.
I would greatly appreciate any insight into the matter, as this has kept my mind busy for quite some time now. I'm pretty sure it cannot be reliably done for the d6 and d12, but I would appreciate any kind of closure or proof you peoples might be able to provide!
Best Answer
Emulating a d6 using a fixed number of d20 rolls is impossible.
Of course, as the other answer points out, it is possible to do so if we take into account more than just the rolled result, such as its orientation, but let's ignore that for a moment.
You rightly say that we can emulate a d6 with a d20 by mapping 1-18 to the d6 and rerolling on 19 or 20. This works, but this could in theory go on forever if we keep rolling above 18.
So, why is it impossible? As you said it has something to do with factorization. A d6 is impossible to create with a d20 not because it is the product of two primes, but rather because it has a prime factor which is not present in the prime factorization of 20. Firstly, note that the reason that we can't emulate a d6 with a single d20 is because 20 is not divisible by 6. Now, the prime factorization of 6 is \$2 \times 3\$, and that of 20 is \$2^2 \times 5\$. If we roll \$n\$ d20s, this gives a total of \$20^n\$ possibilities. Because multiplication is the same as adding the prime factors, \$20^n\$ will have \$n\$ times the factors:
$$ 20^n = 2^{2n} \times 5^n $$
That is, regardless of the amount of times we roll a d20, the total amount of possible results will never have a prime factor other than 2 or 5, and will therefore never be divisible by 3. Because every outcome is equally likely, there is therefore no way of distributing these outcomes over the faces of a d6 such that all 6 possibilities are equally likely.
More generally, a dX can emulate a dY if and only if X has all prime factors that Y has. Therefore, a d20 cannot emulate a d3, d6, d12 or d35, but it can emulate a d8, d10 or d4294967296.
Example of emulating a d8 with a d20
If we wish to emulate a d8 with a d20, we first note that 20 is not divisible by 8. This is because 8 has three 2s in its prime factorization, and 20 has only two. However, \$20^2\$ has factorization \$2^4 \times 5^2\$, which encapsulates the prime factorization of 8, and therefore we need only two d20 rolls.
Now, all we needed from one of those rolls was a single factor 2, so we can use one of them as a coin flip. Therefore, we can roll the first d20 and if it lands on the top half (11-20), we take something from the top half of the d8 (5-8), and similarly for the bottom half (1-10) -> (1-4). Then we only have to divide the other d20 in four categories: (1-5) -> (1 or 5); (6-10) -> (2 or 6) and so forth.
Note that this is only an example, and there are plenty of ways to emulate a d8 with two d20s. All you have to do is ensure that out of the 400 possibilities with two sequential d20s, 50 of those possibilities are assigned to each of the 8 target numbers, which is equivalent to cutting the space equally in two a total of three times.