Recitation 5 4 Square Infection The following problem is fairly tough until you hear a certain one-word clue. Then the solution is easy! Suppose that we have an n x n grid, where certain squares are infected Here is an example where n=6 and infected squares are marked x × Now the infection begins to spread in discrete time steps. Two squares are considered djacent if they share an edge; thus, each square is adjacent to 2, 3 or 4 others. A square is infected in the next time step if either the square was previously infected, or the square is adjacent to at least two already-infected squares In the example the infection spreads as shown below. |×| Over the next few time-steps, the entire grid becomes infected Theorem. An n x n grid can become completely infected only if at least n squares are initially Prove this theorem using induction and some additional reasoning. If you are stuck, ask your recitation instructor for the one-word clue Solution. Define the perimeter of an infected region to be the number of edges with xactly one side. Let I denote the Proof. We use induction on the number of time steps k to prove that the perimeter of the the perimeter of the infected region is at most, ypothesis P(k)is this: after k time steps, infected region never increases. The inductive hyRecitation 5 5 4 Square Infection The following problem is fairly tough until you hear a certain one­word clue. Then the solution is easy! Suppose that we have an n × n grid, where certain squares are infected. Here is an example where n = 6 and infected squares are marked ×. × × × × × × × × Now the infection begins to spread in discrete time steps. Two squares are considered adjacent if they share an edge; thus, each square is adjacent to 2, 3 or 4 others. A square is infected in the next time step if either • the square was previously infected, or • the square is adjacent to at least two already­infected squares. In the example, the infection spreads as shown below. × × × × × × × × ⇒ × × × × × × × × × × × × × × × × ⇒ × × × × × × × × × × × × × × × × × × × × × × Over the next few time­steps, the entire grid becomes infected. Theorem. An n × n grid can become completely infected only if at least n squares are initially infected. Prove this theorem using induction and some additional reasoning. If you are stuck, ask your recitation instructor for the one­word clue! Solution. Define the perimeter of an infected region to be the number of edges with infection on exactly one side. Let I denote the perimeter of the initially­infected region. Proof. We use induction on the number of time steps k to prove that the perimeter of the infected region never increases. The inductive hypothesis P(k) is this: after k time steps, the perimeter of the infected region is at most I