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 2 of 6: Count houses saved by the strategy
Detailed analysis
In the two symmetric columns at distances 0,1,...,c-1 from column c, the strategy saves n-1,n-2,...,n-c houses. In each of the remaining n-2c columns it saves n-c houses. Adding gives n squared+c squared−nc−c.