Renumbering Dice

Metadata

This post collates some math exploration I did in 2017. They were originally posted on the now defunct forums of brilliant.org. Due to a series of unfortunate events (and financial incentives) the entire forum has been effectively deleted.

Here I've reorganised my work and added some new stuff.

Probability distribution of rolling dice.

Define an $n$-die as a die with $n$ sides.

Define a regular $n$-die as a die with $n$ sides numbered $\{1,2,3,\cdots,n\}$

So a typical way of rolling dice is to take one or more dice, rolling and then summing their results. For instance, a common case is taking two regular 6-die, rolling them and summing the results.

In this example, you can get a $2$ by rolling $(1,1)$, up to a $12$ by rolling $(6,6)$.

However, the probabilities of getting a $2$ through $12$ aren't the same.

Similarly, rolling more than two 6-die will result in a different probability distribution. For instance, here is three 6-dice:

There's a generic method to compute this distribution: we could simply tally all possible rolls. For the case of rolling two 6-dice, we have $6^2 = 36$ possibilities, each of equal probability. For each possibility, we can find the sum of the results and construct a table as follows:

The probability that the result is $n$ is simply the number of times $n$ appears in the table divided by $6^2$.

Using polynomials instead of a table

You might have noticed that the table is remarkably similar to polynomial multiplication. For instance, try expanding $(x^6+x^5+x^4+x^3+x^2+x^1)^2$. In order to keep track of the coefficients of the final expanded result, you might construct a similar table:

The coefficient of say $x^5$ is the number of times $x^5$ appears in the table.

Notice how the powers in the table are identical to the previous table? That's bcuz it's exactly the same operation!

This is great bcuz in our analysis of the probabilty distribution of rolling dice, we could and will map it into a problem about polynomials, which we can analyse with the numerous, powerful methods developed to analyse polynomials.

An Informal-Formal Formulation

The relation between polynomials and rolling dice can be made explicit as such:

Lemma 1:

Let $D_{A}$ be a dice numbered with numbers from the set $A = \{a_1, a_2, \cdots, a_n\}$. Let $P(A) = \sum_{a \in A} x^a$ be the polynomial representing the numbers of $D_{A}$.

Upon rolling $k$ dice $D_{A_1}, D_{A_2}, \cdots, D_{A_k}$ and summing the results, the probability of the result being $r$ is $c_r \prod_{1 \le i \le k}|A_i|^{-1}$, where $c_r$ is the coefficient of $x^r$ in the polynomial $\prod_{1 \le i \le k} P(A_i)$.

This relation explicitly converts the probability distribution of rolling dice, into a polynomial.

Dice Renumbering Problem

Now we're ready to introduce a problem on rolling dice. Many board games require rolling two or three regular 6-dice and taking the sum of the output.

Question 1:

Is there a way to renumber two 6-dice with positive integers such that the sum of results for rolling the two renumbered dice has the same probability distribution as rolling two regular 6-dice?

We could tackle this problem by analysing $p_{6,6} = P(\{1,2,3,4,5,6\})^2$, the polynomial that represents the probability distribution of the result upon rolling two regular 6-dice.

Say we have an alternate numbering $D_B$ and $D_C$, $B = \{b_1,b_2,\cdots,b_6\}$, $C = \{c_1,c_2,\cdots,c_6\}$, then by lemma 1, we have $p_{6,6} = P(B) P(C) = p_B p_C$. This means that both $p_B$ and $p_C$ are factors of $p_{6,6}$.

We also know that $P(B)$ and $P(C)$ represent numberings on 6-sided dice, so we have the addtional conditions:

1. $p_B\vert_{x=1} = p_C\vert_{x=1} = 6$, on account $D_B$ and $D_C$ having 6 sides.
2. The coefficients of both $p_B$ and $p_C$ must all be positive integers.

We could easily factorize $p_{6,6}$ computationally (or by noting that the factors are Cyclotomic Polynomials):

Thereafter, we can try every combination of $p_B$ and $p_C$ such that the two conditions above are satisfied. This yields the below numberings:

The second numbering corresponds to regular 6-dice. The first is hence the only numbering possible that answers the question.

In other words, renumbering the dice $\{1,3,4,5,6,8\}$ and $\{1,2,2,3,3,4\}$ is the only way to renumber dice with positive integers such that rolling and summing the results is equivalent to using two regular 6-dice.

I really wanna fabricate these renumbered 6-dice in real life. My favourite person in the world suggested calling them Cookies and Cream, because they have to go together ❤

General Case

We could renumber dice to emulate other dice as well. For instance, what if we wanna say, emulate a regular 18-die with two 6-dice? We could do a similar analysis as above and find all the possible numberings! For the sake of generalisation, we shall relax the condition for numberings to become non-negative integers as opposed to the previous positive integers. In other words, we are allowed to number a face $0$.

The generalisation can be written as such:

How many ways are there to renumber, with non-negative integers, $k$ dice with sides $n_1, n_2, \cdots, n_k$ such that it emulates the rolling and summing of $k'$ regular dice with sides $t_1, t_2, \cdots, t_{k'}$

Here's code to automatically compute the numberings for the general case, written in Sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from sympy.utilities.iterables import multiset_partitions
from collections import Counter
from typing import List

# Work in integer polynomials
x = PolynomialRing(ZZ, 'x').gen()

def dice(n:int) -> "PolynomialZZ":
    
    """Returns polynomial of a regular n-sided die"""
    
    return x*sum(x^i for i in range(n))

def get_numberings(nsides: List[int], tsides: List[int]) -> List[List[int]]:
    
    """
    Returns possible numberings of dice with sides `nsides`
    that when rolled and summed, gives the same distribution as
    regular dice of sides `tsides`
    """
    
    # Check if numberings is even possible
    nx,tx = reduce(lambda a,b: a*b, nsides), reduce(lambda a,b: a*b, tsides)
    assert nx % tx  == 0, \
        "No numberings possible"
    
    # Target distribution
    target = reduce(lambda a,b: a*b, map(dice, tsides)) * (nx//tx)

    # Factors of target distribution
    # Stored as [(factor, sum of coefficients), ...]
    tfactors = [(f,f(1)) for f,c in target.factor() for _ in range(c)]

    tsols = [] # Stores the possible numberings
    _ns = Counter(nsides)
    for ps in multiset_partitions(tfactors, len(nsides)):

        # Skip solutions where new dice don't have `nsides` sides
        ns = [reduce(lambda a,b:a*b[1], p, 1) for p in ps]
        if Counter(ns) != _ns:
            continue

        # Multiply factors together
        ps = [reduce(lambda a,b:a*b[0], p, 1) for p in ps]

        # Skip solutions with negative coefficients
        if min(min(p.coefficients()) for p in ps) < 0:
            continue

        # Convert polynomials to numberings
        tsols.append([
            [c for c,n in p.dict().items() for _ in range(n)]
            for p in ps
        ])
        
    return tsols

def print_numberings(tsols: List[List[int]]) -> None:

    """Pretty-print the possible numberings"""

    print(f"{len(tsols)} Possible Numberings:")
    nsides = [len(t[0]) for t in tsols]
    nsides.sort()
    for t in tsols:
        print()
        t.sort(key=lambda x:len(x))
        for n,d in zip(nsides,t):
            d = " ".join(f"{x:2}" for x in d)
            print(f"{n:3}-sides: {d}")

Applied to the original problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
nsides = [6,6]
tsides = [6,6]
tsols = get_numberings(nsides, tsides)
print_numberings(tsols)

# 5 Possible Numberings:
# 
#   6-sides:  2  4  5  6  7  9
#   6-sides:  0  1  1  2  2  3
# 
#   6-sides:  2  3  4  5  6  7
#   6-sides:  0  1  2  3  4  5
# 
#   6-sides:  2  3  3  4  4  5
#   6-sides:  0  2  3  4  5  7
# 
#   6-sides:  1  3  4  5  6  8
#   6-sides:  1  2  2  3  3  4
# 
#   6-sides:  1  2  3  4  5  6
#   6-sides:  1  2  3  4  5  6

Applied for emulating a regular 18-die via two 6-dice:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
nsides = [6,6]
tsides = [18]
tsols = get_numberings(nsides, tsides)
print_numberings(tsols)

# 8 Possible Numberings:
# 
#   6-sides:  1  1  3  3  5  5
#   6-sides:  0  1  6  7 12 13
# 
#   6-sides:  1  1  2  2  3  3
#   6-sides:  0  3  6  9 12 15
# 
#   6-sides:  1  1  7  7 13 13
#   6-sides:  0  1  2  3  4  5
# 
#   6-sides:  1  1  4  4  7  7
#   6-sides:  0  1  2  9 10 11
# 
#   6-sides:  0  0  2  2  4  4
#   6-sides:  1  2  7  8 13 14
# 
#   6-sides:  0  0  1  1  2  2
#   6-sides:  1  4  7 10 13 16
# 
#   6-sides:  0  0  6  6 12 12
#   6-sides:  1  2  3  4  5  6
# 
#   6-sides:  0  0  3  3  6  6
#   6-sides:  1  2  3 10 11 12

Which $n$-dice can we emulate with just platonic dice?

There is a notion of fairness in dice that I first saw in Numberphile's Video: Fair Dice, where their notion of fairness restricts the shapes of the dice to be Platonic Solids, the 'most symmetric' of the polyhedras.

If we were to restrict ourselves to Platonic Solids, then the $n$-dice we get to work with are:

1. 4-die: Tetrahedron
2. 6-die: Cube
3. 8-die: Octahedron
4. 12-die: Dodecahedron
5. 20-die: Icosahedron

Define a Platonic Die to be one of the above dice.

If we want other $n$-dice, we would have to emulate it by renumbering one or more of the above Platonic dice.

For instance, above, using the code I've written, we've found $8$ possible numberings to emulate an 18-die with two 6-dice. For instance, renumbering two 6-dice $\{0,0,6,6,12,12\}$ and $\{1,2,3,4,5,6\}$, rolling and summing the results, gives an equal probability of the result being $1,2,\cdots,18$, as if we have just rolled a regular 18-die.

The question remains however:

Question 2:

For which $n$ can an $n$-dice be emulated by renumbering one or more Platonic Dice with non-negative integers? We have found an algorithm to output all possible numberings, but for which $n$ could we guarantee to have numberings and for which $n$ could we guarantee to have none?

I posit that:

There exists numberings if and only if $n$ only has prime factors $2,\,3,\,5$.

Proof

Lemma 2.1:

There are no numberings possible if $n$ has prime factors other than $2,\,3,\,5$.

Proof:

We prove by contradiction. Assume there exists an $n$ with a prime factor $p \ne 2,\,3,\,5$ such that there exists numberings. This means there exists dice with sides $T=\{t_1, t_2, \cdots, t_k\}$ such that rolling it and summing the results gives an equal probability of getting $1, \cdots, n$. The number of possibilities for rolling dice with sides $T$ is $T_n = \prod_{t \in T} t$, each possibility having an equal probability of occuring. These imply $N \mid T_n$, since it implies that there exists a way to place the $T_n$ possibilities into $n$ equally-sized bins. However, since $T$ can only contain $4,\,6,\,8,\,12,\,20$, $T_n$ can only have prime factors $2,\,3,\,5$, which imply $N \nmid T_n$: A contradiction. $\blacksquare$

Lemma 2.2:

For every $n$ that only has prime factors $2,\,3,\,5$, there always exists a numbering.

Proof:

We shall show by explicit construction that there always exists a numbering.

Here is where I bring in the concept of Number Bases into dice renumberings. Suppose we work in base $6$. For an $x$ digit number, we could represent every number in $[0, 6^x)$ exactly once as $\overline{a_1a_2\cdots a_x}^6, \; a_i \in [0,6)$, where the horizontal line represents string concatenation rather than multiplication.

Another way I could represent this is that, for each number in $[0, 6^x)$, it is represented exactly once for every choice of $a_i \in [0,6)$ by the following expression: $\overline{a_1a_2\cdots a_x}^6 = a_1 + 6a_2 + \cdots + 6^{x-1}a_x$.

This means that if we were to number $x$ 6-dice with $\{0, 6^i, 2 \cdot 6^i, \cdots, 5 \cdot 6^i\}, \; i \in [0,x)$, rolling the dice and summing the results would give an equal probability of getting each number in $[0, 6^x)$.

If we were to add $1$ to every number on one of the dice, we would have an equal probability of getting each number in $[1, 6^x]$, effectively emulating a $6^x$-dice!

This basic idea can be generalised to all $n$ with only prime factors $2,\,3,\,5$. We start by constructing a 2-die from a 4-die by repeating the faces twice on the 4-die. Similarly, we can construct 3-die from a 6-die and a 5-die from a 20-die. The reason we do so is so that we could work in $2,3,5$-dice, which makes the argument slightly easier.

Let $n = 2^x 3^y 5^z$. We can represent each number in $[0,n)$ exactly once as

This corresponds to numbering $x$ 2-dice with $\{0, \, 2^i 3^y 5^z\}, \; i \in [0, x)$, $y$ 3-dice with $\{0, \, 3^i 5^z, \, 2 \cdot 3^i 5^z\}, \; i \in [0, y)$ and $z$ 5-dice with $\{0, 5^i, \, 2\cdot 5^i, \, 3\cdot 5^i, \, 4\cdot 5^i\}, \; i \in [0,z)$. Rolling these dice and summing the results gives an equal probability of getting each number in $[0, n)$.

Similar to what we did above, if we were to add $1$ to every number on one of the dice, we would have an equal probability of getting each number in $[1,n]$. We have hence constructed a numbering that emulates an $n$-dice if $n$ only has prime factors $2,\,3,\,5$. $\blacksquare$

Combining the above two lemmas shows that there exists numberings if and only if $n$ only has prime factors $2,\,3,\,5$. $\blacksquare$