Can You Get The Gloves Out Of The Box?

The Riddler for March 27, 2020. The Express counts the ordered ways to empty a box of ten gloves when you only ever pull two, three or four at a time. The Classic rolls a die to relabel a die, over and over, and asks how long until every face agrees.

Riddler Express

You pull gloves from a box two, three or four at a time (never any other number), and there are $10$ gloves left. In how many distinct ordered ways can you remove all $10$? (Order matters: $2$ then $4$ then $4$ differs from $4$ then $4$ then $2$.)

The Riddler, FiveThirtyEight, March 27, 2020(original post)

Solution

Let $f(n)$ be the number of ordered ways to remove $n$ gloves in pulls of $2$, $3$ or $4$. The very first pull is a $2$, a $3$ or a $4$, and after it you face the same kind of problem with $n-2$, $n-3$ or $n-4$ gloves left. So $$f(n) = f(n-2) + f(n-3) + f(n-4),$$ with $f(0) = 1$ (one way to remove nothing: stop) and $f(n) = 0$ for $n < 0$. Climbing from the bottom, $$\begin{aligned} &f(0){=}1,\ f(1){=}0,\ f(2){=}1,\ f(3){=}1,\ f(4){=}2,\ f(5){=}2,\\ &f(6){=}4,\ f(7){=}5,\ f(8){=}8,\ f(9){=}11,\\ &f(10){=}f(8){+}f(7){+}f(6){=}17. \end{aligned}$$ So there are $$\boxed{17}$$ distinct ways to empty the box.

The computation

Encode the same recurrence directly.

def ways(n, parts=(2, 3, 4)):
    if n == 0: return 1
    return sum(ways(n - p) for p in parts if n - p >= 0)
print(ways(10))            # 17

The recursion counts $17$ orderings, as boxed.

Riddler Classic

Start with a fair $6$-sided die and roll it six times; write those six results on the faces of a new die (so a value rolled twice appears on two faces). Roll the new die six times to make the next die, and so on. Eventually every face shows the same number. On average, how many rolls does this take? Extra credit: what about an $N$-sided die?

The Riddler, FiveThirtyEight, March 27, 2020(original post)

Solution

What matters about a die is not which numbers are on it but how its six faces split into repeated values: a die showing $\{1,1,1,2,2,3\}$ behaves exactly like one showing $\{4,4,4,5,5,6\}$. So the state is a partition of $6$ (the multiplicities of the distinct values), and there are eleven of them, from $(1,1,1,1,1,1)$ (all six distinct) to $(6)$ (all the same, the absorbing state).

One round rolls the current die six times. Each roll lands on a value with probability equal to that value’s multiplicity over $6$, so the six rolls are a multinomial draw, and the counts they produce are the multiplicities of the next die. That fixes the transition probability between any two partitions. Writing $E(\text{state})$ for the expected number of rounds left, $E$ satisfies $E = 1 + (\text{average of } E \text{ over the next partition})$ off the absorbing state, with $E\bigl((6)\bigr) = 0$. Solving the eleven equations exactly, starting from the all-distinct die, gives $$\boxed{\frac{31394023}{3251248} \approx 9.656}\ \text{rounds}.$$ Since each round is six rolls, that is about $58$ rolls. For the extra credit, the same machinery (a Markov chain on partitions of $N$) applies; the expected number of rounds grows like $2N$ as $N$ increases.

The computation

Encode the chain on partitions of $6$: build each partition’s transition law from the multinomial of six rolls, then solve the linear system for the expected rounds, exactly.

import itertools, math, sympy as sp
from collections import defaultdict
def partitions(n):
    out = []
    def rec(n, mx, cur):
        if n == 0: out.append(tuple(sorted(cur, reverse=True))); return
        for k in range(min(n, mx), 0, -1): rec(n - k, k, cur + [k])
    rec(n, n, []); return sorted(set(out))
parts = partitions(6); idx = {p: i for i, p in enumerate(parts)}
def transition(p):                       # die with face-multiplicities p
    out = defaultdict(lambda: sp.Integer(0))
    for cv in itertools.product(range(7), repeat=len(p)):
        if sum(cv) != 6: continue
        coef = math.factorial(6)
        for c in cv: coef //= math.factorial(c)
        pr = sp.Rational(coef)
        for c, m in zip(cv, p): pr *= sp.Rational(m, 6)**c
        out[tuple(sorted((c for c in cv if c), reverse=True))] += pr
    return out
n = len(parts); A = sp.zeros(n, n); b = sp.zeros(n, 1)
for p in parts:
    i = idx[p]; A[i, i] += 1
    if p == (6,): continue
    b[i] = 1
    for q, pr in transition(p).items(): A[i, idx[q]] -= pr
E = A.LUsolve(b)
print(E[idx[(1,) * 6]])                  # 31394023/3251248 ~ 9.656

The exact expected number of rounds from the all-distinct die is $31394023/3251248 \approx 9.656$, as boxed.