Best of MathNerds - Crazy Dice

Here's a pair of problems that were given to me by a friend...

When you roll a standard pair of 6-sided dice, there are 11 possible outcomes, with a certain probability of occurrence for each possible result (the chance of getting a total of 8 is 5/36, for example). This is called the probability distribution.

Now, it turns out that you can take 2 6-sided dice and put different positive integers (whole numbers) on them such that the probability distribution is the same. That is, you can write a completely different set of numbers on the 2 dice but still have the same likelihood of rolling any total as if the dice were regular. It turns out that the only way to do this is to put 1, 2, 2, 3, 3, 4 on one die and 1, 3, 4, 5, 6, 8 on the other (clearly I'm allowing repeats of numbers, and if you think about it, repeats must occur).

The two problems I have relate to pairs of dice with more than 6 sides. The first problem can be done by trial and error, but the second one most certainly cannot be done that way, and would require an advanced method of solving.

Find the *2* possible relabelings for a pair of 8-sided dice.
Find the only possible relabeling for a pair of 35-sided dice.

Hint 1

Use generating functions. (Sub-hint: practice on the 6-sided case, where you already know the answer.)

Need another hint? Click here.

Click here for the complete solution.

Hint 2

This hint solves the problem for the 6-sided case (sometimes called Crazy Dice or Sicherman Dice) by using generating functions. Once you understand this case, you should be able to work the 8-sided and 35-sided cases the same way. It's helpful if you have a computer algebra program like Mathematica to do the heavy lifting for you, especially in the 35-sided case, but even by hand they are not too hard.

To write this problem in terms of generating functions we use a variable x and make the following observation: The coefficient of x^n in

(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)

is the number of ways of throwing n using 2 regular dice. This is true because we interpret the first factor as the outcome of the first die (the exponent is how many dots came up) and the second factor as the outcome of the second die. For example, you can throw 8 in 5 ways because the factors that lead to x^8 are

x^2 \cdot x^6, \quad x^3 \cdot x^5, \quad x^4 \cdot x^4, \quad x^5 \cdot x^3, \quad x^6 \cdot x^2.

How about the Crazy Dice? They have polynomials too, which are

(x^1 + x^2 + x^2 + x^3 + x^3 + x^4)(x^1 + x^3 + x^4 + x^5 + x^6 + x^8),

and the fact that they have the same frequency distribution as regular dice implies that this product of polynomials must be exactly the same as the product for the regular dice, and if fact if you multiply them out (or get Mathematica to do it for you) you'll see that they really are identical.

"So what?" you ask. So what is that we know a lot about polynomials, in particular about factoring them, so by converting our problem into a polynomial problem we can use this knowledge and solve it. Imagine that we didn't already know the other solution for 6; then we would want to find polynomials so that

\begin{eqnarray} &&(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)(x^1 + x^2 + x^3 + x^4 + x^5 + x^6)\\ &=& (x^{a_1} + x^{a_2} + x^{a_3} + x^{a_4} + x^{a_5} + x^{a_6}) (x^{b_1} + x^{b_2} + x^{b_3} + x^{b_4} + x^{b_5} + x^{b_6}) \quad \quad \mathrm{(*)} \end{eqnarray}

where the a and the b are the number of spots on each face, and we want to find them. A valid solution must have all a and b greater than or equal 1.

Now we use the polynomial properties. We can completely factor the left-hand side, because

\begin{eqnarray} && x^1 + x^2 + x^3 + x^4 + x^5 + x^6 \\ &=& x(1+x^1 + x^2 + x^3 + x^4 + x^5) \\ &=& x \frac{x^6 - 1}{x - 1} = x (x^3 + 1) \frac{x^3 - 1}{x - 1} \\ &=& x (x + 1) (x^2 - x + 1) (x^2 + x + 1), \end{eqnarray}

so the left-hand side of (*) is

x^2 (x + 1)^2 (x^2 - x + 1)^2 (x^2 + x + 1)^2.

We don't know what the terms on the right-hand side are, but we do know that if we factor them completely we must get exactly the same factorization, although the terms may be grouped differently. This means we can work backward to discover the terms on the right: we consider different ways of grouping the factors to make two polynomials

(x^{a_1} + x^{a_2} + x^{a_3} + x^{a_4} + x^{a_5} + x^{a_6}) \mathrm{\ and \ } (x^{b_1} + x^{b_2} + x^{b_3} + x^{b_4} + x^{b_5} + x^{b_6}) \quad \quad \mathrm{(**)}

and see which ones represent valid 6-sided dice. Not every combination is valid; for example, we cannot give all factors to the first polynomial, and none to the second (leaving the second as a constant 1) because each polynomial must have 6 powers of x to represent the 6 faces. In fact we can eliminate most of the possibilities as follows:

The requirement that each polynomial represent a 6-sided die can be written numerically by saying that the value at x=1 of each polynomial in (**) must be 6. Looking at the complete factorization, we notice that the values of the factors x, x + 1, x^2 - x + 1, and x^2 + x + 1 at x=1 are 1, 2, 1, and 3. If one polynomial in (**) got both copies of (x + 1) and of (x^2 + x + 1), then at x=1 that polynomial would be divisible by 4 or by 9, and so could not be equal to 6. Therefore each polynomial in (**) gets one copy of these factors.
Each face must have at least one spot, so each polynomial in (**) must have an x factor (otherwise the polynomial would have a constant term, that is x^0, that would represent 0 spots). So each polynomial in (**) must get one copy of the factor x.

The only uncertainty remaining is the two (x^2 - x + 1) factors. There's no obvious reason why we have to give one copy to each polynomial, or if we could give both copies to the same polynomial. In fact both choices work; giving one to each produces the regular dice, and (as we can verify by multiplying out the polynomials) giving both copies to one polynomial produces two valid sets of 6 spots, that are the Crazy Dice:

x (x + 1) (x^2 + x + 1) \mathrm{\ and \ } x (x + 1) (x^2 - x + 1)^2 (x^2 + x + 1),

which multiply out to

x + 2x^2 + 2x^3 + x^4 \mathrm{\ and \ } x + x^3 + x^4 + x^5 + x^6 + x^8,

so the spots are

1,2,2,3,3,4 \mathrm{\ and \ } 1,3,4,5,6,8.

That's the complete solution for 6-sided dice, now use the same ideas to solve the 8-sided and 35-sided cases. (The next hint gives the needed factorizations.)

Need another hint? Click here.

Click here for the complete solution.

Hint 3

For the 8-sided and 35-sided cases we have the complete factorizations

x + \cdots + x^8 = x (x+1) (x^2+1) (x^4+1)

and

\begin{eqnarray} x + \cdots + x^{35} &=& x (x^4+x^3+x^2+x+1)(x^6+x^5+x^4+x^3+x^2+x+1) \\ && (x^{24}-x^{23}+x^{19}-x^{18}+x^{17}-x^{16}+x^{14}-x^{13}+x^{12}-x^{11}\\ && \quad +x^{10}-x^8+x^7-x^6+x^5-x+1). \end{eqnarray}

Click here for rest of the solution.

The Rest of the Solution

The 8-sided case has three alternate factorizations, and therefore three relabelings (not the two stated in the problem):

\begin{eqnarray} x (x + 1)^2 (x^4 + 1) &\cdot& x (x^2 + 1)^2 (x^4 + 1) \\ x (x + 1) (x^4 + 1)^2 &\cdot& x (x + 1)(x^2 + 1)^2 \\ x (x + 1)^2 (x^2 + 1) &\cdot& x (x^2 + 1) (x^4 + 1)^2 \end{eqnarray}

and these expand to

\begin{eqnarray} (x^7+2x^6+x^5+x^3+2x^2+x) &\cdot& (x^9+2x^7+2x^5+2x^3+x) \\ (x^{10}+x^9+2 x^6+2x^5+x^2+x) &\cdot& (x^6+x^5+2x^4+2x^3+x^2+x) \\ (x^5+2x^4+2x^3+2x^2+x) &\cdot& (x^{11}+x^9+2x^7+2x^5+x^3+x) \end{eqnarray}

(Thanks to Art DuPré for pointing out the third factorization, which is missing from the original solution.)

The 35-sided case has one alternate factorization, and expands to:

\begin{eqnarray} (x^{11}&+&2x^{10}+3x^9+4x^8+5x^7+5x^6+5x^5+4x^4+3x^3+2x^2+x) \\ \cdot \, (x^{59}&+& x^{54}+x^{52}+x^{49}+x^{47}+x^{45}+x^{44}+x^{42}+x^{40}+x^{39} \\ &+& x^{38}+x^{37}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}+x^{30}+x^{29} \\ &+& x^{28}+x^{27}+x^{26}+x^{25}+x^{23}+x^{22}+x^{21}+x^{20}+x^{18} \\ &+& x^{16}+x^{15}+x^{13}+x^{11}+x^8+x^6+x). \end{eqnarray}

Generating Functions

A generating function is a clothesline on which we hang up a sequence of numbers for display. (Herbert S. Wilf)

A generating function is a polynomial or infinite series in which the coefficient of the nth term is the value at n of some function that we are interested in. In the Crazy Dice the coefficient is the number of faces with n spots.

Generating functions are used in almost all kinds of counting problems. They allow us to transform a counting problem into an algebraic or analytic problem. With the Crazy Dice we used algebraic properties of polynomials (factorization) to solve the problem. Often generating functions are infinite series instead of polynomials; in these cases we often attempt to get a closed-form expression for the function represented by the infinite series, and use facts about the behavior of this function to deduce facts about the coefficients. The References below give many examples of problems that can be solved with generating functions.

Cyclotomic Polynomials

To solve the Crazy Dice we had to factor polynomials of the form

x^{n-1} + ... + x + 1,

which is the same problem as factoring

x^n - 1 = (x-1) (x^{n-1} + ... + x + 1).

The roots of this polynomial are called the nth roots of unity (unity being another name for 1). A primitive nth root of unity is one that is not a mth root of unity for an m smaller than n.

Example: The 4^th roots of unity are the roots of

x^4 - 1 = 0.

These roots are 1, -1, i, and -i. Of these, 1 is a 1^st root of unity, -1 is a 2^nd root of unity, and the remaining two, i and -i are primitive 4^th roots of unity.

The polynomial whose roots are all the primitive nth roots of unity is called the cyclotomic polynomial of order n. The roots are conventionally designated by the Greek letter \zeta, and the polynomial is conventionally designated by a capital Greek letter \Phi:

\Phi_n(x) = \prod_\zeta (x - \zeta).

Example (continued): The cyclotomic polynomials for 1, 2, and 4 are

\begin{eqnarray} \Phi_1(x) &=& x - 1 \\ \Phi_2(x) &=& x + 1 \\ \Phi_4(x) &=& x^2 + 1 \end{eqnarray}

"Cyclotomic" comes from a Greek phrase meaning "circle cutting." If you draw the unit circle in the complex plane, and plot the nth roots of unity, you will find that they all lie on the unit circle and that they cut it into n equal arcs. These points are also the vertices of a regular n-gon inscribed in the circle. The roots of unity and the cyclotomic polynomials occur in many areas of mathematics, and we know a lot about them.

It is a surprising fact that the cyclotomic polynomials have all integer coefficients, and an even more surprising fact that they are all irreducible (that is, they cannot be factored into polynomials of lower degree with rational coefficients). A non-surprising but useful fact is that they give the complete factorization

x^n - 1 = \prod_{m|n} \Phi_m(x).

Example: Crazy Dice for 8 sides. We have the factorization

\begin{eqnarray} x^8 - 1 &=& \Phi_1(x) \Phi_2(x) \Phi_4(x) \Phi_8(x) \\ &=& (x-1) (x+1) (x^2+1) \Phi_8(x) \\ &=& (x^4 - 1) \Phi_8(x), \\ \Phi_8(x) &=& \frac{x^8 - 1}{x^4 - 1} = x^4 + 1. \end{eqnarray}

References

Wikipedia has an article on Sicherman Dice, which is another name for 6-sided Crazy Dice.
Martin Gardner, "Sicherman Dice, the Kruskal Count and Other Curiosities", Chapter 19 (pp. 265-280) in Penrose Tiles to Trapdoor Ciphers, revised edition, Mathematical Association of America, 1997
Herbert S. Wilf, generatingfunctionology, 2nd edition, Academic Press, 1994. All about generating functions.
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994. Exercise 8.36, pp. 431 and 582, works out the 6-sided case and a generalization to n 6-sided dice.
Donald J. Newman, Analytic Number Theory, Springer-Verlag, 1998. Chapter 1, pp. 5-7 deals with Crazy Dice, and generating functions appear throughout the book. Warning: This book is loaded with typographical errors! The second, corrected printing (in 2000) fixes many, but not all, of the errors.
Allan Clark, Elements of Abstract Algebra, Dover reprint, 1984. See sections 134-138 for cyclotomic polynomials and the construction a regular 17-gon.
Click here to view the original problem submitted by Chrix.

Crazy Dice