olympiad problem involving generating functions

Question

Shifty has $2$ fair octahedral dice, each containing all the integers from $1$ to $8$

Shifty's arch-nemesis Shafty wants to design two different octahedral dice such that:

• both of Shafty's dice have different numbers from Shifty's dice (the positions of the numbers on each dice do not matter)

• Each face on Shafty's dice has some integer from $1$ to $8$

• The probability of rolling a particular sum with Shafty's dice is the same as the probability of rolling the same sum with Shifty's dice

Is it possible for Shafty to design such a pair of dice? If so, give an example of a pair of dice Shafty could make (positions of numbers on each dice do not matter). If not, prove that this is impossible.

Answer 1

No, sadly it cannot be done. It's a neat problem, and pretty classical.

Start with the generating polynomial for Shifty's dice:

$$p_d(x) = {1\over 8}\sum_{i=1}^8 x^i$$

so that the sum probability is given by

$$p_s(x) = {1\over 64}\left(\sum_{i=1}^8x^i\right)^2= {1\over 64} \left({x^9-1\over x-1}-1\right)^2={1\over 64}\left({x^9-x\over x-1}\right)^2$$

This is just

$$p_s(x)={1\over 64} x^2\left((x^4+1)(x^2+1)(x+1)\right)^2$$

Now here's the kicker, if two different dice gave the same sum, then their generating polynomials, $q_1(x), q_2(x)$ would satisfy $q_1(x)\cdot q_2(x)=p_s(x)$ and since the values are from $1-8$ we need that $q_i(0)=0, i=1,2$. But from the list of irreducible factors we see that this means that $x^4+1$ is a factor of both sides, because if it's just a factor of one, one of the $q_i$ has degree $\ge 9$, impossible. But then similarly if both $x^2+1$ are on one side, then combined with $x^4+1$ and $x$ we would also get too high a degree, but then both sides are at degree $7$ and already have factors $x(x^4+1)(x^2+1)$ so both must get one of the remaining $(x+1)$ factors, so it cannot be done.

Note that if Shafty were allowed a value of $0$ on his dice we could do it though, just let

$$\begin{cases} q_1(x) = {1\over 8}(x^4+1)x^2(x+1)^2 = {1\over 8}(x^8+2x^7+x^6+x^4+2x^3+x^2) \\ q_2(x) = {1\over 8}(x^4+1)(x^2+1)^2 = {1\over 8}(x^8+2x^6+2x^4+2x^2 + 1)\end{cases}$$

which of course would give him the right dice with one having sides $2,3,3,4,6,7,7,8$ and the other with sides $0,2,2,4,4,6,6,8$.

And just as a fun side-observation: this means that any dice with side numbers a power of $2$ is out of the running, because the generating polynomial is always ${1\over 2^n}x{x^{2^n}-1\over x-1}$ for a fair die, and by general theory this is just

$${1\over 2^n}x{x^{2^n}-1\over x-1}={1\over 2^n}x\prod_{i=1}^{n-1}(x^{2^i}+1)$$

so that by degree requirements, you have to put an $x$ on both sides, then only one of the $(x^{2^{i}}+1)$ factors each.