Can You Eat All The Chocolates?

The Riddler for October 2, 2020. The Express counts the ways a number is a difference of two squares, and the Classic shows a surprisingly clean answer for which chocolate gets eaten last.

Riddler Express

A number is “hip” if it can be written as a difference of two perfect squares; it is doubly hip if it can be written that way in two ways, and so on. In how many ways can $1{,}400$ be written as a difference of two perfect squares?

The Riddler, FiveThirtyEight, October 2, 2020(original post)

Solution

Write $1{,}400 = A^2 - B^2 = (A + B)(A - B)$ with integers $A > B \ge 0$. Each representation corresponds to a factorisation $1{,}400 = s \cdot t$ with $s = A + B \ge t = A - B$, and we recover $A = (s + t)/2$, $B = (s - t)/2$. These are integers exactly when $s$ and $t$ have the same parity.

Now $1{,}400 = 2^3 \cdot 5^2 \cdot 7$ has $(3+1)(2+1)(1+1) = 24$ divisors, hence $12$ factor pairs. Since $1{,}400$ is even it cannot be a product of two odd factors, so every same-parity pair must be even$\,\times\,$even. Of the $12$ pairs, six mix an even and an odd factor ($1\times1400$, $5\times280$, $7\times200$, $8\times175$, $25\times56$, $35\times40$) and are rejected; the other six are even$\,\times\,$even. So $1{,}400$ is hip in $$\boxed{6}$$ ways: $39^2 - 11^2$, $45^2 - 25^2$, $57^2 - 43^2$, $75^2 - 65^2$, $177^2 - 173^2$, $351^2 - 349^2$. (In general, the number of representations is the count of same-parity factor pairs: for odd $N$ it is $\lceil d(N)/2 \rceil$ counting $B=0$, and for $N \equiv 2 \pmod 4$ it is $0$.)

The computation

Encode the definition: search for integer pairs $(A, B)$ with $A^2 - B^2 = 1400$.

N = 1400
reps = []
for A in range(1, N // 2 + 2):            # A = (s+t)/2 <= (N+1)/2
    b2 = A * A - N
    if b2 < 0:
        continue
    B = int(b2 ** 0.5)
    if B * B == b2:
        reps.append((A, B))
print(len(reps), reps)          # 6  [(39,11),(45,25),...,(351,349)]

There are exactly six representations.

Riddler Classic

A bag holds $10$ chocolates: $2$ milk and $8$ dark. You draw one at random and eat it, then keep drawing and eating as long as each draw matches the kind you started the streak with. The first time you draw the other kind, you put it back and start a fresh streak (eating the next draw, whatever it is). You continue until all $10$ are eaten. What is the probability the last chocolate eaten is milk?

The Riddler, FiveThirtyEight, October 2, 2020(original post)

Solution

The answer is exactly $\tfrac12$, independent of the $2$-and-$8$ split, by strong induction on the total number of chocolates $N$. Write $P(d, m)$ for the probability the last chocolate is milk when starting with $d$ dark and $m$ milk ($d, m \ge 1$). Base case $N = 2$: one dark and one milk are equally likely to be eaten second, so $P(1, 1) = \tfrac12$.

Inductive step: assume $P = \tfrac12$ for every bag of fewer than $N$ chocolates, and start with $N = d + m$. Look at the opening streak, which begins with a free draw and then keeps eating the same kind until the other kind appears. Exactly three things can happen.

• You draw all $d$ darks before any milk. The chance the first $d$ draws (without replacement) are all dark is $\dfrac{d!\,(N-d)!}{N!} = \dfrac{1}{\binom{N}{d}}$. The bag is then all milk, so the last chocolate is milk.

• You draw all $m$ milks first, with probability $\dfrac{1}{\binom{N}{m}}$; the last chocolate is dark.

• Otherwise you eat some chocolates of one kind, then draw the other kind and return it. The bag now has strictly fewer than $N$ chocolates and still contains both kinds (the returned one, plus at least one of the kind you were eating), so by the inductive hypothesis the last chocolate is milk with probability $\tfrac12$.

The crucial fact is that $m = N - d$, so $\binom{N}{m} = \binom{N}{N-d} = \binom{N}{d}$: the two “clean sweep” cases are equally likely. Letting $c = 1/\binom{N}{d}$, $$P(d, m) = c \cdot 1 + c \cdot 0 + (1 - 2c)\cdot\tfrac12 = \tfrac12.$$ So the probability is, exactly, $$\boxed{\tfrac12}.$$

The computation

Encode the eating process and simulate: start each streak with a free draw, keep eating while the kind matches, otherwise restart.

import random
def last_eaten(rng):
    pool = ['M', 'M'] + ['D'] * 8
    last, streak = None, None
    while pool:
        pick = pool[rng.randrange(len(pool))]
        if streak is None or pick == streak:
            pool.remove(pick); last = pick; streak = pick
        else:
            streak = None                # other kind: put back, restart
    return last
rng = random.Random(0)
trials = 300_000
milk = sum(1 for _ in range(trials) if last_eaten(rng) == 'M')
print(round(milk / trials, 4))           # ~0.4988  (exactly 1/2)

The simulation hovers at $0.5$: the last chocolate is milk exactly half the time.