Can You Get Another Haircut Already?

The Riddler for March 13, 2020. The Express asks for the next power of $2$ that hugs a power of $10$ even more closely than $2^{10} \approx 10^3$. The Classic revisits Tiffany’s barbershop, this time with the queue dynamics stated precisely, and the answer turns on a subtle build-up at the front of the line.

Riddler Express

A kilobyte is $2^{10} = 1024$ bytes, only $2.4\%$ above $10^3$. After $2^{10}$, what is the next whole-number power of $2$ that comes within $2.4\%$ of a power of $10$?

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

Solution

Asking for $2^n \approx 10^m$ is, after taking base-$10$ logarithms, asking for $\tfrac{m}{n} \approx \log_{10}2 = 0.30103\ldots$ The best rational approximations to an irrational number, with the smallest denominators, are its continued-fraction convergents. For $\log_{10}2$ these begin $$\frac{0}{1},\quad \frac{1}{3},\quad \frac{3}{10},\quad \frac{28}{93},\quad \ldots$$ The convergent $\tfrac{3}{10}$ is exactly the kilobyte coincidence $2^{10} \approx 10^3$. The next one, $\tfrac{28}{93}$, gives $$\boxed{2^{93} \approx 10^{28}}.$$ Indeed $93\log_{10}2 = 27.996$, so $2^{93} = 10^{28} \cdot 10^{-0.004} \approx 0.990\cdot 10^{28}$, about $0.97\%$ below $10^{28}$, comfortably inside $2.4\%$ and the first power of $2$ past $2^{10}$ to beat it. (In full, $2^{93} = 9{,}903{,}520{,}314{,}283{,}042{,}199{,}192{,}993{,}792$.) Because only the convergents give approximations this good, no exponent between $11$ and $92$ comes close enough.

The computation

Encode “within $2.4\%$ of a power of $10$” directly as a multiplicative gap, and scan exponents upward for the first one past $10$ that clears the bar.

import math
def rel_gap(n):
    L = n*math.log10(2)
    return 10**abs(L - round(L)) - 1            # gap to nearest power of 10
print(next(n for n in range(11, 200) if rel_gap(n) < 0.024))   # 93

The first qualifying exponent is $93$, i.e. $2^{93}$, as boxed.

Riddler Classic

All of Riddler City queues at Tiffany’s shop, in random order, before it opens; the four barbers begin their first cuts at random times in the first $15$ minutes, and every cut lasts $15$ minutes. Each customer independently prefers Tiffany with probability $\tfrac14$; whenever a Tiffany-preferrer reaches the front, they let anyone behind them take a non-Tiffany chair (and that person may in turn be skipped if they too prefer Tiffany). After a long, oblivious wait you find yourself second in line, one person ahead. How long should you now expect to wait for your haircut?

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

Solution

The tempting move is to say the person ahead of you prefers Tiffany with probability $\tfrac14$. That is wrong, and seeing why is the puzzle.

Write the line as a string of Ts (prefer Tiffany, a fraction $\tfrac14$ of arrivals) and Us (everyone else). Each $15$-minute cycle the four barbers free up together: Tiffany takes whoever is at the very front, T or U; the other three barbers each take the next U, because any T ahead of that U waves the non-Tiffany chair on. So each cycle removes one front customer plus the next three Us. The Us get stripped out three times as fast as Tiffany consumes the front, so a backlog of Ts piles up at the head of the line (its length grows like $\sqrt{N}$ after $N$ cycles).

In Riddler City’s enormous line, by the time you are second the run of Ts in front has grown without bound, so the person immediately ahead of you is, with probability approaching $1$, a Tiffany-preferrer, and so are you in effect waiting in a pure-Tiffany queue. Your wait is then the time for Tiffany to finish her current cut plus one full cut for the person ahead: $$\mathbb{E}[\text{wait}] = \underbrace{7.5}_{\text{rest of current cut}} + \underbrace{15}_{\text{person ahead}} = \boxed{22.5}\ \text{minutes},$$ the $7.5$ being the mean of a remaining cut, uniform on $[0,15]$.

The computation

Encode the queue: a long random line of Ts and Us, processed cycle by cycle (Tiffany takes the front, the other three take the next three Us). Measure how often the front customer is a T deep into the line.

import random
from collections import deque
def front_is_T(cycles=5000, seed=0):
    rng = random.Random(seed)
    line = deque(1 if rng.random() < 0.25 else 0 for _ in range(4*cycles + 100))
    hits = trials = 0
    for c in range(cycles):
        if len(line) < 20: break
        if c > cycles//2:                       # sample after warm-up
            trials += 1; hits += line[0]
        line.popleft()                          # Tiffany serves the front
        for _ in range(3):                      # other 3 barbers each take next U
            i = next((j for j, v in enumerate(line) if v == 0), None)
            if i is None: line.popleft()
            else: del line[i]
    return hits/trials
print(front_is_T())                              # 1.0 -> wait = 7.5 + 15 = 22.5

The front customer is a Tiffany-preferrer with probability $\to 1$, so the expected wait is $7.5 + 15 = 22.5$ minutes, as boxed.