You are given an N x N board. Each cell can have at most 4 neighbors (left, right, up, down). You are allowed to "infect" k cells on the board. At each time step:
1. An "infected" cell remains "infected".
2. A "clean" cell becomes "infected" if atleast two of its neighbors are "infected".
What is the minimum value of k and the initial infection pattern, so that eventually, the entire board becomes infected ?
---- prof. Montanari's quals question