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 1 of 6: Give a defense strategy
Detailed analysis
Defend, in order, the two houses (i,c+2-i) and (i,c+i-1) for i=2 through c+1, then defend (c+1,j) for j=2c+1 through n. Every listed house is still unburned when defended; this is the diagonal strategy in the official solution.