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 =6 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, 2 , 3 , or 4 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. But this is what i tried:
Proof by induction:
Let P(n) be the proposition: If fewer than students in class are initially infected, the whole class will never be completely infected.
- Base case: n = 0, P(0) is true by definition since no students are infected to spread the disease to begin with.
2)Inductive step:
P(n) => P(n-1)
Set of Total students: {n^2}
Total number of students in the above set will be n^2 in n*n grid.
set of infected students initally (at t = 0):
{S,....,Sn-1}
As time passes this set of infected students increaes, Assuming P(n) to be true the number of students in the set of infected students will never reach the number of students in the set of total students.Therefore the whole class will never be infected.Hence, Proved!
Is my Proof correct? if not why?Any help will greatly be appreciated
Here’s a hint from Arthur Engel’s Problem Solving Strategies. I’d look for invariance. Paint all infected squares, the perimeter length of these painted areas is non increasing (prove it). If all squares are infected the perimeter is $4n$ but if less than $n$ squares are infected the total perimeter length is less than $4n$.