Project Euler Problem 240

Solution

Answer: 7448717393364181966

Let the $20$ dice rolls be reordered in nonincreasing order:

$$x_1 \ge x_2 \ge \cdots \ge x_{20},$$

where each $x_i \in {1,\dots,12}$.

The condition in the problem is

$$x_1+x_2+\cdots+x_{10}=70.$$

The key observation is that the order of the dice only matters at the very end.

It is much easier to count by multiplicities of each face value.

---

1. Mathematical analysis

Suppose:

$$c_v = \text{number of dice showing value } v$$

for $v=1,\dots,12$.

Then:

$$c_1+c_2+\cdots+c_{12}=20.$$

For any fixed multiplicity vector $(c_1,\dots,c_{12})$, the number of ordered rolls is

$$\frac{20!}{c_1!c_2!\cdots c_{12}!}.$$

So the problem reduces to:

Which multiplicity vectors have the property that the ten largest dice sum to $70$?

---

Determining the contribution of each value to the top ten

Process values from high to low.

Suppose we are considering value $v$.

Let

$$H_v = c_{v+1}+c_{v+2}+\cdots+c_{12}$$

be the number of dice strictly larger than $v$.

Then among the $c_v$ dice equal to $v$, exactly

$$t_v = \min(c_v,; 10-H_v)$$

belong to the top ten (provided $H_v<10$; otherwise none do).

Hence the top-ten sum condition becomes

$$\sum_{v=1}^{12} v, t_v = 70.$$

So we simply enumerate all multiplicity vectors satisfying:

• total dice = $20$,
• induced top-ten sum = $70$,

and accumulate

$$\frac{20!}{\prod_v c_v!}.$$

---

2. Python implementation

from math import factorial

def count_ways(num_dice, sides, top_count, target_sum):
    fact = [factorial(i) for i in range(num_dice + 1)]

    answer = 0

    def search(v, remaining_dice, top_used, top_sum, counts):
        """
        v               current face value being assigned
        remaining_dice  dice still unassigned
        top_used        how many of the top dice are already determined
        top_sum         current sum of the top dice
        counts          list of multiplicities chosen so far
        """
        nonlocal answer

        # Finished assigning all face values
        if v == 0:
            if (
                remaining_dice == 0
                and top_used == top_count
                and top_sum == target_sum
            ):
                ways = fact[num_dice]
                for c in counts:
                    ways //= fact[c]
                answer += ways
            return

        # Try all possible counts for face value v
        for c in range(remaining_dice + 1):

            # How many of these c dice appear in the top group?
            take = min(c, max(0, top_count - top_used))

            new_sum = top_sum + v * take

            # Prune impossible branches
            if new_sum > target_sum:
                break

            counts.append(c)

            search(
                v - 1,
                remaining_dice - c,
                top_used + take,
                new_sum,
                counts,
            )

            counts.pop()

    search(sides, num_dice, 0, 0, [])

    return answer

# Check the small example from the statement
print(count_ways(5, 6, 3, 15))

# Solve the actual problem
print(count_ways(20, 12, 10, 70))

---

3. Code walkthrough

Factorials

fact = [factorial(i) for i in range(num_dice + 1)]

Precomputes factorials so multinomial coefficients can be evaluated quickly.

---

Recursive search

We assign counts for values $12,11,\dots,1$.

At each stage:

for c in range(remaining_dice + 1):

we choose how many dice show value $v$.

---

Determining how many belong to the top ten

take = min(c, max(0, top_count - top_used))

If fewer than ten larger dice already exist, some of the current value-$v$ dice enter the top group.

---

Updating the top-ten sum

new_sum = top_sum + v * take

adds the contribution from the current value.

---

Counting arrangements

Once a valid multiplicity vector is found:

ways = fact[num_dice]
for c in counts:
    ways //= fact[c]

computes

$$\frac{20!}{\prod c_v!}.$$

---

4. Verification

The sample case in the problem statement gives:

$$1111$$

which the program reproduces exactly.

The final answer is approximately $7.45\times10^{18}$, which is reasonable because:

• there are $12^{20} \approx 3.83\times10^{21}$ total rolls,
• the condition on the top ten is restrictive but still leaves many possibilities.

Everything is consistent.

---

Answer: 7448717393364181966