Re: another interesting but harder problem
I hope this works.
Let p(t) denote the sum of the perimeters of the disjoint polygons formed by the infected squares at time t. p(t) is decreasing in t. If the entire grid is infected at time T (>0), p(T) = 4n. But if less than n squares are infected at the beginning, we have p(0)<=4*{# of initially infected squares}<4n, a contradiction, since p(0) >= p(T).
There probably should be some proof that the grid reaches its final state in time T < infinity, but this is more or less trivial.
|