Who Steals The Most In A Town Full Of Thieves?

Riddler Express

You’re driving a car down a two-mile track. For the first mile, you drive 30 miles per hour. How fast do you have to go for the second mile in order to average 60 miles per hour for the whole track?

Solution

Average speed over a fixed distance is total distance over total time, so it is the time, not the speed, that must add up. To average $60$ mph over two miles you would need a total time of $2/60$ hours, which is $2$ minutes. But the first mile alone, driven at $30$ mph, already takes $1/30$ hour, which is exactly $2$ minutes. The entire time budget is spent before the second mile begins. Solving $60 = 2\big/\!\left(\tfrac{1}{30} + \tfrac{1}{s}\right)$ for the second-mile speed $s$ forces $\tfrac1s = 0$, so $$\boxed{\text{no finite speed works}.}$$ You would have to cover the second mile in zero time, that is, infinitely fast.

The computation

Solve the average-speed equation symbolically and watch it demand an infinite speed.

import sympy as sp
s = sp.symbols('s', positive=True)
print(sp.solve(sp.Eq(2 / (sp.Rational(1, 30) + 1 / s), 60), s))   # []
print(sp.limit(2 / (sp.Rational(1, 30) + 1 / s), s, sp.oo))       # 60

Riddler Classic

A town of $1{,}000$ households has a strange law intended to prevent wealth-hoarding. On January $1$ of every year, each household robs one other household, selected at random, moving all of that house’s money into their own house. The order in which the robberies take place is also random and is determined by a lottery. (If House A robs House B first, and then C robs A, the houses of A and B would each be empty and C would have acquired the resources of both.) What is the probability that a house is not robbed over the course of the day? And if every house starts with $100, which lottery position has the most expected cash at the end, and how much?

Solution

Who escapes. Fix a house $H$. Each of the other $999$ houses independently chooses its victim uniformly among the $999$ houses that are not itself, so it picks $H$ with probability $1/999$. House $H$ is spared only if none of them choose it: $$\Pr(H \text{ not robbed}) = \left(1 - \frac{1}{999}\right)^{999} \approx \boxed{0.368},$$ which is essentially $e^{-1}$. About $36.8\%$ of the town goes untouched.

Who wins. The best slot is the last. A house acting last can never be robbed afterward, so it keeps everything it holds at the end: its own money plus its victim’s. Its own $100 survives only if none of the $999$ earlier robbers took it, worth $100\,(998/999)^{999} \approx \$36.77$ on average. Its victim is a uniformly random other house, and since the $100,000 in town is conserved, the other $999$ houses hold $100,000 minus this house’s own cash, so a random one of them holds on average $(100000 - 36.77)/999 \approx \$100.06$. Adding the two parts, $$\mathbb{E}[\text{last house}] \approx 36.77 + 100.06 \approx \boxed{\$137}.$$ Acting earlier is strictly worse: it exposes you to being robbed afterward (wiping you out) and your victim has had less time to accumulate. So the last lottery position wins, with about $137.

The computation

Run the town: give every house a random victim and a random lottery order, carry out the robberies in that order, and tally both the fraction of houses left untouched and the average final cash in each lottery position.

import numpy as np
rng = np.random.default_rng(0)
n, runs = 1000, 40000
safe = 0.0; by_pos = np.zeros(n)
for _ in range(runs):
    t = rng.integers(0, n - 1, n); t += (t >= np.arange(n))   # victim != self
    safe += (n - len(set(t.tolist()))) / n          # houses nobody targeted
    order = rng.permutation(n)
    cash = np.full(n, 100.0)
    for h in order:
        cash[h] += cash[t[h]]; cash[t[h]] = 0.0
    by_pos += cash[order]                            # cash by lottery position
print(safe / runs)                                   # ~0.368
print(by_pos[-1] / runs, "at the last position")     # ~137, the maximum