During 6.042, the students are sitting in an $n$ × $n$ grid. A sudden outbreak of beaver flu
(a rare variant of bird flu that lasts forever; symptoms include yearning for problem sets
and craving for ice cream study sessions) causes some students to get infected. Here is an
example where $n = 6$ and infected students are marked ×.
Now the infection begins to spread every minute (in discrete time-steps). Two students are
considered adjacent if they share an edge (i.e., front, back, left or right, but NOT diagonal);
thus, each student is adjacent to $2, 3,$ or $4$ others. A student is infected in the next time step
if either:
- the student was previously infected (since beaver flu lasts forever), or
- the student is adjacent to at least two already-infected students.
In the example, the infection spreads as shown below.
In this example, over the next few time-steps, all the students in class become infected.
Theorem. If fewer than $n$ students in class are initially infected, the whole class will never
be completely infected.
Prove this theorem.
Hint: When one wants to understand how a system such as the above “evolves” over time,
it is usually a good strategy to (1) identify an appropriate property of the system at the
initial stage, and (2) prove, by induction on the number of time-steps, that the property is
preserved at every time-step. So look for a property (of the set of infected students) that
remains invariant as time proceeds.
Source: MIT OCW Mathematics for Computer Science, Problem Set 2, Problem 3.
I am not really sure of how I can prove this. I went out on a limb and assumed that I would be using induction since this seems like a problem that requires an invariant to be used to prove the theorem.
Another thing that I have realized is that if $k$ students are initially infected, then the perimeter of the figure formed by the infected students as the infection spread is at most $4k$. So, this might be my invariant.
So, this is what I have thus far:
Theorem: If fewer than $n$ students in class are initially infected, the whole class will never
be completely infected.
Proof: by induction
I would appreciate any and all hints that would help me get the ball rolling with this proof.
Best Answer
You solved your own problem! Consider the length of the boundary. If there are $<n$ infected squares initially, then the length is at most $4(n-1)$. It cannot increase, but if we end up with all squares infected the boundary would be length $4n$.
In the diagram below consider what happens when square $b$ becomes infected. In the first case we get new boundary above and below it (because $a,c$ are uninfected), but we lose the boundary on either side of $b$, so there is no net change.
In the second case, we have a net loss of 2 (we lose three sides of boundary and only gain 1). In the third case we have a net loss of 4.
So in all cases, we cannot increase the total length of boundary - we must lose at least 2 and can gain at most 2.