Free Drinks On Card Two

Riddler Express

What is the missing letter in the sequence below? (The sequence is published as an image only, and the hint is that you should think outside the box.)

The Riddler, FiveThirtyEight, April 5, 2019(original post)

Solution

The puzzle is published as a strip image of capital letters that look English but happen also to be valid Greek capitals (e.g. I = iota, B = beta, T = tau, M = mu). The trick is that the sequence walks the Greek alphabet by stepping $-7$ positions each time (wrapping around), and the missing letter is the Greek capital theta, $\Theta$, which has no Latin-letter twin and therefore does not look “in” the sequence on first reading.

This puzzle is deferred from the worked-solution standard because the data is the image: any text transcription of the strip already gives the trick away (the letters are chosen precisely so the Greek-alphabet origin is invisible at a glance), and without the image there is nothing to derive. The official solution (FiveThirtyEight, April 12, 2019) gives the missing letter as $$\boxed{\Theta\ (\text{Greek capital theta}).}$$

Riddler Classic

You have won two gift cards, each loaded with $50$ free drinks at your favourite coffee shop. The cards look identical and you randomly pick one each time you buy a drink. One day the clerk tells you the card you presented has no drinks left on it. What is the probability that the other card still has free drinks on it? How many drinks do you expect are still available on it?

The Riddler, FiveThirtyEight, April 5, 2019(original post)

Solution

Call the cards $A$ and $B$. The setup is a Banach matchbox problem. Each time you buy a drink you flip a fair coin to choose a card; if that card has $\ge 1$ drink, the drink is taken; if it has zero drinks left, the clerk tells you it is empty and the process stops.

Counting one direction. Suppose the empty card discovered is $A$, and $B$ has $k \in \{0, 1, \ldots, n\}$ drinks left, where $n = 50$. For this to be the outcome you must have:

• used $A$ a total of $n$ times before the empty-card flip,

• used $B$ a total of $n - k$ times,

• flipped $A$ on the final (empty) attempt.

Total flips $= n + (n - k) + 1 = 2n - k + 1$. The final flip is $A$; among the first $2n - k$ flips, exactly $n$ are $A$ and $n - k$ are $B$. Each flip is iid uniform on $\{A, B\}$, so $$\Pr(A\text{ empty},\,B\text{ has }k) \;=\; \binom{2n - k}{n}\,\left(\tfrac{1}{2}\right)^{2n - k + 1}.$$ The same count applies with $A$ and $B$ swapped, so the unconditioned probability that the empty card discovered has $k$ drinks left on the other card is double the above: $$p_{k} \;=\; \binom{2n - k}{n}\,\left(\tfrac{1}{2}\right)^{2n - k}.$$ A quick check: $\sum_{k=0}^{n} p_{k} = 1$ exactly (verified in the code).

Headline. “The other card has no drinks” is the event $k = 0$: $$p_{0} \;=\; \binom{100}{50}\,\left(\tfrac{1}{2}\right)^{100} \;\approx\; 0.0796.$$ So the other card still has free drinks on it with probability $$1 - p_{0} \;\approx\; 1 - 0.0796 \;=\; 0.9204.$$ The expected number of drinks left on the other card is $$\mathbb{E}[k] \;=\; \sum_{k=0}^{n} k\,\binom{2n - k}{n}\,\left(\tfrac{1}{2}\right)^{2n - k} \;\approx\; 7.04.$$

$$\boxed{\Pr(\text{other card valid}) \;\approx\; 92.0\%, \qquad \mathbb{E}[k] \;\approx\; 7.04 \text{ drinks}.}$$

Why the value is so high. The Banach distribution concentrates around small positive $k$: the symmetric random walk between the two card piles has standard deviation of order $\sqrt{n}$, and $\sqrt{50} \approx 7$, which is exactly where the mean lands. The chance both run out at once is only the central binomial coefficient over $2^{100}$, which is order $1/\sqrt{\pi n} \approx 0.08$ by Stirling.

The computation

Build $p_{k}$ exactly as a rational with $\mathrm{Fraction}$ for the small denominator and verify the sum. Confirm with Monte Carlo.

1. Build $p_{k} = \binom{2n - k}{n}/2^{2n - k}$ for $k = 0, \ldots, n$.

2. Check the sum equals $1$.

3. Report $1 - p_{0}$ and $\sum k\,p_{k}$.

4. Monte Carlo the actual two-card process and confirm.

import random
from fractions import Fraction
from math import comb

n = 50
probs = [Fraction(comb(2 * n - k, n), 2 ** (2 * n - k)) for k in range(n + 1)]
assert sum(probs) == 1, "probabilities should sum to 1"

p_other_valid = 1 - probs[0]
E_k = sum(k * probs[k] for k in range(n + 1))

print(f"P(other valid)  = {float(p_other_valid) * 100:.3f}%")
print(f"E[k drinks left] = {float(E_k):.4f}")

# Monte Carlo
def simulate(rng, n=50):
    A, B = n, n
    while True:
        c = rng.randint(0, 1)
        if c == 0:
            if A == 0: return B          # A presented empty; B has this many
            A -= 1
        else:
            if B == 0: return A
            B -= 1

rng = random.Random(0)
trials = 200_000
samples = [simulate(rng) for _ in range(trials)]
hits = sum(1 for k in samples if k > 0)
print(f"MC P(other valid) = {hits/trials*100:.3f}%")
print(f"MC E[k]            = {sum(samples)/trials:.4f}")

The script prints $\Pr(\text{other valid}) \approx 92.04\%$, $\mathbb{E}[k] \approx 7.04$, and a Monte Carlo agreement within $\pm 0.3\%$ on the probability and $\pm 0.05$ on the mean.