Prove that if fewer than $n$ students in class are initially infected, the whole class will never be completely infected.

Question

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 ×.

Example.

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.

Example.

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.

Answer 1

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.

Answer 2

Theorem: If fewer than $n$ students in class are initially infected, the whole class will never be completely infected.

Proof: by induction. We define perimeter of an infected set of students as the number of edges with infection on exactly one side. We let $x$ denote the size of the perimeter.

Let $P(k)$ be the proposition that after $k$ discrete time-steps, the perimeter is less than $4n$.

Base Case: $P(0)$ is true.

This is trivially true since the perimeter could not have possible changed after $0$ discrete time-steps. The perimeter of the infected region remains to be $x$.

Inductive Step: for all nonnegative integers, we must show that $P(k)\Rightarrow P(k+1)$

We assume that $P(k)$ is true for purposes of induction. So, this means that we are assuming that the perimeter of the infeted region is at most $x$ after $k$ steps.

At step $k + 1$, the perimeter of the infected region can only change in two ways. Since each newly infected square is adjacent to at least two previously infected squares, each newly infected square can either:

lose at least two edges from the perimeter of the infected region, or add at most two edges to the perimeter. Therefore, the perimeter of the infected region cannot increase.

So, we have shown that for all nonnegative integers, $k$, $P(k)\Rightarrow P(k+1)$

Q.E.D.

Answer 3

Proof by Induction. Define the perimeter of an infected set of students to be the number of edges with infection on exactly one side. Let ν be size (number of edges) in the perimeter.

We claim that ν is a weakly decreasing variable. This follows because the perimeter changes after a transition only because some squares became newly infected. By the rules above, each newly infected square is adjacent to at least two previously-infected squares. Thus, for each newly infected square, at least two edges are removed from the perimeter of the infected region, and at most two edges are added to the perimeter. Therefore, the perimeter of the infected region cannot increase.

Now if an n × n grid is completely infected, then the perimeter of the infected region is 4n. Thus, the whole grid can become infected only if the perimeter is initially at least 4n. Since each square has perimeter 4, at least n squares must be infected initially for the whole grid to become infected.