Problem 205: Dice Game

Mathematical Foundation

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 given by the $n$-fold convolution:

where $f_{X_i}(k) = 1/d$ for $k \in \{1, \ldots, d\}$ and $0$ otherwise. Equivalently, the number of ways to write $s = k_1 + \cdots + k_n$ with each $k_i \in \{1, \ldots, d\}$ is the coefficient of $x^s$ in $(x + x^2 + \cdots + x^d)^n$.

Proof. For independent discrete random variables, the PMF of the sum is the convolution of the individual PMFs. This follows from the law of total probability: $P(S_n = s) = \sum_{k=1}^{d} P(S_{n-1} = s - k) \cdot P(X_n = k)$, which is precisely the convolution formula. The generating function representation follows from the product rule for generating functions of independent variables. $\square$

Theorem (Winning Probability). Let $P$ denote Peter’s total (sum of 9 dice with $d=4$) and $C$ denote Colin’s total (sum of 6 dice with $d=6$). Then:

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

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

Writing $\Pr(P = p) = f_P(p)/4^9$ and $\Pr(C < p) = \Pr(C \leq p-1) = F_C(p-1)/6^6$, we obtain the claimed formula. $\square$

Lemma (Range Constraints). Peter’s sum ranges over $[9, 36]$ ($4^9 = 262144$ total outcomes). Colin’s sum ranges over $[6, 36]$ ($6^6 = 46656$ total outcomes).

Proof. The minimum of $n$ dice each showing at least 1 is $n$; the maximum with faces up to $d$ is $nd$. For Peter: $n=9, d=4$ gives $[9, 36]$. For Colin: $n=6, d=6$ gives $[6, 36]$. $\square$

Editorial

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. We compute f_P[9..36]: frequency distribution for sum of 9 four-sided dice. We then compute f_C[6..36]: frequency distribution for sum of 6 six-sided dice. Finally, compute cumulative F_C[t] = sum of f_C[6..t] for t = 6..36.

Pseudocode

Input: Peter has 9d4, Colin has 6d6
Output: P(Peter > Colin) rounded to 7 decimal places
Compute f_P[9..36]: frequency distribution for sum of 9 four-sided dice
Compute f_C[6..36]: frequency distribution for sum of 6 six-sided dice
Compute cumulative F_C[t] = sum of f_C[6..t] for t = 6..36
winning_count = sum over p = 9..36 of f_P[p] * F_C[p-1]
probability = winning_count / (4^9 * 6^6)
Return round(probability, 7)

Complexity Analysis

• Time: $O(n_P \cdot d_P \cdot s_{\max} + n_C \cdot d_C \cdot s_{\max} + s_{\max})$ for the convolutions and final summation, where $s_{\max} = 36$. This is $O(9 \cdot 4 \cdot 36 + 6 \cdot 6 \cdot 36 + 36) = O(2628)$, effectively $O(1)$.
• Space: $O(s_{\max}) = O(36)$, effectively $O(1)$.

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()