Problem 205: Dice Game

Mathematical Development

Theorem (Convolution of Discrete Uniform Distributions). Let $X_1, X_2, \ldots, X_n$ be independent random variables, each uniformly distributed on $\{1, 2, \ldots, d\}$. The probability mass function of $S_n = \sum_{i=1}^{n} X_i$ is the $n$-fold convolution of the individual distributions. Equivalently, the number of ways to realize total $s$ is the coefficient of $x^s$ in $(x + x^2 + \cdots + x^d)^n$.

Proof. For independent discrete random variables, the probability mass function of the sum is obtained by convolution. The generating-function statement is the coefficient form of the same recurrence. $\square$

Theorem (Winning Probability). Let $P$ be Peter’s total and $C$ be Colin’s total. Then

where $f_P(p)$ is the number of Peter outcomes with total $p$, and $F_C(t) = \sum_{c=6}^{t} f_C(c)$ is Colin’s cumulative frequency table.

Proof. Since $P$ and $C$ are independent,

Writing these probabilities in terms of outcome counts yields the stated formula. $\square$

Lemma (Range Constraints). Peter’s sum lies in $[9, 36]$ and Colin’s sum lies in $[6, 36]$.

Proof. The minimum of $n$ dice is $n$, and the maximum is $nd$. $\square$

Editorial

The clean approach is to compute the exact sum distribution for each player. Repeated convolution gives the number of ways Peter can make each total from 9 to 36 and the number of ways Colin can make each total from 6 to 36.

After that, the probability calculation is just bookkeeping. For a fixed Peter total $p$, every Colin total below $p$ is a win, so a cumulative table for Colin turns the double sum into a single pass over Peter’s distribution. Dividing the final win count by $4^9 6^6$ gives the exact probability, which is then rounded to seven decimals.

Pseudocode

BuildDistribution(number_of_dice, faces):
    Start with freq[0] = 1.
    Repeat once per die:
        Create an empty table next.
        For every current sum s with frequency count:
            For face from 1 to faces:
                Add count to next[s + face].
        Replace freq by next.
    Return freq

Let peter = BuildDistribution(9, 4).
Let colin = BuildDistribution(6, 6).

Build a cumulative table smaller_colin where smaller_colin[p]
is the number of Colin outcomes with total strictly less than p.

winning_count = 0
For each Peter total p:
    winning_count += peter[p] * smaller_colin[p]

Return winning_count / (4^9 * 6^6), rounded to seven decimals

Complexity Analysis

• Time: $O(n_P d_P s_{\max} + n_C d_C s_{\max} + s_{\max})$, where $s_{\max} = 36$.
• Space: $O(s_{\max})$ for the two distribution tables and Colin’s cumulative table.

Answer

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

int main(){
    // Peter: 9 four-sided dice. Colin: 6 six-sided dice.
    // P(Peter > Colin) rounded to 7 decimal places.

    // Compute frequency distribution for sum of n dice with faces 1..f
    auto dice_dist = [](int n, int f) -> vector<long long> {
        int maxsum = n * f;
        vector<long long> freq(maxsum + 1, 0);
        freq[0] = 1;
        for(int die = 0; die < n; die++){
            vector<long long> nf(maxsum + 1, 0);
            for(int s = 0; s <= maxsum; s++){
                if(freq[s] == 0) continue;
                for(int face = 1; face <= f && s + face <= maxsum; face++){
                    nf[s + face] += freq[s];
                }
            }
            freq = nf;
        }
        return freq;
    };

    auto peter = dice_dist(9, 4);  // indices 0..36, nonzero for 9..36
    auto colin = dice_dist(6, 6);  // indices 0..36, nonzero for 6..36

    // Cumulative sum for Colin
    vector<long long> colin_cum(37, 0);
    for(int s = 1; s <= 36; s++){
        colin_cum[s] = colin_cum[s-1] + colin[s];
    }

    // P(Peter > Colin) = sum over p of peter[p] * colin_cum[p-1]
    long long win = 0;
    for(int p = 9; p <= 36; p++){
        win += peter[p] * colin_cum[p-1];
    }

    double total = (double)(1LL << 18) * 46656.0; // 4^9 * 6^6 = 262144 * 46656
    double prob = (double)win / (262144.0 * 46656.0);

    cout << fixed << setprecision(7) << prob << endl;
    return 0;
}

"""
Problem 205: Dice Game

Peter has 9 four-sided dice; Colin has 6 six-sided dice.
Find P(Peter beats Colin), rounded to 7 decimal places.

Compute sum distributions via convolution, then sum over all (p, c) pairs
where Peter's total p > Colin's total c.
"""

def solve():
    from itertools import product as iprod

    def dice_distribution(n_dice, faces):
        """Compute frequency distribution for sum of n_dice dice with given faces."""
        freq = {0: 1}
        for _ in range(n_dice):
            new_freq = {}
            for s, cnt in freq.items():
                for f in range(1, faces + 1):
                    new_freq[s + f] = new_freq.get(s + f, 0) + cnt
            freq = new_freq
        return freq

    peter = dice_distribution(9, 4)   # sums 9..36
    colin = dice_distribution(6, 6)   # sums 6..36

    # Cumulative distribution for Colin: P(Colin < p)
    colin_cum = {}
    running = 0
    for s in range(0, 37):
        colin_cum[s] = running
        running += colin.get(s, 0)

    # P(Peter wins) = sum_p peter[p] * colin_cum[p] / (4^9 * 6^6)
    win_count = sum(peter[p] * colin_cum[p] for p in peter)

    total = (4**9) * (6**6)
    prob = win_count / total

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

if __name__ == "__main__":
    solve()