Understanding “perimeter” invariant

discrete mathematicsinductioninvariance

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.

Unfortunately, I could not solve this problem and had to look up the solution. But even after looking at the solution, the whole thing doesn't make complete sense to me. I think I might be misunderstanding what perimeter means (Define the perimeter of an infected set of students to be the number of edges with infection on exactly one side). I currently have two problems in understanding the solution –

  1. When I calculate the perimeter of the infected students in the starting state, I get 30, when I should be getting n*4 = 6*4 = 24. Here's how.

  2. The solution also states that for every infected student added, the edges subtracted from the perimeter of the previous state is neutralized by the edges of the new infected student. What about this case?

Also, as a more general question, how does one go about identifying the invariant property for such questions?

Best Answer

Here is what I think is going on:

In the example, the inital perimeter really is $30$. But, maybe the invariant is not that the perimeter always stays the same .... but that it always stays below $4n$. So, the fact that in your example the perimeter decreases would be just fine ... as long as it does not increase, then if the perimeter at the start is below $4n$ (which it is if there are fewer than $n$ initially infected students) it will never reach $4n$ ... which is what the perimeter of a 'full' board is. So, to complete the proof, you have to show that the condition under which new students get infected means that the perimeter either stays the same or decreases.

As to your last question: Ha! If only mathematicians had a formula for finding invariants! No, I think this only comes with practice.

Related Question