Push Past The Putnam
(Stanford Putnam Training 2007)
There is a board. Out of these 100, 9 cells are infected.
A cell becomes infected if it's adjacent to 2 already infected cells.
Think of the situation when the maximum number of cells are infected. How many cells remain uninfected then?
Challenge
Generalize for board with n-1 initially infected cells.
The answer is 19.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
*Warning *
This is not a complete solution, just a hint. Also, the idea of the solution is entirely mine. Any corrections are welcome.
Note that if you place the initially infected 9 cells along the diagonal of the 1 0 × 1 0 grid, you will end up with 81 infected cells.
Note that this is the maximum possible number of infected cells you can get in 1 0 × 1 0 grid with 9 initially infected cells. This should not be too hard to believe since you can check the result for smaller grids. Applying Induction will generalize for any n × n grid.