Coin Rolls

Solution: Simulation + Mathematical Proof

// Simulation approach
function simulateCoinRolls(numCoins, numTrials) {
    let totalRolls = 0;

    for (let trial = 0; trial < numTrials; trial++) {
        let coins = Array(numCoins).fill(true); // true = coin exists
        let rolls = 0;

        while (coins.some(c => c)) {
            rolls++;

            // Pick random coin that still exists
            let availableIndices = [];
            for (let i = 0; i < coins.length; i++) {
                if (coins[i]) availableIndices.push(i);
            }

            const randomIndex = availableIndices[
                Math.floor(Math.random() * availableIndices.length)
            ];

            // Flip coin (50% chance of heads = removal)
            if (Math.random() < 0.5) {
                coins[randomIndex] = false;
            }
        }

        totalRolls += rolls;
    }

    return totalRolls / numTrials;
}

// Test simulation
console.log("Simulation results:");
for (let n = 1; n <= 10; n++) {
    const avgRolls = simulateCoinRolls(n, 10000);
    const theoretical = 2 * n;
    console.log(`N=${n}: Simulated=${avgRolls.toFixed(2)}, Theoretical=${theoretical}`);
}

/* Expected output:
N=1: Simulated≈2.00, Theoretical=2
N=2: Simulated≈4.00, Theoretical=4
N=3: Simulated≈6.00, Theoretical=6
N=5: Simulated≈10.00, Theoretical=10
N=10: Simulated≈20.00, Theoretical=20
*/

Mathematical Solution

// Exact mathematical answer
function expectedRolls(numCoins) {
    // Mathematical proof: E(N) = 2N
    return 2 * numCoins;
}

// Derive using recursion with memoization
function expectedRollsRecursive(n, memo = {}) {
    if (n === 0) return 0;
    if (n === 1) return 2;
    if (memo[n]) return memo[n];

    // E(n) = 2 + E(n-1)
    memo[n] = 2 + expectedRollsRecursive(n - 1, memo);
    return memo[n];
}

console.log("nMathematical solutions:");
for (let n = 1; n <= 10; n++) {
    console.log(`E(${n}) = ${expectedRolls(n)}`);
}

Python Version with Proof

import random

def simulate_coin_rolls(num_coins, num_trials=10000):
    """Empirical simulation"""
    total_rolls = 0

    for _ in range(num_trials):
        coins = [True] * num_coins
        rolls = 0

        while any(coins):
            rolls += 1

            # Pick random existing coin
            available = [i for i, c in enumerate(coins) if c]
            chosen = random.choice(available)

            # Flip: 50% chance to remove
            if random.random() < 0.5:
                coins[chosen] = False

        total_rolls += rolls

    return total_rolls / num_trials


def expected_rolls(n):
    """Mathematical exact answer: E(N) = 2N"""
    return 2 * n


# Verify simulation matches theory
print("Coin Rolls Expected Value:")
print("NtSimulatedtTheoreticaltMatch")
print("-" * 50)

for n in [1, 2, 3, 5, 10, 20]:
    simulated = simulate_coin_rolls(n, 10000)
    theoretical = expected_rolls(n)
    match = "✓" if abs(simulated - theoretical) < 0.5 else "✗"
    print(f"{n}t{simulated:.2f}tt{theoretical}tt{match}")

Mathematical Derivation

Let E(N) be expected rolls to remove N coins.

Step 1: On each roll, we either remove a coin or don't.

E(N) = 1 + P(remove) × E(N-1) + P(don't remove) × E(N)

Step 2: Calculate probabilities:

• We pick one of N coins uniformly: probability 1/N per coin
• Each coin has 1/2 chance of heads (removal)
• P(remove any coin) = N × (1/N) × (1/2) = 1/2
• P(don't remove) = 1/2

Step 3: Substitute:

E(N) = 1 + (1/2)×E(N-1) + (1/2)×E(N)
E(N) - (1/2)×E(N) = 1 + (1/2)×E(N-1)
(1/2)×E(N) = 1 + (1/2)×E(N-1)
E(N) = 2 + E(N-1)

Step 4: Solve recurrence:

E(1) = 2 (base case)
E(2) = 2 + E(1) = 2 + 2 = 4
E(3) = 2 + E(2) = 2 + 4 = 6
...
E(N) = 2N

Complexity Analysis

Simulation:

• Time: O(N × T) where T is number of trials, N is coins
• Space: O(N) for storing coin states

Mathematical:

• Time: O(1) - just return 2×N
• Space: O(1)

Variations

1. Different removal probability (p): E(N) = 2N/p
2. Coins with different probabilities: E = 2 × (1/p₁ + 1/p₂ + ... + 1/pₙ)
3. Choose which coin to roll: Optimal strategy: always pick coin with highest removal probability
4. Cost per roll: Expected cost = cost × 2N

Common Mistakes

1. Thinking E(N) = N: Forgetting you need multiple attempts per coin
2. Assuming independence: Coins are dependent because you stop when all removed
3. Wrong probability calculation: Must account for picking coin AND flipping heads
4. Simulation bias: Need 10,000+ trials for accurate results

Follow-up Questions

1. What if we roll all coins simultaneously each round? Different problem - geometric distribution
2. Variance of the number of rolls? Var(N) = 2N + 2N(N-1) = 2N²
3. Probability of removing all coins in exactly k rolls? More complex - need generating functions
4. Median number of rolls? Close to 2N but slightly less due to distribution skew

Related Problems

• Red Marbles, Blue Marbles - Probability problems
• Probability Distribution Function - Statistical analysis
• Monty Hall Problem - Probability theory