Project Euler Problem 205

Solution

Answer: 0.5731441

Let Peter’s total be $P$ and Colin’s total be $C$.

We want

$$\Pr(P>C).$$

Peter rolls $9$ four-sided dice, so:

$$P = X_1+\cdots+X_9, \qquad X_i\in{1,2,3,4}.$$

Colin rolls $6$ six-sided dice, so:

$$C = Y_1+\cdots+Y_6, \qquad Y_i\in{1,2,3,4,5,6}.$$

The key idea is:

1. Compute the distribution of all possible sums for Peter.
2. Compute the distribution of all possible sums for Colin.
3. Count all winning pairs $(p,c)$ with $p>c$.
4. Divide by the total number of outcomes.

---

1. Counting dice sums

For independent dice, the distribution can be built incrementally.

If ways[s] is the number of ways to obtain sum $s$, then after adding another die with faces $1$ to $k$,

$$\text{new_ways}[s+f] += \text{ways}[s]$$

for every face $f\in{1,\dots,k}$.

This is a standard convolution/dynamic-programming approach.

---

2. Peter’s distribution

Each of Peter’s dice has 4 faces.

Initially:

$$\text{ways}_0(0)=1.$$

After processing 9 dice we obtain the number of ways to make each total from $9$ to $36$.

Total outcomes:

$$4^9 = 262144.$$

---

3. Colin’s distribution

Similarly, Colin has 6 six-sided dice.

Possible sums range from $6$ to $36$.

Total outcomes:

$$6^6 = 46656.$$

---

4. Computing the winning probability

If Peter rolls total $p$, and Colin rolls total $c$, then Peter wins when

$$p>c.$$

Hence

$$\Pr(P>C) = \frac{ \sum_{p>c} N_P(p),N_C(c) }{ 4^9 6^6 },$$

where:

• $N_P(p)$ = number of Peter outcomes summing to $p$,
• $N_C(c)$ = number of Colin outcomes summing to $c$.

---

5. Python implementation

from collections import defaultdict

def distribution(num_dice, faces):
    """
    Return a dictionary:
        sum -> number of ways
    """
    ways = {0: 1}

    for _ in range(num_dice):
        new_ways = defaultdict(int)

        for current_sum, count in ways.items():
            for face in range(1, faces + 1):
                new_ways[current_sum + face] += count

        ways = dict(new_ways)

    return ways

# Peter: 9 four-sided dice
peter = distribution(9, 4)

# Colin: 6 six-sided dice
colin = distribution(6, 6)

# Count winning outcomes
wins = 0

for p_sum, p_count in peter.items():
    for c_sum, c_count in colin.items():
        if p_sum > c_sum:
            wins += p_count * c_count

# Total outcomes
total = (4 ** 9) * (6 ** 6)

probability = wins / total

print(f"{probability:.7f}")

---

6. Code walkthrough

Distribution function

ways = {0: 1}

Before rolling any dice, there is exactly one way to obtain sum 0.

---

For each die:

for _ in range(num_dice):

we create a new distribution.

---

For every existing sum and every possible face:

new_ways[current_sum + face] += count

we add all combinations leading to the new total.

This performs the convolution of distributions.

---

After all dice are processed:

return ways

contains the exact number of ways to obtain every total.

---

7. Verifying correctness on a small case

Suppose both players roll one standard six-sided die.

Then:

• total outcomes = $36$,
• winning outcomes for player A are:

$$5+4+3+2+1 = 15.$$

Hence:

$$\Pr(A>B)=\frac{15}{36}=\frac{5}{12}\approx 0.4166667.$$

The same dynamic-programming code reproduces this exactly, confirming the method.

---

8. Final verification

Peter rolls many dice with lower variance, centered around:

$$9 \times 2.5 = 22.5.$$

Colin’s average is:

$$6 \times 3.5 = 21.$$

Peter’s mean is slightly higher and his totals are more concentrated, so a probability a bit above $0.5$ is reasonable.

The computed value is:

$$0.5731441$$

which matches the expected magnitude.

---

Answer: 0.5731441