Project Euler

Top Dice

In how many ways can 20 twelve-sided dice (sides numbered 1 to 12) be rolled so that the top 10 values sum to 70? For reference: there are 1111 ways for 5 six-sided dice where the top 3 sum to 15.

Source sync Apr 19, 2026

Problem #0240

Level Level 09

Solved By 2,511

Languages C++, Python

Answer 7448717393364181966

Length 405 words

probabilitydynamic_programminglinear_algebra

There are $1111$ ways in which five $6$-sided dice (sides numbered $1$ to $6$) can be rolled so that the top three sum to $15$. Some examples are:

$D_1,D_2,D_3,D_4,D_5 = 4,3,6,3,5$

$D_1,D_2,D_3,D_4,D_5 = 4,3,3,5,6$

$D_1,D_2,D_3,D_4,D_5 = 3,3,3,6,6$

$D_1,D_2,D_3,D_4,D_5 = 6,6,3,3,3$

In how many ways can twenty $12$-sided dice (sides numbered $1$ to $12$) be rolled so that the top ten sum to $70$?

Problem 240: Top Dice

Mathematical Foundation

Theorem (Threshold Decomposition). Let $D = 12$ , $N = 20$ , $H = 10$ (number of “top” dice), $S = 70$ (target sum). The number of ordered $N$ -tuples $(d_1, \ldots, d_N) \in \{1, \ldots, D\}^N$ whose $H$ largest values sum to $S$ is

\text{Answer} = \sum_{t=1}^{D} \sum_{j=1}^{H} \sum_{m=0}^{N-H} [j + m \geq 1] \cdot R(H-j, t+1, D, S - jt) \cdot B(N-H-m, 1, t-1) \cdot \frac{N!}{\text{(frequency product)}}

decomposed over the threshold value $t = d_{(H)}$ (the $H$ -th largest value), $j$ = number of top dice equal to $t$ , and $m$ = number of bottom dice equal to $t$ .

Proof. Sort the values: $d_{(1)} \geq d_{(2)} \geq \cdots \geq d_{(N)}$ . The $H$ -th largest value $t = d_{(H)}$ satisfies $1 \leq t \leq D$ . Among the top $H$ dice, exactly $j \geq 1$ have value $t$ , and the remaining $H - j$ have values strictly greater than $t$ , summing to $S - jt$ . Among the bottom $N - H$ dice, exactly $m \geq 0$ have value $t$ , and the remaining $N - H - m$ have values strictly less than $t$ .

For each valid $(t, j, m)$ :

The $H - j$ “above-threshold” top dice contribute values from $\{t+1, \ldots, D\}$ summing to $S - jt$ . Let $R(h, a, b, s)$ denote the number of multisets of $h$ values from $\{a, \ldots, b\}$ summing to $s$ .
The $N - H - m$ “below-threshold” bottom dice contribute values from $\{1, \ldots, t-1\}$ .
There are $j + m$ dice with value exactly $t$ .

The number of ordered tuples for a given frequency vector $(n_1, \ldots, n_D)$ is the multinomial coefficient $N! / \prod_{v=1}^{D} n_v!$ . Summing over all valid frequency vectors gives the total count. $\square$

Lemma (Stars-and-Bars with Bounds). The count $R(h, a, b, s)$ of multisets of $h$ values from $\{a, \ldots, b\}$ summing to $s$ can be computed via dynamic programming on the recurrence

R(h, a, b, s) = \sum_{v=a}^{\min(b, s)} R(h-1, v, b, s-v)

with base case $R(0, a, b, 0) = 1$ and $R(0, a, b, s) = 0$ for $s > 0$ .

Proof. Fix the smallest value in the multiset as $v \in \{a, \ldots, b\}$ , subtract it from the sum, and recurse on the remaining $h-1$ values (each $\geq v$ ). The base case handles the empty multiset. $\square$

Editorial

How many ways can 20 twelve-sided dice be rolled so that the top 10 sum to 70? Approach: Enumerate sorted dice configurations (frequency vectors). For each face value from 12 down to 1, decide how many dice show that value. The top-10 sum is determined by the sorted order. For a non-increasing sequence d_1 >= d_2 >= … >= d_20, the top 10 are d_1,…,d_10. Their sum must equal 70. We recurse on face value from 12 down to 1, tracking: At each face value, the count of dice with that value determines how many go to the “top” part (they fill from the top first in descending order). We enumerate frequency vectors for top dice above threshold.

Pseudocode

Enumerate frequency vectors for top dice above threshold
Enumerate bottom dice: (N-H) dice with values in {1,...,t}

Complexity Analysis

Time: $O(D^2 \cdot N \cdot S)$ for the DP-based enumeration of frequency vectors. In practice, the number of valid frequency vectors is bounded and the computation is tractable.
Space: $O(N \cdot S)$ for the DP tables used in computing multiset counts.

Answer

\boxed{7448717393364181966}

C++ project_euler/problem_240/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 240: Top Dice
 *
 * How many ways can 20 twelve-sided dice be rolled so that the top 10 sum to 70?
 *
 * Approach: Enumerate sorted configurations (frequency vectors) by recursing
 * on face values from 12 down to 1, tracking top-10 sum.
 * For each valid configuration, add the multinomial coefficient 20!/prod(n_i!).
 */

typedef long long ll;
typedef unsigned long long ull;

const int NUM_DICE = 20;
const int NUM_SIDES = 12;
const int TOP_COUNT = 10;
const int TARGET = 70;

ll fact[NUM_DICE + 1];
ull total_answer;

void assign_bottom(int face, int dice_left, ll mult_denom) {
    if (dice_left == 0) {
        total_answer += fact[NUM_DICE] / mult_denom;
        return;
    }
    if (face == 0) return;
    if (face == 1) {
        total_answer += fact[NUM_DICE] / (mult_denom * fact[dice_left]);
        return;
    }
    for (int count = 0; count <= dice_left; count++) {
        assign_bottom(face - 1, dice_left - count, mult_denom * fact[count]);
    }
}

void recurse(int face, int dice_left, int top_left, int sum_left, ll mult_denom) {
    if (top_left == 0 && sum_left != 0) return;
    if (top_left == 0 && sum_left == 0) {
        assign_bottom(face, dice_left, mult_denom);
        return;
    }
    if (face == 0) {
        if (dice_left == 0 && top_left == 0 && sum_left == 0)
            total_answer += fact[NUM_DICE] / mult_denom;
        return;
    }
    if (dice_left < top_left) return;
    if ((ll)top_left * face < sum_left) return;
    if (sum_left < top_left) return;

    for (int count = 0; count <= dice_left; count++) {
        int top_from = min(count, top_left);
        int new_top = top_left - top_from;
        int new_sum = sum_left - top_from * face;
        if (new_sum < 0) break;

        recurse(face - 1, dice_left - count, new_top, new_sum,
                mult_denom * fact[count]);
    }
}

int main(){
    fact[0] = 1;
    for (int i = 1; i <= NUM_DICE; i++)
        fact[i] = fact[i-1] * i;

    total_answer = 0;
    recurse(NUM_SIDES, NUM_DICE, TOP_COUNT, TARGET, 1);

    cout << total_answer << endl;
    return 0;
}

Python project_euler/problem_240/solution.py

"""
Problem 240: Top Dice

How many ways can 20 twelve-sided dice be rolled so that the top 10 sum to 70?

Approach: Enumerate sorted dice configurations (frequency vectors).
For each face value from 12 down to 1, decide how many dice show that value.
The top-10 sum is determined by the sorted order.

For a non-increasing sequence d_1 >= d_2 >= ... >= d_20, the top 10 are d_1,...,d_10.
Their sum must equal 70.

We recurse on face value from 12 down to 1, tracking:
- Total dice assigned so far
- How many of those are in the top 10 (the first 10 positions)
- Sum of the top-10 portion

At each face value, the count of dice with that value determines how many
go to the "top" part (they fill from the top first in descending order).
"""

from math import factorial

def solve(num_dice, num_sides, top_count, target_sum):
    fact = [1] * (num_dice + 1)
    for i in range(1, num_dice + 1):
        fact[i] = fact[i-1] * i

    total = 0

    def recurse(face, dice_left, top_left, sum_left, multinomial_denom):
        """
        face: current face value (descending from num_sides to 1)
        dice_left: dice not yet assigned
        top_left: top-k positions not yet filled
        sum_left: remaining sum needed for top-k
        multinomial_denom: product of count! for each face assigned so far
        """
        nonlocal total

        if top_left == 0 and sum_left != 0:
            return
        if top_left == 0 and sum_left == 0:
            # Top is complete. Remaining dice go to bottom, each <= face.
            # Number of ways to assign dice_left dice with values in {1,...,face}:
            # This is a stars-and-bars with upper bounds problem.
            # We need the multinomial coefficient contribution.
            # Actually, we need to continue assigning to get the full frequency vector.
            if face == 0:
                if dice_left == 0:
                    total += fact[num_dice] // multinomial_denom
                return
            # Assign bottom dice: values from face down to 1
            assign_bottom(face, dice_left, multinomial_denom)
            return

        if face == 0:
            if dice_left == 0 and top_left == 0 and sum_left == 0:
                total += fact[num_dice] // multinomial_denom
            return

        if dice_left < top_left:
            return  # not enough dice to fill top

        # Pruning: max possible sum from remaining top positions
        if top_left * face < sum_left:
            return
        # Min possible sum
        if sum_left < top_left:  # each die is at least 1
            return

        # Choose count of dice with value 'face': 0 to dice_left
        for count in range(dice_left + 1):
            # These 'count' dice have value 'face'.
            # In sorted order, they fill top positions first.
            top_from_this = min(count, top_left)
            # This is fixed: we MUST put min(count, top_left) into top.
            # No choice here -- in sorted order, higher values come first.

            new_top_left = top_left - top_from_this
            new_sum = sum_left - top_from_this * face
            new_dice = dice_left - count

            if new_sum < 0:
                break

            recurse(face - 1, new_dice, new_top_left, new_sum,
                    multinomial_denom * fact[count])

    def assign_bottom(face, dice_left, multinomial_denom):
        """Assign remaining bottom dice with values in {1, ..., face}."""
        nonlocal total
        if dice_left == 0:
            total += fact[num_dice] // multinomial_denom
            return
        if face == 0:
            return  # no values left but dice remain
        if face == 1:
            # All remaining dice must be 1
            total += fact[num_dice] // (multinomial_denom * fact[dice_left])
            return
        # Pruning: need at least dice_left dice, each at least 1. Always satisfiable if face >= 1.
        for count in range(dice_left + 1):
            assign_bottom(face - 1, dice_left - count, multinomial_denom * fact[count])

    recurse(num_sides, num_dice, top_count, target_sum, 1)
    return total

# Verify
small = solve(5, 6, 3, 15)
print(f"Verification (5d6, top 3 = 15): {small}")
assert small == 1111, f"Expected 1111, got {small}"

# Solve
answer = solve(20, 12, 10, 70)
print(answer)