Log In

prof. montanaris quals question

Posted on: January 20th, 2013 by
1

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


One Response to prof. montanaris quals question

  1. Pratik Poddar had this to say about that:

    Minimum value of k is N.

    Perimeter of infected area can't increase. It stays constant or decreases. Initially maximum perimeter is 4*k if k blocks are infected. If all blocks get infected perimeter becomes 4*n which is larger then 4*k (k <n) . So never would all square become infected.


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}