When Will Your House Collapse? Should You Take A Construction Contract?

Riddler Express

You live in a row house, one of $36$ on your side of the block. After the city is evacuated, the worst-maintained house collapses two years later. Every two years thereafter, two new collapses happen: any house adjacent to one already collapsed falls, and the next-worst-maintained still-standing house falls. (Maintenance rankings are fixed at evacuation.) Assuming a random ranking, what is the longest your house can stand, and the fewest years until all $36$ are rubble? How do these answers change for $N$ houses?

The Riddler, FiveThirtyEight, June 1, 2018(original post)

Solution

Number the houses $1, 2, \ldots, N$ along the street, and let house $r_k$ be the $k$^th worst-maintained ($r_1$ falls in round $1$, etc.). In round $k$ (at year $2k$), two things happen: rank-$k$ house $r_k$ collapses if still standing, and every standing house adjacent to a fallen house collapses.

Longest survival. You want to delay your collapse. Make your own house the best-maintained ($r_N$ = your house), and arrange the rankings so the contagion creeps along the street away from you. Put your house at one end, say position $N$. Place $r_1$ at position $1$ (far end). For the maintenance-driven collapses not to leapfrog the contagion, place $r_2, r_3, \ldots$ in positions $2, 3, \ldots$ in order. Then in round $k$ the contagion reaches position $k$ at the same time the rank-$k$ house at that position is scheduled to fall; the wavefront moves one position per round. Your house falls in round $N$, that is, year $2N$. For $N = 36$, that is $\boxed{72 \text{ years}}$.

This is the best you can do: each round at least one new position collapses, and the only positions still standing form a contiguous block at your end (otherwise a standing house would be adjacent to a fallen one and fall by contagion). So the block shrinks by at least one per round, and you survive at most $N$ rounds.

Fastest total collapse. Now you want to maximise collapses per round. In round $1$ the worst house falls (one house). In round $2$ the two neighbours of $r_1$ fall by contagion, plus $r_2$ somewhere fresh: three new collapses, if $r_2$ is placed away from $r_1$. In round $3$ the new $r_2$ has two fresh neighbours fall, the original block grows by another two, and $r_3$ starts a third front: five new collapses. The pattern is $1, 3, 5, 7, \ldots$ per round. We need $$1 + 3 + 5 + \cdots + (2K - 1) \;=\; K^{2} \;\ge\; N,$$ which gives $K = \lceil \sqrt{N} \rceil$. For $N = 36$, $K = 6$, that is $\boxed{12 \text{ years}}$.

To achieve $1 + 3 + 5 + \cdots$ exactly, place each seed strictly in the interior, so contagion eats both neighbours every subsequent round, and arrange the seeds so the blocks merge only at the very end. After $k$ rounds the block seeded at round $j \le k$ has length $2(k - j) + 1$. For $N = 36$ and six rounds, the final block lengths are $11, 9, 7, 5, 3, 1$, which sum to $36$ exactly. Filling $[1, 36]$ from left to right with these lengths gives seeds at positions $r_1 = 6$, $r_2 = 16$, $r_3 = 24$, $r_4 = 30$, $r_5 = 34$, $r_6 = 36$. Every round contagion produces $2 \cdot (k - 1)$ collapses (two per active block) and the new seed adds one, totalling $1, 3, 5, 7, 9, 11$ as required.

General $N$.

The computation

Encode the problem: given a maintenance ranking and a house index, simulate the round-by-round collapse and record both the year your house falls and the year all houses fall. Search over rankings to test the bounds.

1. Implement simulate(r, h, N) which returns (year house $h$ falls, year all houses have fallen).

2. For $N = 36$: try the constructive rankings for the longest-survival and fastest-collapse layouts and confirm they yield $72$ and $12$ respectively.

3. Verify the longest-survival bound by random search: no random ranking ever lets house $h$ survive past round $N$.

import random

def simulate(rank, h, N):
    """rank[k] = position of the k-th-worst house, k = 0..N-1."""
    standing = [True] * (N + 2)  # padding at 0 and N+1
    year_h = None; year_all = None
    for k in range(N):
        to_fall = set()
        for i in range(1, N + 1):
            if standing[i] and (not standing[i-1] or not standing[i+1]):
                to_fall.add(i)
        if standing[rank[k]]:
            to_fall.add(rank[k])
        for i in to_fall:
            standing[i] = False
        if year_h is None and not standing[h]:
            year_h = 2 * (k + 1)
        if all(not standing[i] for i in range(1, N + 1)):
            year_all = 2 * (k + 1)
            break
    return year_h, year_all

N = 36
# Longest survival: r_k at position k (worst far from your house)
rank = list(range(1, N + 1))
print("longest survival:", simulate(rank, N, N))

# Fastest collapse: seeds at 6, 16, 24, 30, 34, 36
seeds = [6, 16, 24, 30, 34, 36]
rank_fast = seeds + [p for p in range(1, N + 1) if p not in set(seeds)]
print("fastest collapse:", simulate(rank_fast, N, N))

# Random check: bound is 2N = 72
worst = 0; random.seed(0)
for _ in range(20000):
    r = list(range(1, N + 1)); random.shuffle(r)
    h = random.randint(1, N)
    yh, _ = simulate(r, h, N)
    if yh and yh > worst: worst = yh
print("max over 20k random:", worst, "<= 2N =", 2 * N)

The constructive longest-survival layout prints (72, 72) and the fastest-collapse layout prints (12, 12). The random search never exceeds $72$, confirming the bound.

Riddler Classic

Four towns sit at the corners of a square of side $10$ miles. The state offers $\$28$ million for a road system linking all four towns; road costs $\$1$ million per mile. Can you turn a profit? How does the answer change for five towns at the corners of a regular pentagon, six at a hexagon, and so on?

The Riddler, FiveThirtyEight, June 1, 2018(original post)

Solution

This is a Steiner tree problem: find the shortest network connecting four (or $N$) points, allowed to add interior junctions. The candidates and their lengths:

• Perimeter $\sqcap$ shape (three sides): $30$ miles.

• Diagonal $\times$ shape (two diagonals, single central junction): $20 \sqrt{2} \approx 28.28$ miles.

• $H$ shape (two T-junctions on opposite sides): $30$ miles.

• TIE-fighter / honeycomb (two Steiner points pulled inward): the minimum.

The honeycomb. Place the towns at $(\pm 5, \pm 5)$ and the two Steiner points on the $x$-axis at $(\pm a, 0)$, with $0 \le a \le 5$. Each Steiner point joins two towns and the central segment, so $$D(a) \;=\; 4 \sqrt{(5 - a)^{2} + 25} \;+\; 2 a.$$ Setting $D'(a) = 0$: $$-\frac{4(5 - a)}{\sqrt{(5 - a)^{2} + 25}} \;+\; 2 \;=\; 0 \;\;\Longrightarrow\;\; 4(5 - a)^{2} \;=\; (5 - a)^{2} + 25,$$ so $(5 - a)^{2} = 25/3$, giving $a = 5 - 5/\sqrt{3}$. The minimum length is $$\begin{aligned} D_{\min} &\;=\; 4 \sqrt{\tfrac{25}{3} + 25} + 2 \left(5 - \tfrac{5}{\sqrt{3}}\right) \\ &\;=\; \tfrac{40}{\sqrt{3}} + 10 - \tfrac{10}{\sqrt{3}} \;=\; 10 \sqrt{3} + 10 \;\approx\; 27.32\ \text{miles}. \end{aligned}$$ At each of the two Steiner points, three road segments meet at exactly $120^{\circ}$, the Steiner condition for a minimum. Cost is $\$27.32$ million; the $\$28$ million contract clears a profit of $$\boxed{\;\$28\,000\,000 - \$10(1 + \sqrt{3}) \cdot 10^{6} \;\approx\; \$679\,492.\;}$$

General $N$. For a regular $N$-gon of side $s$, the minimum Steiner tree has different structure as $N$ grows.

• $N = 3$: one Steiner point at the centroid, total length $s \sqrt{3}$.

• $N = 4$: two Steiner points, total length $s(1 + \sqrt{3}) \approx 2.732\,s$.

• $N = 5$: three Steiner points; numerical minimum at $s = 10$ is approximately $38.91$ miles, that is $\approx 3.891\,s$.

• $N \ge 6$: the elegant Steiner-point pattern breaks down. The minimum is simply $(N - 1) \cdot s$, the perimeter minus one side, with no interior junctions.

At $\$1$ million per mile and a $\$28$ million contract, the profit is positive only for $N = 3$ and $N = 4$ at $s = 10$: $$\begin{array}{c|c|c} N & \text{road (miles)} & \text{profit (\$M)} \\\hline 3 & 10\sqrt{3} \approx 17.32 & +10.68 \\ 4 & 10(1 + \sqrt{3}) \approx 27.32 & +0.68 \\ 5 & \approx 38.91 & -10.91 \\ 6 & 50 & -22.00 \\ N \ge 6 & 10(N - 1) & 28 - 10(N - 1) \end{array}$$ The contract is a profitable bid only at $N = 3$ or $N = 4$. For $N \ge 5$, walk away.

The computation

For the square, verify the $D(a)$ minimum symbolically with sympy. For the pentagon, place the five vertices on a unit circle and solve the Steiner-tree placement numerically by free-coordinate optimisation over three Steiner points.

import math
import numpy as np
from sympy import symbols, sqrt, diff, solve, simplify
from scipy.optimize import minimize

# Square: symbolic derivation
a = symbols('a', real=True, positive=True)
D = 4 * sqrt((5 - a)**2 + 25) + 2 * a
print("square Steiner a =", [simplify(c) for c in solve(diff(D, a), a)])
a_star = 5 - 5 / math.sqrt(3)
D_star = 4 * math.sqrt((5 - a_star)**2 + 25) + 2 * a_star
print(f"square length = {D_star:.4f}, profit = ${(28 - D_star)*1e6:,.0f}")

# Pentagon: numerical Steiner tree on 5 vertices
def pentagon(s=10):
    R = s / (2 * math.sin(math.pi / 5))
    return [(R*math.cos(2*math.pi*k/5 + math.pi/2),
             R*math.sin(2*math.pi*k/5 + math.pi/2)) for k in range(5)]

def steiner_length(p, t):
    """Tree: T0-S0-T1, S0-S1-T2, S1-S2, S2-T3, S2-T4."""
    s = p.reshape(3, 2)
    edges = [(t[0], s[0]), (t[1], s[0]), (s[0], s[1]), (t[2], s[1]),
             (s[1], s[2]), (t[3], s[2]), (t[4], s[2])]
    return sum(math.hypot(a[0]-b[0], a[1]-b[1]) for a, b in edges)

vs = pentagon()
init = np.array([vs[0][0], vs[0][1], 0.0, 0.0, vs[3][0], vs[3][1]])
res = minimize(steiner_length, init, args=(vs,))
print(f"pentagon length = {res.fun:.4f}, profit = ${(28-res.fun)*1e6:,.0f}")

Sympy prints the critical point $a = 5 - 5/\sqrt{3}$, the square length $10(1 + \sqrt{3}) \approx 27.32$ miles, and the profit $\$679\,492$. The pentagon optimisation prints $\approx 38.91$ miles, a $\$10.91$M loss. The boxed answer for the square holds, and the strategy switches sign at $N = 5$.