Saturday, May 22, 2010

Remove the squares

There are forty matches in a grid pattern as shown above.  Try to remove matches so that no squares remain.  That means no 1x1 squares, no 2x2 squares, no 3x3 squares, and 4x4 squares.

Here's one solution: remove all vertical matches.  No squares are left.  I needed to remove twenty matches.  Can you do better?

I labeled each match with a number so that you can describe your solution easily.

See the solution


Secret Squïrrel said...

I think I have found several minimal solutions, all made from the same "tiles".

Eduard said...

Finding solutions with 10 dropped matches seems easy. Should we prove that 10 is best?

SC said...

Actually, I think I can prove the minimal solution is 9 (if I'm not missing a square... :P). How should I send you my answer?

miller said...

You can just list the numbers of the removed matches. Or, if you want it private, you can e-mail me at skepticsplay at gmail dot com.

SC said...

I don't want to spoil anyone's fun, so I'll just send an e-mail.

Eduard said...

Okay. I have also found a 9 solution. To not spoil directly I give it in binary form:
I'm interested in the proof.

Secret Squïrrel said...

I can confirm that all my sol'ns removed 9 matches. I believe that is the minimum.

The structure consists of 16 small squares, each of which must lose a match to cease being a square. The most efficient way to do this is to consider the structure as consisting of 8 pairs of squares and then remove the central match from each.

There are many ways of "tiling" the structure with these double squares, but the outer 4x4 square will always remain intact.

Therefore, you have to remove at least one more match (altho' it could be more) to fulfil the puzzle's requirement.

Since I have found several different 9-match sol'ns, that is the minimum.

I should add, that if you use the above tiling to solve the puzzle, the best you can do is 10 matches.

SC said...

Yes, that's basically the way I thought too to prove 9 is minimal. Now I was trying to find all the minimal solutions (excluding simmetries and rotations).