07 August 2007

more exotic dice

Mark Dominus at The Universe of Discourse shows that there exists a pair of six-sided dice not labeled 1, 2, 3, 4, 5, 6 (or some trivial transformation thereof) that gives the same probability of throwing any sum from 2 to 12 as a pair of standard six-sided dice.. In particular, if one die has faces {1,2,2,3,3,4} and the other has faces {1,3,4,5,6,8} the distribution comes out right. This results from the factorization

(x6 + x5 + x4 + x3 + x2 + x)2 = (x4 + 2x3 + 2x2 + x) (x8 + x6 + x5 + x4 + x3 + x)

and if it isn't clear to you how the fact about dice follows from this, you should read Mark's entry. But the interesting thing is not the result so much as how he got it; I've seen an ad hoc derivation of this alternate pair of dice, but Mark gets is by factoring the left side and rearranging it to get the right side.

In particular, this indicates that you couldn't make, say, a pair of dice that have the same sums as two d7s (i. e. seven-sided dice). That would require us to find two polynomials P(x), Q(x) such that

(x7 + x6 + x5 + x4 + x3 + x2 + x)2 = P(x) Q(x)

but the thing we're squaring on the left-hand side only factors as x(x6 + x5 + x4 + x3 + x2 + x + 1). So we could have

P(x) = (x6 + x5 + x4 + x3 + x2 + x + 1), Q(x) = x2(x6 + x5 + x4 + x3 + x2 + x + 1)

which corresponds to dice with sides {0, 1, 2, 3, 4, 5, 6} and {2, 3, 4, 5, 6, 7, 8}; this clearly isn't the intent of the problem. There's no other way to rearrange the factors. In the case of the six-sided dice, we had

x6 + x5 + x4 + x3 + x2 + x = x(x2 + x + 1)(x2 - x + 1)(x+1)

which allowed for a lot more rearrangement.

So, to take a similar problem, do there exist a pair of eight-sided dice with the analogous property? This time we're looking for a refactoring of

(x8 + x7 + x6 + x5 + x4 + x3 + x2 + x)2 = P(x) Q(x).

There are certain other conditions this refactoring has to satisfy, as Mark points out; we must have P(1) = Q(1) = 8 (which corresponds to the dice having eight sides) and none of the coefficients of P or Q can be negative; furthermore neither one can have a nonzero constant term (this corresponds to having faces labeled zero). The left-hand side factors nicely, as x(x+1)(x2+1)(x4+1). So we have

x2(x+1)sup>2(x2+1)sup>2(x4+1)sup>2 = P(x) Q(x)

and one of the factors x must be assigned to P(x), while the other must be assigned to Q(x). Now, at x=1 this becomes

12(1+1)2(1+1)2(1+1)2 = P(1) Q(1)

and we remember we needed P(1) = 8, Q(1) = 8; each of the six remaining factors on the left-hand side is a factor of 2, so we must have three of these making up P(x), and three making up Q(x). The possible factorizations, then, are

P(x) = x(x+1)2(x2+1), Q(x) = x(x2+1)(x^4+1)2
P(x) = x(x+1)2(x^4+1), Q(x) = x(x2+1)2(x^4+1)
P(x) = x(x+1)(x2+1)2, Q(x) = x(x+1)(x4+1)2

in addition to the original one; these correspond to pairs of dice labeled {1, 2, 2, 3, 3, 4, 4, 5} and {1, 3, 5, 5, 7, 7, 9, 11}; {1, 2, 2, 3, 5, 6, 6, 7} and {1, 3, 3, 5, 5, 7, 7, 9}; {1, 2, 3, 3, 4, 4, 5, 6} and {1, 2, 5, 5, 6, 6, 9, 10}. The proliferation of these pairs here seems to stem from the simple factorization, which in turn is a consequence of the fact that 8 is a power of 2. Alternatively, we can imagine replacing each d8 with three coins, labeled {0, 1}, {0, 2}, and {0, 4}; rolling a d8 corresponds to flipping these three coins and taking 1 plus the sum of their labels. The "alternative" dice correspond to the different ways in which we can split up this collection of six coins into two triplets; there are a lot of ways to rearrange these coins. Essentially, the d8 "factors" into these component coins. In the d6 case I don't see the dice being able to be factored in this way into smaller dice (a coin is just a two-sided die); this is because factoring the corresponding polynomials gives polynomials with negative coefficients, which has no "physical" analogue.