Detailed mathematical approach

Problem Summary

Pete rolls nine 4-sided dice, so his total lies between \(9\) and \(36\). Colin rolls six 6-sided dice, so his total lies between \(6\) and \(36\). The task is to compute the exact probability that Pete's total is strictly larger than Colin's total.

A naive enumeration would reason about all \(4^9 \cdot 6^6\) joint outcomes separately. The key simplification is that the full roll sequence does not matter once its sum is known, so the problem can be compressed into two exact sum distributions and one final comparison of those distributions.

Mathematical Approach

The natural state space is not the list of individual face results but the running sum after a given number of dice. That is exactly what the implementations count.

Exact State for One Player

For \(n\) dice with \(s\) sides, let \(D_i(t)\) denote the number of ordered outcomes of the first \(i\) dice whose sum is \(t\). The base state is

$D_0(0)=1,\qquad D_0(t)=0 \text{ for } t\neq 0.$

After \(i\) dice, the only possible sums satisfy \(i \le t \le is\). Another invariant is

$\sum_t D_i(t)=s^i,$

because \(D_i\) counts all ordered outcomes of \(i\) independent \(s\)-sided dice.

For Problem 205, Pete's final table is

$P(p)=D^{(4)}_9(p),\qquad 9\le p\le 36,$

and Colin's final table is

$C(c)=D^{(6)}_6(c),\qquad 6\le c\le 36.$

Adding One Die Produces a Convolution Recurrence

If one more \(s\)-sided die is appended, each old sum \(u\) can move to \(u+1,u+2,\dots,u+s\). Therefore the next row satisfies

$D_{i+1}(t)=\sum_{f=1}^{s} D_i(t-f),$

with impossible indices interpreted as zero. This is the discrete-convolution recurrence implemented in all three languages.

The same statement can be written in generating-function form:

$D_n(t)=[x^t]\,(x+x^2+\cdots+x^s)^n.$

For example, with two 4-sided dice,

$D_2(5)=D_1(4)+D_1(3)+D_1(2)+D_1(1)=4,$

because the ordered pairs \((1,4),(2,3),(3,2),(4,1)\) all contribute to sum \(5\).

Combine the Two Independent Sum Distributions

Once \(P\) and \(C\) are known, the original game becomes a comparison of totals. If Pete reaches \(p\) in \(P(p)\) ways and Colin reaches \(c\) in \(C(c)\) ways, then the joint event \((p,c)\) occurs in

$P(p)\,C(c)$

ways, because the two players roll independently.

The total number of joint outcomes is therefore

$\Omega=\sum_{p=9}^{36}\sum_{c=6}^{36} P(p)C(c)=4^9\cdot 6^6.$

Pete wins exactly when \(p>c\), so the winning count is

$W=\sum_{p=9}^{36}\sum_{c=6}^{36} [p>c]\,P(p)C(c).$

Hence the required probability is

$\Pr(\text{Pete wins})=\frac{W}{\Omega}.$

Ties are excluded automatically because the inequality is strict.

Worked Example: The 1d4 Versus 1d6 Checkpoint

A small version of the same game is useful for sanity checking the recurrence and the final strict comparison. Suppose Pete rolls 1 d4 and Colin rolls 1 d6. Then

$P(1)=P(2)=P(3)=P(4)=1,\qquad C(1)=C(2)=C(3)=C(4)=C(5)=C(6)=1.$

There are \(4\cdot 6=24\) equally weighted joint outcomes. Pete wins for

$ (2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3), $

so \(W=6\) and therefore

$\Pr(\text{Pete wins})=\frac{6}{24}=\frac14.$

This is exactly the same counting principle as the full \(9\) d\(4\) versus \(6\) d\(6\) problem, just on a much smaller state space.

How the Code Works

Building the Distribution Tables

The C++, Python, and Java implementations all keep an array indexed by possible sums. They start from the degenerate distribution concentrated at sum \(0\), then repeat one update per die: allocate a fresh array for the next stage, and for every current sum push its count to the entries obtained by adding face values \(1\) through \(s\).

Running that routine with \((9,4)\) produces Pete's exact count table, and running it with \((6,6)\) produces Colin's exact count table. Although the arrays are sized up to the maximum sum, only the mathematically valid interval carries nonzero values after each stage.

Counting Wins and Normalizing Once

After both tables have been built, the implementation scans every attainable Pete total against every attainable Colin total. For each pair it multiplies the two counts, adds that product to the grand total, and adds it to the win counter only when Pete's total is larger. Only after all counts have been accumulated does the code divide wins by total to obtain the probability.

One implementation also contains a small checkpoint for the 1 d4 versus 1 d6 case, and one version allows the dice parameters to be changed from the command line. Those details are auxiliary; the core algorithm is the same in C++, Python, and Java.

Complexity Analysis

For \(n\) dice with \(s\) sides, the distribution builder performs \(n\) stages, scans sums up to \(ns\), and for each reachable sum tries all \(s\) faces. This yields \(O(n\cdot ns\cdot s)=O(n^2s^2)\) time, or equivalently \(O(n\cdot s\cdot M)\) if \(M=ns\) denotes the largest possible sum. The memory usage is \(O(M)\) for the current and next arrays.

The final comparison phase costs \(O(S_P S_C)\), where \(S_P\) and \(S_C\) are the sizes of Pete's and Colin's sum ranges. In this problem those ranges are tiny: Pete only spans \(9\) through \(36\), and Colin only spans \(6\) through \(36\). That is why the exact method is fast even though the underlying sample space contains more than twelve billion joint outcomes.

Footnotes and References

1. Project Euler Problem 205: Project Euler - Dice Game
2. Probability mass function: Wikipedia - Probability mass function
3. Convolution of probability distributions: Wikipedia - Convolution of probability distributions
4. Probability-generating function: Wikipedia - Probability-generating function