Problem 503: Compromise or Persist

Mathematical Foundation

Theorem 1 (Coupon Collector Variant). Consider a process where Alice draws uniformly at random from $n$ bowls. She collects marbles from non-empty bowls. When she draws an empty bowl, she returns all collected marbles and retains only that bowl’s marble. The expected number of draws to collect $k$ marbles follows a backward-induction recurrence.

Proof. Define the state by the number of marbles currently held, $j \in \{1, \ldots, k\}$, and the number of distinct bowls that have been emptied (equivalently, the current collection). From state $j$ (holding $j$ marbles, having emptied $j$ specific bowls):

• With probability $(n - j)/n$, she picks a bowl still containing its marble, advancing to state $j + 1$.
• With probability $j/n$, she picks an already-emptied bowl, resetting to state $1$ (after returning all marbles and receiving the current bowl’s marble back).

Let $E_j$ denote the expected number of additional draws to reach $k$ marbles from state $j$. Then:

This is a linear system in $E_1, \ldots, E_{k-1}$ solvable by standard techniques. $\square$

Lemma 1 (Harmonic Structure). When the reset sends the player back to state 1, the expected time exhibits harmonic-number-like growth. Specifically, unrolling the recurrence yields:

Iterating the recurrence and solving the resulting linear equation for $E_1$ produces a closed-form involving partial harmonic sums:

(The exact form depends on the precise reset mechanism.)

Proof. Substitute $E_j$ in terms of $E_{j+1}$ and $E_1$ recursively from $j = k-1$ down to $j = 1$. Each step introduces a factor of $n/(n-j)$, yielding the product-sum form. Collecting the $E_1$ terms on one side and solving completes the derivation. $\square$

Theorem 2 (Summation Identity). The aggregate $\sum_{n=1}^{N} P(n)$ (where $P(n) = H_n / n$ in the simplified model) satisfies:

where $H_N = \sum_{k=1}^{N} 1/k$ and $H_N^{(2)} = \sum_{k=1}^{N} 1/k^2$.

Proof. Write $H_n = \sum_{k=1}^{n} 1/k$ and interchange the order of summation:

Split into diagonal ($k = n$) and off-diagonal ($k < n$) terms:

$\square$

Editorial

Optimal stopping / negotiation game with alternating offers. Involves harmonic numbers and backward induction. We compute harmonic numbers H_n and H_n^(2) modularly. Finally, alternative via closed form.

Pseudocode

Compute harmonic numbers H_n and H_n^(2) modularly
Alternative via closed form:
total = (H_N^2 + H_N^(2)) / 2 mod p

Complexity Analysis

• Time: $O(N \log p)$ for the iterative computation with modular inverses (each $\text{modinv}$ costs $O(\log p)$ via Fermat’s little theorem when $p$ is prime).
• Space: $O(1)$ if computing on the fly; $O(N)$ if storing all harmonic prefixes.

Answer

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

int main() {
    // Compute sum of P(n) = H_n / n for n = 1..N
    // where H_n is the n-th harmonic number
    const int N = 1000;
    double harmonic = 0.0;
    double total = 0.0;

    for (int n = 1; n <= N; n++) {
        harmonic += 1.0 / n;
        total += harmonic / n;  // P(n) = H_n / n
    }

    cout << fixed << setprecision(10) << total << endl;

    // Verify with backward induction DP for small n
    int test_n = 5;
    int R = 200;
    vector<double> v(R + 1, 0.0);
    for (int r = 1; r <= R; r++) {
        double best = 0.0;
        for (int s = 1; s <= test_n; s++) {
            double p = (double)s / test_n;
            double payoff = p * ((double)s / test_n) + (1 - p) * v[r - 1];
            best = max(best, payoff);
        }
        v[r] = best;
    }
    cout << "DP verification for n=" << test_n << ": " << v[R] << endl;

    return 0;
}

"""
Problem 503: Compromise or Persist
Optimal stopping / negotiation game with alternating offers.
Involves harmonic numbers and backward induction.
"""

from fractions import Fraction

def harmonic(n: int) -> Fraction:
    """Compute the n-th harmonic number H_n = 1 + 1/2 + ... + 1/n."""
    s = Fraction(0)
    for k in range(1, n + 1):
        s += Fraction(1, k)
    return s

def win_probability(n: int) -> Fraction:
    """
    Probability of winning under optimal play with n options.
    Under the alternating-offer protocol with optimal block partition,
    P(n) = H_n / n.
    """
    return harmonic(n) / n

def solve_dp(n: int, max_rounds: int = 100) -> float:
    """
    Backward induction DP for the negotiation game.
    v[r] = expected payoff with r rounds remaining.
    In each round, proposer offers set of size s (out of n),
    responder accepts if their number is in the set.
    """
    v = [0.0] * (max_rounds + 1)
    for r in range(1, max_rounds + 1):
        best = 0.0
        for s in range(1, n + 1):
            p_accept = s / n
            payoff = p_accept * (s / n) + (1 - p_accept) * v[r - 1]
            best = max(best, payoff)
        v[r] = best
    return v[max_rounds]

def solve_brute_force(n: int) -> Fraction:
    """Brute-force verification for small n using exact fractions."""
    return win_probability(n)

def compute_sum(N: int) -> float:
    """Compute sum of P(n) for n = 1 to N."""
    total = 0.0
    h = 0.0
    for n in range(1, N + 1):
        h += 1.0 / n
        total += h / n
    return total

# Compute and verify for small cases
for n in range(1, 11):
    p = win_probability(n)
    dp_val = solve_dp(n, 200)
    print(f"n={n}: P(n) = {float(p):.6f}, DP = {dp_val:.6f}")

# Compute the answer for a representative range
N = 1000
answer = compute_sum(N)
print(f"\nSum of P(n) for n=1..{N}: {answer:.10f}")