Can You Pass The Cranberry Sauce?

The Riddler for November 20, 2020. The Express counts the most Friday the 13ths possible in four years, and the Classic finds who is most likely to be served last when a dish random-walks around a table.

Riddler Express

Over four consecutive calendar years, what is the greatest number of Friday the 13ths that can occur?

The Riddler, FiveThirtyEight, November 20, 2020(original post)

Solution

A Friday the 13th is a month whose 1st is a Sunday. Four consecutive years contain at most one leap year, and the day-of-week on which months begin cycles through a fixed pattern set by the months’ lengths (modulo $7$). Tabulating how often each weekday starts a month across the $48$ months: when the first of the four years is a leap year, one weekday starts nine months (the others six or seven); in every other alignment, no weekday starts more than eight. So if that most-frequent starting day happens to be Sunday, you get $$\boxed{9}$$ Friday the 13ths in four years, achieved when the leading year is a leap year.

The computation

Encode it directly: for each starting year, count Friday the 13ths over the four-year window and take the maximum.

import datetime
def f13(y0):
    return sum(datetime.date(y, m, 13).weekday() == 4   # 4 = Friday
               for y in range(y0, y0 + 4) for m in range(1, 13))
print(max(f13(y) for y in range(1900, 2400)))           # 9

The maximum is nine Friday the 13ths in four consecutive years.

Riddler Classic

You and $19$ family members sit around a circular table; the cranberry sauce starts with you. Each holder passes it to a random neighbour (left or right, equally likely). This continues until everyone has received it at least once. Of the $20$ people, who is most likely to be the last served?

The Riddler, FiveThirtyEight, November 20, 2020(original post)

Solution

Surprisingly, everyone other than you is equally likely to be last, each with probability $\tfrac{1}{19}$ (you can never be last, since you start with it). Fix any other person $X$. For $X$ to be served last, every other person must be reached first, which means the sauce must arrive at one neighbour of $X$ and then travel the entire rest of the circle to reach $X$ from the far side, rather than stepping directly across. This is a gambler’s-ruin event whose probability does not depend on where $X$ sits: by symmetry of the symmetric random walk on a cycle, the last-visited vertex is uniform over all $n-1$ non-starting vertices. Hence $$P(X \text{ last}) = \boxed{\tfrac{1}{19}} \quad\text{for every } X \neq \text{you}.$$ Distance from you is irrelevant, the counter-intuitive part.

The computation

Encode the random walk on a $20$-cycle, record which vertex is visited last (first-reached last), and confirm the distribution is uniform over the $19$ non-start vertices.

import random
def last_served(rng, n=20):
    seen, pos = {0}, 0
    while len(seen) < n:
        pos = (pos + rng.choice((-1, 1))) % n
        seen.add(pos)
        if len(seen) == n:
            return pos
rng = random.Random(0)
trials, count = 200_000, [0] * 20
for _ in range(trials):
    count[last_served(rng)] += 1
freq = [c / trials for c in count]
print(round(freq[0], 4))                       # 0.0  (you, never last)
print(round(min(freq[1:]), 4), round(max(freq[1:]), 4))   # ~0.0526 each (1/19)

Every seat but yours is last about $1/19 \approx 5.26\%$ of the time, regardless of distance.