Killing squares

[bonanova]

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

1. prove your answer is smallest possible.
2. destroy every rectangle (including the squares) with fewest removals.
3. extend the size of the square to 5x5, 6x6, 7x7 and 8x8.
4. derive an expression for the fewest removals.

[k-man]

One solution to this puzzle by removing 9 toothpicks is shown here

To prove that it cannot be done by removing less than 9 toothpicks is easy. We must remove one toothpick from the outside border to break the outside square. Removing any one toothpick from the outside border leaves 15 unit squares intact. Every toothpick on the inside can impact at most 2 unit squares. To break 15 unit squares we need to remove at least 8 more toothpicks.