Can You Find A Matching Pair Of Socks?

The Riddler for December 20, 2019. The Express is an office-vote puzzle: from three rounded-down percentages, reconstruct the smallest possible office. The Classic asks, on average, how many loose socks you must pull from a drawer to get a matching pair.

Riddler Express

You record the share of the vote each party theme received, but in a hurry you keep only the digits before the decimal point (so $35.0\%$, $35.17\%$ and $35.92\%$ are all written “$35$”). The winner came out at $73\%$, second place at $58\%$, and third at $32\%$ (people evidently voted more than once). Based on these recorded percentages, what is the minimum number of people who could work in the office? Extra credit: what is the greatest number of people the office cannot have?

The Riddler, FiveThirtyEight, December 20, 2019(original post)

Solution

Recording “$73$” for a count of $a$ votes out of $N$ people means $73 \le 100a/N < 74$, that is, the half-open interval $\bigl[\tfrac{73N}{100}, \tfrac{74N}{100}\bigr)$ contains a whole number $a$. The same goes for $58$ and $32$. (Since people cheated and voted repeatedly, the counts are just nonnegative integers, not tied to $N$.) Each such interval has length $N/100$.

That length is the whole story. Once $N \ge 100$ every one of these intervals is at least $1$ wide and so always contains an integer, making all three percentages achievable. So only $N < 100$ can fail, and both a smallest working $N$ and a largest failing $N$ exist; find them by checking the intervals.

Searching upward, the first $N$ for which all three intervals catch an integer is $$\boxed{34},$$ realised by $25/34 = 73.53\%$, $20/34 = 58.82\%$ and $11/34 = 32.35\%$.

For the extra credit, search downward from $99$. The largest office size for which some percentage is unreachable is $$\boxed{88}:$$ between $51/88 = 57.95\%$ and $52/88 = 59.09\%$ no count yields $58\%$. Every size $89$ and above works, in keeping with the $N \ge 100$ guarantee.

The computation

Encode the rule directly: a percentage $p$ is attainable for office size $N$ when some integer count $a$ has $\lfloor 100a/N\rfloor = p$. Find the smallest $N$ that attains all of $73, 58, 32$, and the largest $N$ that fails at least one.

import math
def attainable(N, p):
    return any(math.floor(100*a/N) == p for a in range(0, 3*N + 1))
def works(N):
    return all(attainable(N, p) for p in (73, 58, 32))
min_N    = next(N for N in range(1, 500) if works(N))
max_fail = max(N for N in range(1, 100) if not works(N))
print(min_N, max_fail)                # 34 88

The smallest possible office is $34$ people, and the greatest impossible size is $88$, as boxed.

Riddler Classic

I have 10 pairs of distinct socks loose in a drawer. In the dark I pull socks out one at a time until I have a matching pair among those removed. On average, how many socks do I pull out to get my first matching pair? Extra credit: what if I have $N$ pairs?

The Riddler, FiveThirtyEight, December 20, 2019(original post)

Solution

Suppose the first $i$ socks pulled all came from different pairs, so no match yet. Among the $2N - i$ socks still in the drawer, exactly $i$ are the partners of the ones already out (drawing any of them makes a pair), and the other $2N - 2i$ come from untouched pairs. So the next sock avoids a match with probability $$\frac{2N - 2i}{2N - i}.$$ Let $T$ be the draw on which the first pair appears. Getting through $k$ draws with no match has probability $P(T>k) = \prod_{i=0}^{k-1}\frac{2N-2i}{2N-i}$, and summing the survival probabilities, $$\mathbb{E}[T] = \sum_{k=0}^{N} \prod_{i=0}^{k-1}\frac{2N - 2i}{2N - i}.$$ For $N = 10$ this evaluates to $$\frac{262144}{46189} \approx \boxed{5.68}.$$ So even though the pigeonhole guarantee is $11$ socks, on average fewer than six suffice.

For the extra credit, the early factors behave like $1 - \tfrac{i}{2N}$, so $P(T>k) \approx e^{-k^2/(4N)}$ and the sum is well approximated by a Gaussian integral, giving $$\mathbb{E}[T] \to \sqrt{\pi N}\ \ \text{as } N \to \infty.$$ For $N=10$ that estimate is $\sqrt{10\pi} \approx 5.60$, already close to the exact $5.68$.

The computation

Evaluate the exact product-sum, and confirm it by pulling socks at random until a pair appears.

from fractions import Fraction as F
import numpy as np
def expected(N):
    E = F(0); p = F(1)
    for k in range(N + 1):
        E += p
        p *= F(2*N - 2*k, 2*N - k)        # survival for next draw
    return E
print(expected(10), float(expected(10)))   # 262144/46189 ~ 5.676
rng = np.random.default_rng(0); runs = 1_000_000; total = 0
for _ in range(runs):
    drawer = rng.permutation([i for i in range(10) for _ in range(2)])
    seen = set()
    for n, s in enumerate(drawer, 1):
        if s in seen:
            total += n; break
        seen.add(s)
print(total / runs)                         # ~5.68