Ken's POTW


Alternative Dice
A regular pair of dice consists of two 6-sided dice with the numbers 1 through 6 on both dice, yielding the following probability for each sum:
2:1/36 3:2/36 4:3/36 5:4/36 6:5/36 7:6/36
8:5/36 9:4/36 10:3/36 11:2/36 12:1/36
Can you find other sets of dice that yield this same probability table?

Source: Original, based upon a puzzle from Ken Burres' Math Problem of the Week.


Solutions were received from: Nick Baxter, Jon Abraham, and Kirk Bresniker.

Several solutions are below, followed by Nick Baxter's thorough analysis. I know this list is not exhausted, yet, so I'd be happy to add to it, or receive a note that shows the full possible list, using the minimum number of zeros.

One Die
[2 3 3 4 4 4 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 9 9 9 9 10 10 10 11 11 12]
Two Dice
[0 1 2 3 4 5] [2 3 4 5 6 7]   (included for reference, not minimum zeros)
[1 2 3 4 5 6] [1 2 3 4 5 6]
[1 2 2 3 3 4] [1 3 4 5 6 8]
[1 2 4 5]     [1 2 3 3 4 5 5 6 7]
[1 2 2 3]     [1 3 3 5 5 5 7 7 9]
[1 4 4 7]     [1 2 2 3 3 3 4 4 5]
[1 2 3]       [1 2 3 4 4 5 5 6 6 7 8 9]
[1 2]         [1 2 3 3 4 4 5 5 5 6 6 6 7 7 8 8 9 10]
Three Dice
[0 2 4]  [1 3 5]    [1 2 2 3]
[0 1]    [1 2 3]    [1 3 4 5 6 8]
[0 3]    [2 3 4]    [0 1 2 3 4 5]    (not minimum zeros)
[1 4]    [0 1 2]    [1 2 3 4 5 6]
[0 3]    [1 4]      [1 2 2 3 3 3 4 4 5]
Four Dice
[0 1]     [1 2]     [0 2 4]     [1 3 5]
[0 3]     [1 2]     [0 2 4]     [1 2 3]
[0 3]     [1 4]     [0 1 2]     [1 2 3]
[1 4]     [1 4]     [0 1 2]     [0 1 2]

Nick's analysis:
>On Jun 13,  5:16pm, Nick Baxter wrote:
>> Subject: Alternative Dice
>> The probability distrbution for standard dice can be
>> generated by powers of the polynomial d(x)=(1+x+x^2+x^3+x^4+x^5).
>> To solve this problem, we need to final factorizations
>> of f(x)=1+2x+3x^2...+2x^9+x^10 into two polynomials a(x) and b(x),
>> other than d(x)^2, such that a(x) and b(x) have non-negative
>> coefficients and a(1)=b(1)=6.
>>
>> f(x) = d(x)^2 = (x^6-1)^2/(x-1)^2
>>      = [ (x+1)(x^2+x+1)(x^2-x+1) ]^2
>>      = [ (x+1)(x^2+x+1)(x^2-x+1)^2 ][ (x+1)(x^2+x+1) ]
>>              (this is the only way to partition the factors so
>>               a(1)=b(1)=6 (2x3) and a(x),b(x) not the same as d(x))
>>      = (1+x^2+x^3+x^4+x^5+x^7)(1+2x+2x^2+x^3)
>>
>> Thus, the two dice with faces (1,3,4,5,6,8) and (1,2,2,3,3,4)
>> give the same probability distribution as two (1,2,3,4,5,6) dice.
>>
>> Nick Baxter

The values of x really aren't important here, it's the coefficients of the
polynomial that are key (d(1) is the sum of the coefficients, so that 
particular value is interesting, but only by coincidence!).  Later I will
explain that the value of x can actually be useful.  But, let me get to
the key issues for this problem.

Full disclosure: p(x), a polynomial of a single variable with non-negative
coefficients, can be used as a generating function for its probability
distribution.  Ax^i represents A occurences of the face containing i
pips.  Obviously now, p(1) is the total number of faces.  The key 
feature is that multiplying two such polynomials will give the distribution
of the sums of the corresponding two dice for all possible combinations
of a single roll of those dice.  This works because the exponents in the
sum correspond to the total number of ways that the two dice can be paired
to make the same number of pips.  (1+x) is the generating function for
a two-sided coin.  That is why Pascal's Triangle gives you the coefficients
of (1+x)^n, as well as the distribution of heads/tails conbinations for
n tosses.

Standard dice would normally be represented as (x+x^2+...+x^6).  In the
solution I gave you before (below), I simplified it a bit and removed
the extra factor of x^2 since I was assuming two dice.  In the new 
examples below, I remove that assumption.

Nevertheless, some assumptions need to be made about the range of values
appearing on the dice.  The two 6-faced dice with values (0,1,2,3,4,5) and
(2,3,4,5,6,7) have the same distribution as "normal" dice.  This simple
transformation is equivalent to moving a factor of x from one generating
polynomial to the other!  I could have used x^10, and get the dice
(-9,-8,-7,-6,-5,-4) and (11,12,13,14,15,16) -- also with the same 
distribution.  Clearly these dice, as a pair, are equivalent to the 
original pair, and in my mind, don't constitute a uniquely different pair.

So, I will generally use dice with 0 as the lowest value, and indicate
the necessary increments for the dice in question.


>Why did you assume a(1)=b(1)=6?

I was taking the normal definition of dice, and assumed you wanted cubes
with 6 faces.   

>What are the x(1) values?  They appear to be
>the number of sides on the dice.  If we don't assume they have to be
equal, or
>equal to 6, can we then find sets of >2 dice?

Sure.  As I said above, since I assumed 2 dice, I removed the factors of
x in the generating functions, since they were going to get multiplied 
right back into the two solution dice, assuming the standard convention
that the faces all have positive values.  

So, a more general approach would be
f(x) = x^2(x+1)(x+1)(x^2-x+1)(x^2-x+1)(x^2+x+1)(x^2+x+1)

We have a physical constraint that a negative number of faces is meaningless,
so, at a minimum, we must combine terms so that there are no negative
coefficients.  There are 3 base configurations to build from:
f(x) = x^2(x+1)(x^3+1)(x^4+x^2+1)(x^2+x+1)
     = x^2(x^3+1)(x^3+1)(x^2+x+1)(x^2+x+1)
     = x^2(x^4+x^2+1)(x^4+x^2+1)(x+1)(x+1)

Assuming two dice, there are 5 factorizations into 2 polynomials
(where each contain a factor of x):
f(x) = (x+x^2+x^4+x^5)(x+x^2+2x^3+x^4+2x^5+x^6+x^7)
     = (x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6)
     = (x+2x^2+2x^3+x^4)(x+x^x+x^4+x^5+x^6+x^8)
     = (x+2x^4+x^7)(x+2x^2+3x^3+2x^4+x^5)
     = (x+2x^x+x^3)(x+2x^3+3x^5+2x^7+x^9)

This corresponds to:
[1 2 4 5][1 2 3 3 4 5 5 6 7]
[1 2 3 4 5 6][1 2 3 4 5 6]
[1 2 2 3 3 4][1 3 4 5 6 8]
[1 4 4 7][1 2 2 3 3 3 4 4 5]
[1 2 2 3][1 3 3 5 5 5 7 7 9]

The second and third cases are the cubical solutions.  The others all
use a 4-faced (tetrahedron?) and a 9-faced (good luck!) die.

Simply by combining few terms in the 3 base configurations above,
you can get solutions with more than 2 dice.  However, you will 
necessarily have faces with 0 pips.

Since f(x)=(x+x^2)(1+x^3)(1+x^2+x^4)(x+x^2+x^3), 
we get the dice [1 2][0 3][0 2 4][1 2 3].  There are a lot of
solutions following this path!


Now, on to a slightly more interesting area, beyond the scope of 
this problem.  I mentioned above that (1+x) is the generating
function for a two-sided coin.  To be precise, this works for a
FAIR coin.  Let's say p=P(heads) and q=P(tails), and let's not
worry about whether or not p+q=1, the generating function is
now f(p,q)=px+qy.  f^n will give you the probability 
distribution for n tosses of the coin!  Typically this is 
simplified to f=p+q, and the x and y are assumed, but this gets
less obvious when the number of variables is more than 2.

Let's say the standard dice are not fair, with probabilities
a,b,c,d,e,f that each of the faces 1-6 appear.  Then
f(x)=ax+bx^2+cx^3+dx^4+ex5+fx^6 is now the generating
function.  f(1)=1 holds true when a+b+c+d+e+f=1.  

For dice, the values of the rolled dice are added to produce
a single outcome for any roll.  If this is not the case, then
the generating function may be something like f(x,y,z)=x+y+z.

Enjoy!
Nick

Mail to Ken