Thursday, June 17, 2010

Removing squares solution

See the original puzzle

Click for a solution

The solution proves that you can do it by removing nine matches.  We can prove that it is impossible to do any better.

Before we remove any matches, there are sixteen 1x1 squares.  For each one, we need to remove one of its four sides.  If we remove one of the inside matches, then we can remove two of the sixteen squares.  So we can get all of the 1x1 squares by removing eight matches.  However, we also need to remove one of the outside matches to get rid of the 4x4 square.  Therefore, we need at least nine matches.