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 6 of 6: Match the construction and upper bound
Previous stepNext step
[n2−n(n−1)2−c(n−c+1)]+n(n−1)2=n2+c2−nc−c\left[n^2-\frac{n(n-1)}2-c(n-c+1)\right]+\frac{n(n-1)}2=n^2+c^2-nc-c
Detailed analysis

The diagonal strategy saves every house on levels greater than n−1, while the induction gives the maximum possible saving on the lower levels. Adding the two contributions simplifies to n squared+c squared−nc−c, so this is the maximum.