Chessboard, Tiling, Maths A square-shaped garden is divided into an n x n square grid by footpaths (like a chessboard). 
The owner wishes to have all the sections covered by grass; however, the grass grows in a peculiar way. If at least two of the neighbouring squares (i.e. squares that share an edge) of a given square become fully covered with grass, then so will the given square. 
What is the minimum number of squares that need to be planted initially so that the grass will eventually extend to the whole garden?
 A: The solution in the book (see my comment on the original question) is terrific: just note that the perimeter of the grassy region never increases. 
A: One can easily prove by induction that $n$ seeds arranged in the diagonal span the whole square.
The only remaining thing to prove is that $n-1$ seeds cannot span $n^2$ squares.
One can see using the definition of neighbouring squares that any number of seeds arranged in an $r\times c$ rectangle cannot span any square outside of that rectangle.
Suppose we place $n-1$ seeds in the $n\times n$ grid.
Let $r_1$ be the minimum row index in which one the $n-1$ seeds is placed, and $r_2$ the maximum row index in which one of the $n-1$ seeds is placed.
If $r_2-r_1<n-1$ then obviously the number of squares spanned by the seeds is $\leq (r_2-r_1)n<n^2$.
If $r_1=0$ and $r_2=n-1$ then by the pigeon hole principle there is at least a row with no seeds. Put $r_i$ for such a row. The only squares that can be spanned by the seeds are those with one seed in their column in the rows $r_{i-1}$ and $r_{i+1}$. There are at most $\lfloor\frac{n-1}{2}\rfloor$ squares such as these in which case the number of squares spanned is $3\lfloor \frac{n-1}{2}\rfloor<n^2$. So in all cases, there will be at least a square where no grass grows, so in any case $n-1$ seeds cannot span $n^2$ squares.
A: Take $2*2$ case, and plant grass in diagonal squares initially this will cover complete 4 squares. Now add 5 squares along adjacent edges of given square to make it a $3*3$ square. No squares of the newly added squares grow grass on its own. So you need to plant one square, any square of the newly added squares with grass and you are done. This logic can be extended to higher $n$. Thus minimum square need to be planted with grass initially is $n$.
