APMO - March, 2005

At most $n^{2}+c^{2}-n c-c$ houses can be saved. This can be achieved under the following order of defending:
$$\begin{gather*} (2, c), (2, c+1); (3, c-1), (3, c+2); (4, c-2), (4, c+3); \ldots \\ (c+1, 1), (c+1, 2c); (c+1, 2c+1), \ldots, (c+1, n) \end{gather*}$$

Under this strategy, there are

2 columns (column numbers $c$, $c+1$) at which $n-1$ houses are saved

2 columns (column numbers $c-1$, $c+2$) at which $n-2$ houses are saved

⋯

2 columns (column numbers $1$, $2c$) at which $n-c$ houses are saved

$n-2c$ columns (column numbers $n-2c+1, \ldots, n$) at which $n-c$ houses are saved

Adding all these we obtain:
$$\begin{equation*} 2[(n-1)+(n-2)+\cdots+(n-c)] + (n-2c)(n-c) = n^{2}+c^{2}-c n-c \end{equation*}$$

We say that a house indexed by $(i, j)$ is at level $t$ if $|i-1|+|j-c|=t$. Let $d(t)$ be the number of houses at level $t$ defended by time $t$, and $p(t)$ be the number of houses at levels greater than $t$ defended by time $t$. It is clear that
$$p(t) + \sum_{i=1}^{t} d(i) \leq t \text{ and } p(t+1) + d(t+1) \leq p(t) + 1$$
Let $s(t)$ be the number of houses at level $t$ which are not burning at time $t$. We prove that
$$s(t) \leq t - p(t) \leq t$$
for $1 \leq t \leq n-1$ by induction. It is obvious when $t=1$. Assume that it is true for $t=k$. The union of the neighbors of any $k-p(k)+1$ houses at level $k+1$ contains at least $k-p(k)+1$ vertices at level $k$. Since $s(k) \leq k-p(k)$, one of these houses at level $k$ is burning. Therefore, at most $k-p(k)$ houses at level $k+1$ have no neighbor burning. Hence we have
$$\begin{aligned} s(k+1) &\leq k-p(k)+d(k+1) \\ &= (k+1) - (p(k)+1-d(k+1)) \\ &\leq (k+1) - p(k+1) \end{aligned}$$

We now prove that the strategy given above is optimal. Since
$$\sum_{t=1}^{n-1} s(t) \leq \binom{n}{2},$$
the maximum number of houses at levels less than or equal to $n-1$, that can be saved under any strategy is at most $\binom{n}{2}$, which is realized by the strategy above. Moreover, at levels bigger than $n-1$, every house is saved under the strategy above.

The following is an example when $n=11$ and $c=4$. The houses with $\bigcirc$ mark are burned. The houses with $\otimes$ mark are blocked ones and hence those and the houses below them are saved.