Removing Matchsticks

Ashish Khare posted the following problem on Linkedin:


I have attempted to solve this problem by eliminating the most common matches first and working my way down.

First, I set up the grid:

And labeled how many times am edge was used to create a 1×1 block.

And then added on top of that how many times the edges were used for 2×2 blocks.

And 3x3s

And finally the big 4×4 square.

Then I removed the most commonly used edge; which was a tie upon many, so I chose at random.

And after removing the edge, I adjusted all the other numbers accordingly.

And chose a new most commonly used edge:

Removed it, and adjusted the numbers…

Repeat a few times…

Look at all these zeroes!  We’re getting close…

Gee… this is a bit tedious, let’s do the last three all at once.

That’s a total of 10 matchsticks removed.

There are no 1×1, 2×2, 3×3, or 4×4 squares remaining.

In general: for a nxn board, one will need to remove (1/2)(n)(n+1) matchsticks.