Problem 4
In an n by n town, houses are indexed by (i,j), with (1,1) at the top left. Initially the house (1,c) burns, where c is at most n/2. During each unit interval firefighters defend one unburned house, then fire spreads to every undefended neighbor of each house burning at the start of the interval. Defended houses remain defended. What is the maximum number of houses that can be saved? Neighbors differ by one in exactly one coordinate.
Step 4 of 6: Inductively bound each level
Detailed analysis
We prove s(t)≤t−p(t). It is clear at t=1. If it holds at t=k, then among any k−p(k)+1 houses of level k+1, their neighbors contain at least that many level-k houses, while at most s(k) of level k are unburned. Hence at most k−p(k) houses of level k+1 avoid a burning neighbor. After accounting for d(k+1) defended houses, s(k+1)≤k−p(k)+d(k+1). The bookkeeping inequality p(k+1)+d(k+1)≤p(k)+1 from Step 3 is equivalent to k−p(k)+d(k+1)≤(k+1)−p(k+1), proving the induction step.