Problem 493: Under the Rainbow

Mathematical Foundation

Theorem 1 (Linearity of expectation for indicator variables). Let $X = \sum_{i=1}^{n} X_i$ where each $X_i$ is an indicator random variable. Then $E[X] = \sum_{i=1}^{n} P(X_i = 1)$, regardless of dependence among the $X_i$.

Proof. By the linearity of expectation, $E[X] = E\left[\sum_{i=1}^{n} X_i\right] = \sum_{i=1}^{n} E[X_i]$. Since $X_i \in \{0, 1\}$, $E[X_i] = P(X_i = 1)$. $\square$

Theorem 2 (Expected distinct colors). Let $D$ be the number of distinct colors among 20 balls drawn without replacement from an urn of 70 balls (10 of each of 7 colors). Then

Proof. For each color $i \in \{1, \ldots, 7\}$, define $X_i = \mathbf{1}[\text{color } i \text{ is present in the draw}]$. Then $D = \sum_{i=1}^{7} X_i$. By Theorem 1:

by symmetry (all colors are interchangeable). The complement is:

since there are $\binom{60}{20}$ ways to choose 20 balls from the 60 non-color-1 balls, out of $\binom{70}{20}$ total ways. Hence $P(X_1 = 1) = 1 - \binom{60}{20}/\binom{70}{20}$, and the result follows. $\square$

Lemma 1 (Product formula for the ratio). The binomial ratio simplifies as:

Proof. We have $\binom{60}{20}/\binom{70}{20} = \frac{60!}{40!} \cdot \frac{50!}{70!}$. Writing this as a ratio of falling factorials:

The numerator has factors $41, 42, \ldots, 50, 51, \ldots, 60$ and the denominator has $51, 52, \ldots, 70$. The common factors $51, \ldots, 60$ cancel, leaving $\prod_{k=0}^{9}(50 - k)/\prod_{k=0}^{9}(70 - k)$. $\square$

Editorial

We enumerate the admissible parameter range, discard candidates that violate the derived bounds or arithmetic constraints, and update the final set or total whenever a candidate passes the acceptance test.

Pseudocode

ratio = 1
For k from 0 to 9:
    ratio *= (50 - k) / (70 - k)
answer = 7 * (1 - ratio)
output answer rounded to 9 decimal places

Complexity Analysis

• Time: $O(1)$ — a fixed product of 10 terms and one subtraction/multiplication.
• Space: $O(1)$.

Answer

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

int main(){
    // E[distinct colors] = 7 * (1 - C(60,20)/C(70,20))
    // C(60,20)/C(70,20) = prod_{k=0}^{9} (50-k)/(70-k)

    // Use exact rational arithmetic with long doubles or fractions
    // For precision, compute with exact fractions using __int128 or just careful doubles

    // Actually, let's use exact rational computation
    // Numerator: 50*49*48*47*46*45*44*43*42*41
    // Denominator: 70*69*68*67*66*65*64*63*62*61

    // These fit in unsigned long long
    // num = 50*49*48*47*46*45*44*43*42*41
    // den = 70*69*68*67*66*65*64*63*62*61

    // For exact decimal, use high-precision approach
    // But we can use long double which has ~18 digits of precision

    long double ratio = 1.0L;
    for(int k = 0; k < 10; k++){
        ratio *= (long double)(50 - k) / (long double)(70 - k);
    }

    long double answer = 7.0L * (1.0L - ratio);

    cout << fixed << setprecision(9) << answer << endl;

    return 0;
}

from fractions import Fraction
from math import comb

def solve():
    """
    Expected number of distinct colors when drawing 20 balls from 70
    (10 each of 7 colors).

    E = 7 * (1 - C(60,20)/C(70,20))
    """
    # Use exact rational arithmetic
    ratio = Fraction(comb(60, 20), comb(70, 20))
    expected = 7 * (1 - ratio)

    # Convert to decimal with 9 places
    # expected is a Fraction
    # We need to print with exactly 9 decimal places
    numerator = expected.numerator
    denominator = expected.denominator

    # Integer part
    integer_part = numerator // denominator
    remainder = numerator % denominator

    # Decimal part: multiply remainder by 10^9, divide by denominator
    decimal_part = (remainder * 10**9) // denominator

    # Check rounding
    next_digit = (remainder * 10**10) // denominator % 10
    if next_digit >= 5:
        decimal_part += 1

    print(f"{integer_part}.{decimal_part:09d}")

solve()