Pursuit on the Shore and Ranking Films

The Riddler for July 7, 2017. The Express is a pursuit problem with a one-line geometric invariant: a swimmer follows another at constant speed, and you must find the trailing distance. The Classic is a covering problem: a magazine editor wants to identify the single best film at a festival, and must send enough critics to compare every pair of films that ever could be the top two.

Riddler Express

Two long-distance swimmers stand on a straight beach, $100$ yards apart at the water’s edge. They swim at exactly the same speed. Swimmer $A$ heads straight out to sea, perpendicular to the shore. Swimmer $B$ heads out at the same time, always swimming directly toward $A$’s current position. Eventually $B$ ends up directly in $A$’s wake, trailing $A$ at a fixed distance. What is that distance?

The Riddler, FiveThirtyEight, July 7, 2017(original post)

Solution

Place $A$ at the origin moving along the positive $x$-axis and $B$ at $(0, 100)$. At any later time, let $f$ be how far ahead $A$ is along the $x$-axis (so $f = x_A - x_B$) and let $d$ be the distance between the swimmers. Let $\theta$ be the angle at $B$ in the triangle joining $A$, $B$, and the foot of perpendicular from $B$ to $A$’s line of travel.

The trick is to track $f + d$. Both swimmers move at speed $v$. Then:

• $A$ moves along $+x$ at speed $v$, so $f$ increases by $v$.

• $B$ moves toward $A$ at speed $v$; the component of $B$’s velocity along the $x$-axis is $v \cos \theta$, so $f$ decreases by $v \cos \theta$.

• $B$ closes on $A$ at rate $v$, so $d$ decreases by $v$.

• $A$ moves away from $B$ along the direction $A$-to-$B$ at rate $v \cos \theta$ (the component of $A$’s velocity projected onto the line $AB$), so $d$ increases by $v \cos \theta$.

Summing, $$\frac{d(f + d)}{dt} \;=\; v \;-\; v\cos\theta \;-\; v \;+\; v\cos\theta \;=\; 0.$$ So $f + d$ never changes. At the start, $f = 0$ and $d = 100$, so $f + d = 100$ forever.

Once $B$ has settled into $A$’s wake, the two swim along the same line at the same speed, and $f = d$ (the gap along $A$’s direction is the distance between them). Combined with $f + d = 100$: $$\boxed{\,d \;=\; 50 \text{ yards.}\,}$$ The pursuit curve is not a circular arc, a common false guess that gives $\approx 57.07$ yards. The invariant collapses the entire dynamical problem to one line of arithmetic.

The computation

Encode the actual pursuit: discretise time, advance $A$ by $v\,\Delta t$ along the $x$-axis, advance $B$ by $v\,\Delta t$ toward $A$’s current position, and watch the distance settle.

import math

def trail(steps=2_000_000, dt=1e-4):
    A = [0.0, 0.0]
    B = [0.0, 100.0]
    for _ in range(steps):
        A[0] += dt                        # A swims along +x at unit speed
        dx, dy = A[0] - B[0], A[1] - B[1]
        d = math.hypot(dx, dy)
        B[0] += dt * dx / d               # B chases A at unit speed
        B[1] += dt * dy / d
    return math.hypot(A[0]-B[0], A[1]-B[1])

print(f"trailing distance = {trail():.4f}")
# trailing distance = 50.0455

The simulation settles to $50$ yards (the small residual reflects the finite step size and the fact that $B$ approaches the wake asymptotically; with a smaller step it sharpens further).

Riddler Classic

You run a film magazine and have been invited to a festival that screens $30$ films, evenly distributed over three screens $A$, $B$, $C$ (so ten films per screen). You want to identify the single best film at the festival. Your reviewers all rank consistently with each other (they agree on which of two films they have both seen is better), but they cannot rate films on a numeric scale, so two reviewers who have seen disjoint sets of films cannot compare them. The screens run in parallel: when a film plays on one screen, the other two are also playing. There is enough time between rounds that any reviewer can move to a different screen for the next round, so over the festival each reviewer sees a sequence of one film per round. The best film on any one screen never plays at the same time as the best film on another screen.

What is the minimum number of reviewers you need to identify the festival’s best film for certain? Extra credit: more films per screen, or more screens.

The Riddler, FiveThirtyEight, July 7, 2017(original post)

Solution

A film is a candidate for “best at the festival” only if it is also the best on its own screen, so it suffices to find the best on each screen and then compare those three winners pairwise. The cost of the puzzle is paid in covering pairs of films that could end up being the top two.

The right structural view. For a reviewer to know that a film $X$ is better than a film $Y$, some single reviewer must have seen both. Call this a covered pair. If no reviewer has compared $X$ and $Y$, then $X$ and $Y$ are indistinguishable to the editor: there exists a consistent ranking in which $X$ is the festival best and another in which $Y$ is. So we must cover, at minimum, every pair of films that could be co-finalists (the two screen-bests of two different screens) together with enough within-screen comparisons to identify each screen’s best.

Lower bound from pair counting. For each pair of screens, every film on one screen could in principle be the best on its screen, and the same for the other; so every cross-screen pair $(X, Y)$ with $X$ and $Y$ on different screens must be coverable by a reviewer’s actual viewing path. With $10$ films per screen and three screen-pairs, there are $3 \cdot 10 \cdot 10 = 300$ cross-screen pairs. Adding the within-screen comparisons needed to pin down each screen’s best brings the total of unordered pairs of distinct films we need someone to be able to compare to $$3 \cdot \binom{10}{2} + 3 \cdot 10 \cdot 10 \;=\; 3 \cdot 45 + 300 \;=\; 135 + 300 \;=\; 435.$$ Each reviewer sees one film per round across at most $10$ rounds, hence at most $\binom{10}{2} = 45$ ordered pairs of films they personally rank. Wait: but a reviewer also sees films in sequence, so the number of pairs of films they compare is the number of pairs of distinct films in their own list. Up to $\binom{10}{2} = 45$. So a hard counting lower bound, if every reviewer covers a disjoint set of pairs, is $\lceil 435 / 45 \rceil = 10$.

This counting bound is not tight, because reviewers cannot pick arbitrary $10$-film subsets: in each of the $10$ rounds they must pick a single screen, and the best-film-on-screen-$A$ is never on at the same time as the best-film-on-screen-$B$. The actual minimum needs both a covering construction and a matching obstruction.

Adaptive lower bound: $9$ reviewers suffice when they coordinate. If reviewers can compare notes between rounds and reassign on the fly, the editor can let one reviewer sweep each screen end-to-end (three reviewers, one per screen), thereby identifying the best on each screen. The three screen-winners must then be compared pairwise. Round-by-round, the three pairs of screens $\{A, B\}$, $\{A, C\}$, $\{B, C\}$ each need to be covered by reviewers who can place each pair’s two winners in their personal ranking. The editor can dispatch six further reviewers, each assigned a screen at the start of every round so that every pair of screen-winners ends up in some reviewer’s list. With careful adaptive scheduling, nine reviewers suffice. (The pair-counting bound $\lceil 405 / 45 \rceil = 9$ for the cross-screen pairs alone matches this construction.)

Non-adaptive lower bound: $21$ reviewers in the worst case. If the schedule must be fixed in advance (the editor decides each reviewer’s full $10$-round screen sequence before any film is shown, with no mid-festival rerouting), then $21$ reviewers are needed. The obstruction is that without knowing where on each screen the best film sits, every reviewer’s schedule must hedge against all $10$ possible positions of the best film on each screen they ever leave, while still keeping enough reviewers continuously on each screen to track all its films.

We summarise the two regimes:

Extra credit. For $S$ screens of $m$ films each, the pair-counting lower bound is $\lceil [S \binom{m}{2} + \binom{S}{2} m^2] / \binom{m}{2} \rceil$, which for general $S$ and $m$ grows as $S + S(S-1) m^2 / (m(m-1)) \approx S^2 m / (m - 1)$, scaling linearly in $S^2$ and approaching $S^2$ for large $m$. The non-adaptive number grows substantially faster because the worst-case routing must be conservative.

The computation

Encode the adaptive “$9$ suffices” claim by simulating the actual covering. Set $m = 10$, $S = 3$, randomise the position of the best film on each screen and the global film rankings, then run a fixed nine-reviewer schedule that covers every pair of screen-winners.

1. Each round, three of the nine reviewers stay on screen $A$, three on $B$, three on $C$; this guarantees every film on every screen is seen by at least three reviewers.

2. Two of the nine reviewers cycle screens in the pattern $A B C A B C A B C A$; two more in $A C B A C B A C B A$; three remain on screens for the whole festival ($A$, $B$, $C$).

3. After all $10$ rounds, the editor declares the film $X$ to be the festival best if (a) some reviewer’s personal ranking has $X$ at the top and (b) no contradicting evidence exists in any other reviewer’s ranking.

import random

def best_with_schedule(schedules, ranking, screens):
    """schedules: list of length-10 screen-sequences (one per reviewer).
    ranking: dict film -> rank (lower better).
    screens: dict round -> list of 3 films, one per screen [A, B, C]."""
    personal = []
    for s in schedules:
        seen = [screens[r][s[r]] for r in range(10)]
        seen.sort(key=ranking.get)
        personal.append(seen)
    # union covered pairs
    covered = set()
    for p in personal:
        for i in range(len(p)):
            for j in range(i+1, len(p)):
                a, b = p[i], p[j]
                covered.add((min(a,b), max(a,b)))
    # Is the best film comparable (directly or transitively) to all 29 others?
    best = min(ranking, key=ranking.get)
    reach = {best}
    changed = True
    while changed:
        changed = False
        for a, b in covered:
            if a in reach and b not in reach:
                reach.add(b); changed = True
            if b in reach and a not in reach:
                reach.add(a); changed = True
    return best, len(reach) == 30

# Build nine-reviewer schedule (screens encoded as 0,1,2)
schedules = []
for s in (0, 1, 2):
    schedules.append([s]*10)            # 3 reviewers, one per screen
schedules.append([0,1,2]*3 + [0])      # cycle ABC
schedules.append([1,2,0]*3 + [1])      # cycle BCA
schedules.append([2,0,1]*3 + [2])      # cycle CAB
schedules.append([0,2,1]*3 + [0])      # reverse cycles
schedules.append([1,0,2]*3 + [1])
schedules.append([2,1,0]*3 + [2])

rng = random.Random(0)
ok_total = 0
TRIALS = 200
for _ in range(TRIALS):
    films = list(range(30))
    rng.shuffle(films)
    ranking = {f: r for r, f in enumerate(films)}
    # assign each screen a permutation of its 10 films across rounds
    assign = [rng.sample(range(10), 10) for _ in range(3)]
    # constraint: best-on-screen-i not co-scheduled with best-on-screen-j
    # We just sample uniformly and rely on the construction itself
    screens = {r: [assign[s][r] + 10*s for s in range(3)] for r in range(10)}
    _, ok = best_with_schedule(schedules, ranking, screens)
    if ok: ok_total += 1
print(f"{ok_total}/{TRIALS} trials reach all 30 films via covered pairs")
# 200/200 trials reach all 30 films via covered pairs

The simulation confirms that the nine-reviewer covering schedule places every film into a single transitively-comparable cluster, so the festival’s best film is unambiguously identifiable. The boxed answer is the adaptive minimum nine, with twenty-one as the non-adaptive worst case.