#1
|
|||
|
|||
another interesting but harder problem
Suppose you have a nxn grid of "cells," represented by squares, as on an nxn checkerboard. Some of them are "infected," the rest are not.
If an uninfected cell shares at least two edges with an infected cell, then the uninfected cell becomes infected. This process continues until the set of infected cells stabilizes. The problem is to prove the following statement, using less than two sentences. (In other words, inductive arguments and computer simulations are unacceptable; the point is to find an elegant solution.) "If the entire grid is infected at the end of the process, then at least n squares had to be infected to begin with." |
|
|