MathLabs

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 5 of 6: Count the upper bound
Previous stepNext step
∑t=1n−1s(t)≤∑t=1n−1t,∣{ℓ>n−1}∣=n2−n(n−1)2−c(n−c+1)\sum_{t=1}^{n-1}s(t)\le\sum_{t=1}^{n-1}t,\quad |\{\ell>n-1\}|=n^2-\frac{n(n-1)}2-c(n-c+1)
Detailed analysis

Thus at most the sum of 1 through n−1 houses on levels at most n−1 can be saved. Directly counting the grid points on those levels gives n(n−1)/2+c(n−c+1); all remaining levels contain n squared minus this number of houses.