Enumerative Solutions - The Second Matchstick Problem

Problem: How many matches do you need to construct a matrix of n squares (as shown below):

Look through the sequence of building matrices:

Let us build a table indicating how many matches are need to build each set of squares:

Number of squares
Number of matchsticks
1
4
2
12
3
24
4
40
5
6
7

Fill in the missing values. Click outside the box once you have entered each value to check the correctness of your entry.

If you watch carefully you will be able to see that each time we add a new layer of boxes to make a n x n matrix , we add 4n new matchsticks. That is when there is one box on the table and we add matchsticks to make a 2 x 2 matrix, 8 matchsticks have to be added. Similarly to go from a 2 x 2 array to a 3 x 3 requires adding 12 matchsticks.

Thus we can conclude that if it takes p matchsticks to form a matrix of (m-1) squares, then the number of matchsticks in a matrix of m squares is p + 4m. Thus starting with a square (1 x 1) of 4 matchsticks, the number in the next larger size is 4 + 4 X 2 = 12, and the next level (3 x 3 square) requires 12 + 4 x 3 = 24 matchsticks. Thus an algorithm for computing the number of matchsticks in a square of size n x n is:

```
matchsticks = 0
for i = 1 to n
matchsticks = matchsticks + 4 x i
```

Alternatively we can compute the number of matchsticks needed for boxes of size greater than 4 by constructing a difference table, and noting that the second difference is a constant (4):

Number of
Squares
Number of
Matchsticks
1st Difference2nd Difference
1
4
8
2
12
4
12
3
24
4
16
4
40
4
5
6
7

Complete this table, so that you can compute the number of matchsticks needed to complete a 7 x 7 matrix.

Yet again we can find a different means to compute the number of matchsticks in (n x n) matrices. Note that in each row of a (n x n) matrix there are n matchsticks, and there are (n + 1) lines of matchsticks. Thus the total number of matchsticks in the rows of matchsticks is n (n + 1). There is exactly the same number of matchsticks in each column. So the total number of matchsticks in a (n x n) matrix is 2n (n + 1). Check the values that result from this equation against the tables above.

ALTERNATIVE SOLUTIONS to problems are important to us for several reasons.

1. They provide an opportunity to choose the best algorithm for computation, whether the choice is to be based on speed or space.
2. They provide a means of double checking the results of our computations by checking the results of one algorithm against those of another.

Our implementation of algorithms, unfortunately, are not always correct. However by using an alternative solution enables us to check the results and to know when the results are questionable. It is better to give the answer of "I don't know" than to give a wrong answer!

Last updated 2001/02/27