Matchstick removal

So I was browsing around, and found some elementary-to-middle-school-targeted math problems (PDF), with a possible gem sequestered within.

29. Given a 4×4 square grid made up of matchsticks (i.e. 40 matchsticks), what is the minimum number of matchsticks you can remove such that there are no squares left?

Hmm. Let's see (I says to myself, says I).

If only squares of size 1 are considered, there are sixteen squares to be destroyed; each matchstick is used by at most two such squares, so 16/2 = 8 is a lower bound. And indeed there is a very simple eight-matchstick set which eliminates all of the size-1 squares (see image). And this is probably about right for average eighth-graders under pressure, give or take a grade level.

But what if squares of sizes 2, 3, and 4 are also considered?

It is relatively easily shown, based on the preceding, that 9 is a lower bound. Any outer-edge matchstick will remove only one size-1 square, so will not be contained in a minimal size-1-square-destroying set; but at least one outer-edge matchstick must be removed to break the size-4 square. Similarly, it's easy to show that 10 is an upper bond; there are several solutions, one of the more regular of which is pictured to the right.

So that reduces it to 9 or 10. Which is it? At first I thought it was 10, due to a flawed proof-by-counting similar to the proof for size-1. I later "corrected" it, producing a proof-by-cases over the possible domino-tilings of the 4-square that there was no 9-matchstick set, and found a flaw in that while typing it up.

In attempting to correct that second proof, I found this.


This isn't a very easy solution to find, being quite asymmetric (as, I think, all such solutions must be), tucked into a back corner of the large (40C9 > 2⁷²) solution space, and elusive of elegant derivation. Surely the eighth-grade problem was the first interpretation? But I checked the solutions anyway.

ANS: 9
SOL: First, considering a 1 × 1 square, only one matchstick need be removed to ‘break’ all the squares. Then go to a 2 × 2 square, by inspection one can easily see that three matchsticks must be removed. Now for a 3 × 3 square., [sic] we find that at least six matchsticks must be removed. At this point we could guess that the next number in the sequence is nine.

Uh-huh. Two entirely separate objections leap to mind:

a) The sequence S_n = n(n+1)/2 : 1, 3, 6, 10, ... (the triangular numbers) is a much more natural sequence to extrapolate from the values 1, 3, 6.
b) Guessing based on a few values of an initial sequence is worth absolutely nothing anyway.

How much would you like to bet that their original solution was "10" by the logic involved in a), hastily changed to "9" when a particularly lucky or clever student found a nine-stick solution like the one above?