Азиатско-Тихоокеанская математическая олимпиада, 2005 год

В маленьком городке имеется ${{n}^{2}}$ домов, индексированных парами чисел $(i,j)$ для $1\leq i,j\leq n$. Дома с индексами $(i,j)$, $(k,l)$ назовем соседними, если $|i-k|+|j-l|=1$. В момент времени 0, в доме с индексом $(1,c)$, где $c\leq \frac{n}{2}$, начался пожар. В течение каждого последующего временного интервала $[t,t+1]$ пожарники ставят систему защиты от пожара одному дому, до которого огонь еще не добрался, в то время как пожар распространяется на все незащищенные дома, каждый из которых соседствуют с некоторым домом, охваченным пожаром в момент времени $t$. Дом, где установлена система защиты от пожара, не горит. Процесс завершается, когда распространение пожара становится невозможным. Какое максимальное число домов могут спасти пожарники?
Замечание. Можно считать, что городок имеет форму таблицы $n\times n$, где дома суть единичные клетки, $(1,1)$ — индекс дома, стоящего в левом верхнем углу, $i$ и $j$ указывают соответственно строку и столбец дома с индексом $(i,j)$.