MathDB

In a small town, there are

n \times n

houses indexed by

(i, j)

for

1 \leq i, j \leq n

with

(1, 1)

being the house at the top left corner, where

i

and

j

are the row and column indices, respectively. At time 0, a fire breaks out at the house indexed by

(1, c)

, where

c \leq \frac{n}{2}

. During each subsequent time interval

[t, t+1]

, the fire fighters defend a house which is not yet on fire while the fire spreads to all undefended neighbors of each house which was on fire at time t. Once a house is defended, it remains so all the time. The process ends when the fire can no longer spread. At most how many houses can be saved by the fire fighters? A house indexed by

(i, j)

is a neighbor of a house indexed by

(k, l)

|i - k| + |j - l|=1

Problem Statement