



Crazy DiceSubmitted by Chrix from Bloomington, Minnesota, 7/2/2000. Original answer and this article by Allen Stenger.Here's a pair of problems that were given to me by a friend... When you roll a standard pair of 6sided 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 6sided 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.
Need a hint? Click here. Click here for the complete solution. Hint 1Use generating functions. (Subhint: practice on the 6sided case, where you already know the answer.) Need another hint? Click here. Click here for the complete solution. Hint 2This hint solves the problem for the 6sided case (sometimes called Crazy Dice or Sicherman Dice) by using generating functions. Once you understand this case, you should be able to work the 8sided and 35sided 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 35sided 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 lefthand 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 lefthand 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 righthand 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 6sided 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 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 6sided dice, now use the same ideas to solve the 8sided and 35sided cases. (The next hint gives the needed factorizations.) Need another hint? Click here. Click here for the complete solution. Hint 3For the 8sided and 35sided 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^7x^6+x^5x+1).
\end{eqnarray}
Click here for rest of the solution. The Rest of the SolutionThe 8sided 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 35sided 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 FunctionsA 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 closedform 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 PolynomialsTo solve the Crazy Dice we had to factor polynomials of the form
x^{n1} + ... + x + 1,
which is the same problem as factoring
x^n  1 = (x1) (x^{n1} + ... + 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 ngon 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 nonsurprising but useful fact is that they give the complete factorization
x^n  1 = \prod_{mn} \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) \\
&=& (x1) (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

Email the Webmaster 