Forty toothpicks form a 4x4 checkerboard as shown in the figure.
What is the smallest number of toothpicks that if removed will break
the perimeter of every square: the 16 unit squares, the 9 order-2 squares,
the 4 3x3 squares and of course the outside border?
If you like, extend the problem to
- prove your answer is smallest possible.
- destroy every rectangle (including the squares) with fewest removals.
- extend the size of the square to 5x5, 6x6, 7x7 and 8x8.
- derive an expression for the fewest removals.