## Leave No Squares

How many matchsticks do you need to remove so that no squares of any size remain?

**SOLUTION**

Nine matchsticks are enough, as seen from the solution below.

To see that eight matchsticks are not enough, first we consider the center 2 by 2 square. It must have at least one matchstick removed and we can assume without loss of generality that it is the top left one.

Then, we consider the top left and the bottom right 1 by 1 squares, as well as the top right and the bottom left 2 by 2 squares. Each of the former two must have at least one matchstick removed and each of the latter two must have at least three matchsticks removed.

Therefore, the total number of matchsticks that need to be removed is at least 1+1+1+3+3=9.