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 matchsticks|
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):
|1st Difference||2nd Difference|
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.
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
© J.A.N. Lee, 2001.