Q4 Matemática  (APMO 2005)

Em uma cidade pequena, existem $n\times n$ casas indexadas por $(i,j)$ por $1\le i,j\le n$ sendo $(1,1)$ a casa no canto superior esquerdo , onde $i$ e $j$ são os índices de linha e coluna, respectivamente. No instante 0, ocorre um incêndio na casa indexada por $(1,c)$, onde $c\le \frac{n}{2}$. Durante cada intervalo de tempo subsequente $[t,t+1]$, os bombeiros defendem uma casa que ainda não está pegando fogo enquanto o fogo se espalha para todos os vizinhos indefesos de cada casa que estava pegando fogo no momento t. Uma vez que uma casa é defendida, ela permanece assim o tempo todo. O processo termina quando o fogo não pode mais se espalhar. No máximo quantas casas podem ser salvas pelos bombeiros? Uma casa indexada por $(i,j)$ é vizinha de uma casa indexada por $(k,l)$ se $|i-k|+|j-l|=1$.