A garden is divided into nxn squares by footpaths. You want all the squares to be covered by grass. If at least two neighbors of a square are covered, then the grass will extend to it too. Otherwise, not. What is the minimum number of squares to be planted initially, so that the grass extends to the whole garden? Prove rigorously. No, really, make sure that your math professor would approve.
NOTE: Many have answered, but none have given a proof showing it cannot be done in fewer. Proving that you really have the minimum is the interesting part of this problem.