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 3 of 6: Organize houses into fire levels
Detailed analysis
Call a house at level t when its Manhattan distance from (1,c) is t. Let d(t) be the number of level-t houses defended by time t, p(t) the number of houses at levels greater than t defended by time t, and s(t) the number of level-t houses not burning at time t. Since one house is defended per time, p(t)+d(t) is at most t, and p(t+1)+d(t+1) is at most p(t)+1.