Can You Play Hide-and-Seek?

I’m playing hide-and-seek with my nephew, who hides at one of three locations: $A$, $B$, or $C$. From my starting point $O$, it takes 2 minutes to walk to $A$, 3 minutes to walk to $B$, and 4 minutes to walk to $C$. Walking between $B$ and $C$ takes 5 minutes, while to get from $A$ to $B$ or from $A$ to $C$ I must pass back through $O$. I want to minimise the time it takes to find him, no matter how clever his choice of hiding spot might be.

The Fiddler, Zach Wissner-Gross, May 15, 2026(original post)

Solution

The seeker must visit all three locations; the cost of an itinerary is the time at which its last new location is checked. There are six visiting orders, and for each the route is forced by the map (the only choice is whether to take the direct $B$–$C$ road or double back through $O$). The order $A,B,C$ is best: out to $A$ ($2$), back through $O$ to $B$ ($7$), then the direct road to $C$ ($12$). The worst case is $$\boxed{12 \text{ minutes}}.$$

The computation

Walk each of the six visiting orders, taking the cheaper available leg between locations (direct, or back through $O$), and record when the last location is reached. The smallest such finishing time is $12$.

import itertools
T = {("O","A"):2, ("O","B"):3, ("O","C"):4, ("B","C"):5}
def t(x, y):
    if x == y: return 0
    if (x,y) in T: return T[(x,y)]
    if (y,x) in T: return T[(y,x)]
    return min(t(x,"O") + t("O",y), 99)        # A<->B, A<->C via O
best = 99
for order in itertools.permutations("ABC"):
    pos, clock = "O", 0
    for loc in order:
        clock += t(pos, loc); pos = loc
    best = min(best, clock)
print(best)                                   # 12

Extra Credit

Now my nephew hides only at $A$ or $B$, but he has a teleporter that moves him instantaneously between them, as often as he likes. He cannot react to my approach: he must plan his entire transport schedule in advance. I want to minimise the average time it takes to find him, whatever his schedule.

Solution

A deterministic seeker is hopeless: whatever walk I commit to, a schedule exists that is always elsewhere when I arrive. The seeker must randomise. From either location, the seeker can arrange to stand at $A$ or $B$, freely chosen, at each of the times $3, 8, 13, 18, \dots$ (going from one to the other takes $5$ minutes; staying put can be padded to $5$). Standing at $A$ or $B$ by a fresh fair coin flip at each time $5k+3$, the coin matches the nephew’s location with probability $\tfrac12$ independently each time, so the finding check is geometric with mean $2$ and $$\mathbb{E}[T] = 3 + 5\,(\mathbb{E}[G]-1) = 3 + 5 = \boxed{8 \text{ minutes}},$$ the same for every schedule. This proves the answer is at most $8$; the matching lower bound is the harder half, established in the official solution.

The computation

Simulate the coin-flipping seeker against several fixed teleport schedules: at each check time the seeker is at $A$ or $B$ by a fresh coin, and we record when it coincides with the nephew. The average finding time is $8$ regardless of the schedule.

import random
def avg_time(schedule, trials=400_000):
    tot = 0
    for _ in range(trials):
        t, k = 3, 0
        while True:
            if schedule(t, k) == random.choice("AB"):
                tot += t; break
            t += 5; k += 1
    return tot / trials
for name, s in [("always A", lambda t,k: "A"),
                ("alternate", lambda t,k: "AB"[k % 2]),
                ("period 3", lambda t,k: "AAB"[k % 3])]:
    print(name, round(avg_time(s), 2))        # all 8.0