Chapter 230

You’ve Been Marooned By Kidnappers. Can You Escape At Dawn?

Riddler Express

Kidnappers maroon you on a small, featureless, flat sand island, “a bit more than a mile by half a mile.” Everything is taken; you have no watch, no compass, no idea of your location or even the date. You are left a satellite phone with one minute of battery, and told not to call until daylight. Your people, who are clever, will get whatever you say. The night is clear and moonless. What do you say to let them find you?

The Riddler, FiveThirtyEight, June 7, 2019(original post)

Solution

You have no instruments, but you have a clock you cannot read and your people can: the sky. Two events you can time exactly without any equipment are the instant of sunrise and the instant of sunset. So you spend your minute of battery on two short calls.

The first call, at the exact moment of sunrise. You do not know what time it is, but your people do. Sunrise sweeps around the globe along the line dividing night from day, the terminator, which at any given instant of universal time is a known meridian. So “it is sunrise here, right now” pins you to one line of longitude. (The Earth turns $15^\circ$ of longitude per hour, so a one-minute error in the call costs only a quarter-degree.)

The second call, at the exact moment of sunset. The gap between your two calls is the length of daylight where you are. On any date away from the equinox, day length is a one-to-one function of latitude (and the hemisphere is fixed by whether the day is long or short for that season), so the elapsed time fixes your latitude. Longitude from the sunrise instant and latitude from the day length together give a point.

The only soft spot is the equinox, when daylight is twelve hours everywhere and latitude drops out; then you would fall back on a noon shadow (the ratio of a bottle’s shadow to its height gives latitude, and the side the shadow falls on gives the hemisphere). Away from the equinox, two timestamps suffice.

The computation

To show the two timestamps really do determine the location, encode the physics in the forward direction and then invert it. Place a hidden point at latitude $\phi$ and longitude $\lambda$ on a date with known solar declination $\delta$ . The sunrise hour angle $H$ satisfies $\cos H = -\tan\phi\,\tan\delta$ ; daylight lasts $2H$ (in degrees) over $15$ degrees per hour, and local solar sunrise is $H/15$ hours before solar noon. Converting solar time to universal time through the longitude gives the two observable instants. Inverting, the day length returns $H$ hence $\phi$ , and the sunrise instant returns $\lambda$ .

import numpy as np
def d2r(x): return x * np.pi / 180.0

def observe(lat, lon, decl):                 # -> (UTC sunrise hour, daylight hours)
    H = np.degrees(np.arccos(-np.tan(d2r(lat)) * np.tan(d2r(decl))))
    daylen = 2 * H / 15.0
    utc_sunrise = ((12 - H / 15.0) - lon / 15.0) % 24
    return utc_sunrise, daylen

lat_true, lon_true, decl = -33.0, 151.0, -20.0      # hidden point + date's declination
utc_sr, daylen = observe(lat_true, lon_true, decl)
print(f"observed: UTC sunrise {utc_sr:.4f} h, daylight {daylen:.4f} h")

H = daylen / 2 * 15.0                                # latitude from day length
lat_rec = np.degrees(np.arctan(-np.cos(d2r(H)) / np.tan(d2r(decl))))
lon_rec = ((12 - H / 15.0 - utc_sr) * 15.0 + 180) % 360 - 180   # longitude from sunrise
print(f"recovered: lat {lat_rec:.3f}, lon {lon_rec:.3f}")
print(f"true:      lat {lat_true:.3f}, lon {lon_true:.3f}")
# observed: UTC sunrise 19.0219 h, daylight 13.8229 h
# recovered: lat -33.000, lon 151.000
# true:      lat -33.000, lon 151.000

The inversion returns the hidden latitude and longitude to the displayed precision: two timed calls are enough.

Riddler Classic

The year is $1942$ . The Germans field a tank, the Uberpanzer, stamped with a serial number equal to how many had been built when it left the line ( $1, 2, 3, \dots$ ). British scouts recorded the serial numbers of several tanks they saw, but a spy destroyed the data; only two figures survived: the lowest recorded serial number was $22$ and the highest was $114$ . What is the best estimate of the total number of Uberpanzers built?

The Riddler, FiveThirtyEight, June 7, 2019(original post)

Solution

This is the German tank problem, but with a twist: we do not know how many tanks were seen, only the smallest and largest serial numbers, $L = 22$ and $M = 114$ . The idea is a symmetry argument that does not need the sample size.

Suppose the sample is a random subset (no repeats) of $\{1, 2, \dots, N\}$ . The gaps the sample leaves are, on average, all the same size: the gap below the minimum, the gaps between consecutive observed values, and the gap above the maximum. So the minimum sits as far above $1$ as the maximum sits below $N$ . In expectation, $L - 1 \;=\; N - M,$ because the expected distance from the smallest observation down to the bottom of the range equals the expected distance from the largest observation up to the top. Equivalently, by the symmetry of a random subset under $x \mapsto N + 1 - x$ , the minimum and maximum are mirror images, so $\mathbb{E}[L + M] \;=\; N + 1.$ Rearranging $L - 1 = N - M$ gives the single best estimate $\widehat{N} \;=\; M + L - 1 \;=\; 114 + 22 - 1 \;=\; \boxed{135}.$ The usual textbook formula $\widehat{N} = M + M/k - 1$ needs the sample size $k$ to estimate the average gap as $M/k$ ; here we are denied $k$ , so we use the smallest observation itself, $L - 1$ , as our read on how much room sits below the minimum, and add it to the maximum.

The computation

Encode the sampling experiment, not the estimator. Fix a true $N$ , draw a random sample of some size from $\{1, \dots, N\}$ , record its minimum and maximum, and average $L + M$ over many samples. If that average is $N + 1$ regardless of the sample size, then $M + L - 1$ is the natural single estimate of $N$ , and at $L = 22, M = 114$ it reads $135$ .

import random
rng = random.Random(0)
for N in (135, 200):
    for k in (2, 5, 12):
        s = 0; T = 200_000
        for _ in range(T):
            samp = rng.sample(range(1, N + 1), k)
            s += min(samp) + max(samp)
        print(f"N={N}, k={k}: E[min+max]={s / T:.2f}  (N+1={N + 1})")
print("estimate from L=22, M=114:", 114 + 22 - 1)
# E[min+max] hugs N+1 for every sample size k; estimate = 135

The expectation of $L + M$ sits on $N + 1$ for every sample size, confirming that $\widehat{N} = M + L - 1 = 135$ is the right single estimate when the sample size is unknown.