Can You Get A Haircut Already?

The Riddler for February 28, 2020. The Express is a dark-room card trick: split a deck into two piles with equally many face-up cards, blind. The Classic is a queueing problem at a barbershop where you hold out for one particular barber.

Riddler Express

You sit in a dark room at a table with a single pile of $52$ cards, exactly $13$ of them face up and the rest face down. You can feel and move the cards but cannot tell by touch which way any card faces. How can you make two piles (each with at least one card) guaranteed to hold the same number of face-up cards?

The Riddler, FiveThirtyEight, February 28, 2020(original post)

Solution

The one number you know is that $13$ cards face up. So separate exactly $13$ cards into a new pile, and flip that whole pile over.

Here is why it works. Say the $13$ cards you moved happen to contain $x$ face-up cards. Then the other $39$ cards hold the remaining $13 - x$ face-up cards. Flipping the $13$-card pile turns its $x$ face-up cards face down and its $13 - x$ face-down cards face up, so that pile now shows $13 - x$ face up, exactly matching the big pile. The two piles agree no matter what $x$ was:

You never needed to know which cards were which, only that $13$ faced up to begin with. Splitting off $k$ cards and flipping them works whenever $k$ equals the known face-up count.

The computation

Encode the trick: shuffle a deck of $13$ face-up and $39$ face-down cards, peel off any $13$, flip them, and check both piles match every time.

import random
rng = random.Random(0)
ok = True
for _ in range(1_000_000):
    deck = [1]*13 + [0]*39          # 1 = face up
    rng.shuffle(deck)
    pile, rest = deck[:13], deck[13:]
    flipped = [1 - c for c in pile]              # flip the 13-card pile
    if sum(flipped) != sum(rest):
        ok = False; break
print(ok)                                        # True

Across a million shuffles the flipped pile always matches the rest, as boxed.

Riddler Classic

At a barbershop, four barbers work at once and every haircut takes exactly $15$ minutes. You only want the owner, Tiffany: if another chair opens and it is your turn, you wave it on to the person behind you and keep your place at the front of the line. A quarter of the other customers also hold out for Tiffany; nobody holds out for the other three barbers. You arrive to find all four barbers busy (you know nothing about how far along each cut is) and exactly one customer waiting ahead of you. What is your expected wait for a haircut from Tiffany?

The Riddler, FiveThirtyEight, February 28, 2020(original post)

Solution

Since you arrive at a random moment, Tiffany’s remaining time $T$ and the other three barbers’ remaining times $B_1,B_2,B_3$ are each uniform on $(0,15)$ and independent. The one customer ahead of you holds out for Tiffany with probability $\tfrac14$.

If the customer ahead holds out for Tiffany (probability $\tfrac14$): they are ahead of you in her queue, so you wait for her current cut to finish and then for theirs, $Y = 15 + T$.

If the customer ahead does not hold out (probability $\tfrac34$): they grab the first chair to open. If a non-Tiffany barber opens first, they take it and you slide into Tiffany’s chair when she finishes, $Y = T$. But if Tiffany opens first, the customer ahead takes her, and you wait for her next slot, $Y = 15 + T$. The extra $15$ appears exactly when $T$ is the smallest of $T, B_1, B_2, B_3$, which by symmetry happens with probability $\tfrac14$. So $$\mathbb{E}[Y \mid \text{no hold-out}] = \mathbb{E}[T] + 15\cdot\tfrac14 = 7.5 + 3.75 = 11.25.$$

Combining the two cases, $$\mathbb{E}[Y] = \tfrac14(22.5) + \tfrac34(11.25) = \frac{225}{16} = \boxed{14.0625} \text{ min}.$$

The computation

Simulate your arrival: draw four uniform remaining times and a hold-out coin for the customer ahead, apply the waiting rule, and average.

import numpy as np
rng = np.random.default_rng(0)
runs = 4_000_000; total = 0.0
for _ in range(runs):
    t, b1, b2, b3 = rng.uniform(0, 15, 4)
    if rng.random() < 0.25:              # ahead holds out for Tiffany
        wait = 15 + t
    else:
        wait = 15 + t if t < min(b1, b2, b3) else t
    total += wait
print(total / runs)                          # ~14.0625