another interesting but harder problem

[borisp]

Suppose you have a nxn grid of "cells," represented by squares, as on an nxn checkerboard. Some of them are "infected," the rest are not.

If an uninfected cell shares at least two edges with an infected cell, then the uninfected cell becomes infected. This process continues until the set of infected cells stabilizes.

The problem is to prove the following statement, using less than two sentences. (In other words, inductive arguments and computer simulations are unacceptable; the point is to find an elegant solution.)

"If the entire grid is infected at the end of the process, then at least n squares had to be infected to begin with."

[blah_blah]

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.

[borisp]

Holy crap, that is easily the fastest correct solution that I have seen, and I have posed this to many very smart people. You haven't seen this before?

In any event, this is exactly the response I was looking for.

[blah_blah]

[ QUOTE ]
Holy crap, that is easily the fastest correct solution that I have seen, and I have posed this to many very smart people. You haven't seen this before?

In any event, this is exactly the response I was looking for.

[/ QUOTE ]

it seemed like a natural thing to look at, except that at first I thought that the perimeter of the boundary would be increasing in time. After I tried some small cases and saw that the opposite was in fact true, the proof quickly followed /images/graemlins/smile.gif

[borisp]

...and the finite time follows simply from the pigeonhole principle.

[blah_blah]

[ QUOTE ]
...and the finite time follows simply from the pigeonhole principle.

[/ QUOTE ]

of course, but I was already at three sentences and didn't want to incur your wrath /images/graemlins/smile.gif. is your solution the same?

[borisp]

I accept any answer that involves "perimeter" and "nondecreasing" /images/graemlins/smile.gif

[borisp]

er, nonincreasing, but if you've solved it, you know what i mean