Fig. 29 How many squares can you find?
This problem is much like the previous one (see How Many Triangles in a Triangle?), in that a relationship must be proven for the number of geometrical figures that can be constructed from the arrangement given, as a function of the order. In this problem, a range of different sized chessboards are given, with the conventional board being of order eight (8 sides).
Fig. 30 Unconventional Chessboards
The text investigates the properties of these first few, then asks how many squares could be found on the one with eight squares on each side. It then leaves as an exercise for the reader to find a general rule that could be applied. It can be verified easily for these first few that for a function N(O = n), where N is the number of squares and O is the order of the figure, that N(O = n) = (n/6)(n + 1)(2n + 1). I have found two different proofs for this relationship, but there may well be many more.
Firstly we take a look at the square of order n (I'll use n = 3 to illustrate), and assume that we have already counted those for that of order n - 1 which appears in the bottom left, so we are only looking at the top and right edges (and those parts that are overlapped by the larger sized squares). Now we can see that there will be one square of side length n (there is only one three by three square in that of order three.). Looking at the next largest square, with side length n - 1, we can fit along the edge three of these (since it shifts one space from the top left corner and then reaches the corner and must shift down a space for the next one), in the 3x3 square, three 2x2 squares can be fit along the edge like this.
Fig. 31 2x2 squares on the edge of 3x3 square
We can continue this through, forming a sum of a series of odd numbers up until we reach 1x1 squares of which there are 2n - 1, since there are n on the top row and n - 1 on the right, since the top right square was counted in the top. So now we have this series:
N(O = n) - N(O = n - 1) = 1 + 3 + ... + (2n - 1) -- (1)
It can be shown by induction that (1) is equal to the square of n. So for each value of n the function gives a square plus the function before, which was its square plus the function before it, and so on. Since N(O = 1) = 12, we can say that N(O = 2) = 22 + 12, and so on up through all values of n. Now we have reached the formula:
N(O = n) = n2 + (n - 1)2 + ... + 22 + 12 -- (2)
To reach the formula given at the beginning we can use an inductive approach as follows.
Assuming that N(O = n = k) = (k/6)(k + 1)(2k + 1),
N(O = n = k + 1) = (k/6)(k + 1)(2k + 1) + (k + 1)2
= [(k + 1)/6][k(2k + 1) + 6(k + 1)]
= [(k + 1)/6](2k2 + k + 6k + 6)
= [(k + 1)/6](2k2 + 7k + 6)
= [(k + 1)/6](2k2 + 4k + 3k + 6)
= [(k + 1)/6][2k(k + 2) 3(k + 2)]
= [(k + 1)/6](k + 2)(2k + 3)
= [(k + 1)/6][(k + 1) + 1][2(k + 1) + 1]
So if it is true for O = n = k it is also true for O = n = k + 1, and in turn O = n = (k + 1) + 1 = k + 2, and so on for all integer values of O = n > k.
But N(O = 1) = 1, and (1/6)(1 + 1)(2 x 1 + 1) = (2 x 3)/6 = 1. Therefore it is true for all O = n greater than or equal to 1.
The second method for this proof involves the derivation of (2). Once again we assume that all the squares in the square of order n - 1 that appears in the bottom left have been counted. Now, we notice that along the top row there will be 1 nxn square, 2(n - 1)x(n - 1) squares, and so on until we notice n 1x1 squares. On the right edge we now have one less of each square (since those that fit in the top right corner have been counted). So on the edge we have the triangular number of n (Tn) and the triangular number of n - 1 (Tn - 1).
By induction it can be shown that the triangular number for a given value x, is given by Tx = (x2 + x) / 2. So now we have:
N(O = n) - N(O = n -1) = (x2 + x) / 2 + [(x - 1)2 + (x - 1)] / 2
= (x2 + x + x2 - 2x + 1 + x - 1) / 2
= (2x2) / 2
= x2
This is equivalent to (2) and the proof is completed in the same way from there.
204
ReplyDeletec=0;
ReplyDeletefor n=1:8
nc= (8-n+1)^2;
c=c+nc;
end