The Universe of Discourse | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
12 recent entries Archive:
Comments disabled |
Tue, 07 Aug 2007
Different arrangements for standard dice
To understand just what is being asked for here, first observe that a standard pair of dice throws a 2 exactly 1/36 of the time, a 3 exactly 2/36 of the time, and so forth:
The standard dice have faces numbered 1, 2, 3, 4, 5, and 6. It should be clear that if one die had {0,1,2,3,4,5} instead, and the other had {2,3,4,5,6,7}, then the probabilities would be exactly the same. Similarly you could subtract 3.7 from every face of one die, giving it labels {-2.7, -1.7, -0.7, 0.3, 1.3, 2.3}, and if you added the 3.7 to every face of the other die, giving labels {4.7, 5.7, 6.7, 7.7, 8.7, 9.7}, you'd still have the same chance of getting any particular total. For example, there are still exactly 2 ways out of 36 possible rolls to get the total 3: you can roll -2.7 + 5.7, or you can roll -1.7 + 4.7. But the question is to find a nontrivial relabeling. Like many combinatorial problems, this one is best solved with generating functions. Suppose we represent a die as a polynomial. If the polynomial is Σa_{i}x^{i}, it represents a die that has a_{i} chances to produce the value i. A standard die is x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x, with one chance to produce each integer from 1 to 6. (We can deal with probabilities instead of "chances" by requiring that Σa_{i} = 1, but it comes to pretty much the same thing.) The reason it's useful to adopt this representation is that rolling the dice together corresponds to multiplication of the polynomials. Rolling two dice together, we multiply (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x) by itself and get P(x) = x^{12} + 2x^{11} + 3x^{10} + 4x^{9} + 5x^{8} + 6x^{7} + 5x^{6} + 4x^{5} + 3x^{4} + 2x^{3} + x^{2}, which gives the chances of getting any particular sum; the coefficient of the x^{9} term is 4, so there are 4 ways to roll a 9 on two dice. What we want is a factorization of this 12th-degree polynomial into two polynomials Q(x) and R(x) with non-negative coefficients. We also want Q(1) = R(1) = 6, which forces the corresponding dice to have 6 faces each. Since we already know that P(x) = (x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x)^{2}, it's not hard; we really only have to factor x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x and then see if there's any suitable way of rearranging the factors. x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x = x(x^{4} + x^{2} + 1)(x + 1) = x(x^{2} + x + 1)(x^{2} - x + 1)(x + 1). So P(x) has eight factors:
We want to combine these into two products Q(x) and R(x) such that Q(1) = R(1) = 6. If we calculate f(1) for each of these, we get 1, 3 (pink), 1, and 2 (blue). So each of Q and R will require one of the factors that has f(1) = 3 and one that has f(1) = 2; we can distribute the f(1) = 1 factors as needed. For normal dice the way we do this is to assign all the factors in each row to one die. If we want alternative dice, our only real choice is what to do with the x^{2} - x + 1 and x factors. Redistributing the lone x factors just corresponds to subtracting 1 from all the faces of one die and adding it back to all the faces of the other, so we can ignore them. The only interesting question is what to do with the x^{2} - x + 1 factors. The normal distribution assigns one to each die, and the only alternative is to assign both of them to a single die. This gives us the two polynomials:
And so the solution is that one die has faces {1,2,2,3,3,4} and the other has faces {1,3,4,5,6,8}:
Counting up entries in the table, we see that there are indeed 6 ways to throw a 7, 4 ways to throw a 9, and so forth. One could apply similar methods to the problem of making a pair of dice that can't roll 7. Since there are six chances in 36 of rolling 7, we need to say what will happen instead in these 6 cases. We might distribute them equally among some of the other possibilities, say 2, 4, 6, 8, 10, and 12, so that we want the final distribution of results to correspond to the polynomial 2x^{12} + 2x^{11} + 4x^{10} + 4x^{9} + 6x^{8} + 6x^{6} + 4x^{5} + 4x^{4} + 2x^{3} + 2x^{2}. The important thing to notice here is that the coefficient of the x^{7} term is 0. Now we want to factor this polynomial and proceed as before. Unfortunately, it is irreducible. (Except for the trivial factor of x^{2}.) Several other possibilities are similarly irreducible. It's tempting to reason from the dice to the algebra, and conjecture that any reducible polynomial that has a zero x^{7} term must be rather exceptional in other ways, such as by having only even exponents. But I'm not sure it will work, because the polynomials are more general than the dice: the polynomials can have negative coefficients, which are meaningless for the dice. Still, I can fantasize that there might be some result of this type available, and I can even imagine a couple of ways of getting to this result, one combinatorial, another based on Fourier transforms. But I've noticed that I have a tendency to want to leave articles unpublished until I finish exploring all possible aspects of them, and I'd like to change that habit, so I'll stop here, for now. [ Addendum 20070905: There are some followup notes. ]
[Other articles in category /math] permanent link |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||