Consider a square grid made of matchsticks. Four matches are needed to
make a single square. To break the square, you can remove any single match.
Twelve matches are needed to make a 2x2 grid of
squares (6 horizontal and 6 vertical.) There are 5 squares in such a grid,
four 1x1 and one 2x2. To eliminate all squares, three matches must be removed
(an external match must be removed to break the 2x2 square, but this leaves
three 1x1 squares, and at least two more matches must be removed to leave
no full squares.)
__ __ __
|__|__|__|
|__|__|__|
|__|__|__|
What is the fewest number of matches which must be removed to break all
squares - of any size - in:
a 3x3 grid (originally 24 matches, as shown)?
a 4x4 grid (originally 40 matches)?
a 5x5 grid (originally 60 matches)?
Source:
Based on "Vanishing Trick" in Michael Holt's
Math Puzzles & Games, Volume 2, Page 44.