3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.