The disease problem

Question

Students are sitting in a n * n grid. There's a disease spreading among them in a particular fashion.

At start, there a 'k' students infected(At random). After every time step(equal intervals), the number of students infected, increase. The manner of increment after each time step is -

1. The students that were previously infected, are continued to be infected.
2. The students(non- infected) that were adjacent to at least 2 of the infected students, get infected.

*Adjacent means that the infected students should be in top, right, left or bottom cell, of a particular student into consideration.

Theorem - If fewer than n students in class are initially infected, the whole class will never be completely infected. i.e k < n, then all the students would never be infected.

If possible, prove this by induction.

Answer 1

Hint: prove the perimeter of the shape formed by the infected squares never increases.