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)$ if $|i - k| + |j - l|=1$.
Problem
Source: APMO 2005 Problem 4
Tags: inequalities, geometry, perimeter, induction, algorithm, combinatorics unsolved, combinatorics
23.03.2005 17:14
Finally we can discuss it
23.03.2005 17:20
I personally think that it takes 20 minutes to read and understand the question completely.
23.03.2005 17:59
to be frank, i still dun really understand this question till now............. does it mean that, only ONE random house broke out of fire at first?
23.03.2005 19:16
siuhochung wrote: to be frank, i still dun really understand this question till now............. does it mean that, only ONE random house broke out of fire at first? Yes, I believe that $c$ is a fixed number. Only house is on fire initially. And we seek for an answer in terms of $n$ and $c$.
23.03.2005 19:44
Answer: $n^2 - n$
23.03.2005 20:01
Answer: $(n-c)*n$ The trick is to first defend the house (1,c+1) then (2,c+1) , then (3,c+1) and so on ... till (n,c+1). Thus you would have defended all the houses in the coloumn $c+1$ hence total number of houses defended would be $(n-c)*n$
23.03.2005 20:35
Well, symmetricmean, of course you could defend some more houses (namely $c-2$ ) once you've saved $(1, c+1), ..., (n, c+1)$, so it would be $n^2-cn+c-2$, but that isn't optimal. I didn't get this problem at the APMO but other contestants told me that saving $(2, c)$ first, one would get the fire spreading in 2 directions and could save houses on each side alternately giving a V-like pattern (this is easier to see in a diagram), which is more efficient. However, no one I know gave a rigorous proof that this was optimal, either.
23.03.2005 22:51
I agree with Severius; this v-shaped pattern yields the formula $n(n-c)+c^2-c$, which is larger than $n(n-c)$. However, I do not have a rigorous proof that this is optimal either.
24.03.2005 15:37
It isn't hard at all to show that the fighters can save at least $n(n-c)+c(c-1)$ houses... But then, why can't they save mor houses? Here are some ideas i thought, although i don't know if they work because it is very dificult to formally prove them. In the test i did a solution, but asumming this two lemmas were true (1) First name the houses with numbers, acording to their minimal distance (how many houses they have to walk) to the house $(1,c)$. Then it would help a lot if we could prove that "the more convenient" thing to do is to save houses with different numbers.. i.e. not to save a house with number 5 in the fourth turn, because saving a house with number 4 would "help" also to protect that house with number 5. (2) In an optimal pattern, it is "not convenient" to save two houses in the same column. This is intuitively right, because how could it be convenient to save two houses from the same column, if we want to make an "horizontal barrier"?? (well, we can make a vertical barrier with $c=1$, but in the other cases is almost evident that the best thing to do is a conected barrier that covers from row 1 to $n$). It can be easily proved that we must have at least one saved house per column. So here we can also think about the number of turns the fire can spread. If anyone has solved the problem i would like him/her to post some hints to formalize things here...
25.03.2005 21:21
I have not solved the problem, but it seems like the following logic is workable: 1) Show that after the kth rescue (defending a house at time k), there are at least k dangerous houses (a dangerous house is a house on fire that can still spread to at least one of its neighbours) 2) Using 1), show that after the kth rescue, at least k+1 more houses will be lit up on fire. 3) Using 2), we can effectively calculate the rest of the problem. Now of course, 1) wouldn't be true for big k (namely k>c) but for the time being, we can suppose that c is sufficiently large for us to recognize and formally prove the above patterns. Does this help anyone?
26.03.2005 02:23
I triedo some inequalities with the perimeter of the endangered zone and the longest walk of house on fire....It could work but i reallly screwed everything in this exam...
29.03.2005 06:41
Can someone post a valid solution please?
29.03.2005 13:10
This isn't something I came up with myself, it's the official solution. Label the houses according to their "distance" from (1,c) as suggested by RaMlaF: say that house (i, j) is at level t if $\mid i - 1\mid + \mid j - c\mid = t $. Let d(t) be the number of houses at level t defended by time t, p(t) the number of houses at level t + 1 or greater defended by time t. Clearly $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 by induction that $s(t) \leq t - p(t)$ for $1\leq t \leq n-1$. The base case t = 1 is clearly true, so suppose it is true when t = k. At time k + 1, consider the set M(k+1) of the s(k+1) - d(k+1) houses at level k+1 that do not burn but are not themselves defended. These houses survive because all their neighbours at level k do not burn. There are at least s(k+1) - d(k+1) houses at level k that are neighbours of at least one house in M(k+1), so there must be at least s(k+1) - d(k+1) houses at level k that do not burn; that is, $s(k) \geq s(k+1) - d(k+1).$ But by the inductive hypothesis $s(k) \leq k - p(k)$, so $s(k+1) - d(k+1) \leq k - p(k)$. Hence, using (*), $s(k+1) \leq k - p(k) + d(k+1) \leq k + 1 - p(k+1)$ also. $p(t) \geq 0$ for all t, so from that it follow that $s(t) \leq t$ for all $1\leq t \leq n-1$. Summing, we find that at most $\frac 12 n(n-1)$ houses at levels n-1 or below can be defended. It is easy to see that the v-shaped algorithm described by Severius and others saves exactly this many houses at levels n-1 and below, and every house at level n and above, so this must be the optimal algorithm, and at most $n(n-c) + c(c-1)$ houses can be saved.
12.04.2005 08:37
the Solution : n^2+c^2-nc-c I have a hard copy of the APMO solutions but I can't post to here ,I can't use the system
02.10.2005 06:05
Can we extend the problem with arbitary (i, j). Anyone has some idea for it ?
02.10.2005 06:06
Can we extend the problem with arbitary (i, j). Anyone has some idea for it ?