Frank Morley poses this classic counting puzzle [Arc80], [MT -> Morley], [YaY64]. Show that on a chess-board the number of squares visible is 204, and the number of rectangles (including squares) visible is 1296; and that, on a similar board with n squares in each side, the number of squares is the sum of the first n square numbers, and the number of rectangles (including squares) is the sum of the first n cube numbers. There is a bunch of problems of this type. Let's take a closer look. Problem A: How many squares do you count? n=1 *---* | | *---* n=2 *---*---* | | | *---*---* | | | *---*---* n=3 *---*---*---* | | | | *---*---*---* | | | | *---*---*---* | | | | *---*---*---* Solution A: Let more generally A(n,m) be the figure with height n and width m. Let s(n) be the number of squares in A(n,n). Let's define further s(n,m) = # squares of A(n,m). We will show s(n) = n(n + 1)(2n + 1)/6 = n(n + 1)(n + 1/2)/3 = C(n+2,3) + C(n+1,3) = 2 C(n+1,3) + C(n+1,2) More general we have s(m,n) = 2 C(n+1,3) + (m-m+1)*C(n+1,2) where m>=n. Solution A: direct proof The number of squares of different size is easily seen. A(n,n) has 1*1 squares of size n*n 2*2 squares of size (n-1)*(n-1) ... n*n squares of size 1*1. [GKP88, Section 2.5] show seven ways to find the sum of squares. Solution A: inclusion exclusion principle (order 1) We have the recurences: (1) s(n,m) = s(n,m-1) + C(n+1,2) for m>=n. The scheme for the recurence (1) looks like this *---*---*---* * *---*---* X * * * | | | | | * * * * * * * * X * * * | | = | | + | * * * * * * * * X * * * | | | | | *---*---*---* * *---*---* X * * * If a square is on the left boarder then each selection of two points from this boarder determines a valid square. There are n+1 choose 2 ways in doing this. Otherwise the square is inside a smaller rectangle. Now use two cases of (1). (1.0) s(n,n) = s(n,n-1) + C(n+1,2) (1.1) s(n,n+1) = s(n,n) + C(n+1,2) That is s(n,n+1) = s(n,n-1) + 2 C(n+1,2). As s(1,0) = 0 we get s(n,n-1) = 2 ( C(2,2) + C(3,2) + ... + C(n,2) ) Rewriting Pascal's identity C(s+1,3) = C(s,2) + C(s,3) as C(s,2) = C(s+1,3) - C(s,3) gives s(n,n-1) = 2 ( C(3,3)-C(2,3) + C(4,3)-C(3,3) + ... + C(n+1,3)-C(n,3) ) = 2 C(n+1,3). Applying (1) several times to s(n,m) with m>=n we get s(m,n) = 2 C(n+1,3) + (m-m+1)*C(n+1,2). Solution A: inclusion exclusion principle (order 2) We have the recurences: (1) s(n,n) = 2s(n,n-1) - s(n-1,n-1) + n (2) s(n,n+1) = 2s(n,n) - s(n,n-1) Like the simple recursion in the previous proof we get *---*---*---* * *---*---* *---*---*---* * *---*---* * * * * | | | | | | | | * * * * * * * * * * * * * * * * * * * * | | = | | + | | - | | + * * * * * * * * *---*---*---* * *---*---* * * * * | | | | *---*---*---* * *---*---* * * * * * * * * X * * * *---*---*---* * *---*---* *---*---* * * *---* * | | | | | | | | * * * * = * * * * + * * * * - * * * * | | | | | | | | *---*---*---* * *---*---* *---*---* * * *---* * (1) and (2) looks similar and can be combined into a single recurence (3) a(n) = 2a(n-1) - a(n-2) + a2(n) with a(2n) = s(n,n) a(2n+1) = s(n,n+1) and a2(n) = n/2 for n even, a2(n) = 0 for n odd. The sequence a2 can be found in the difference scheme of a again. Difference Scheme: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n ------------------------------------------------------------------- 0 0 1 2 5 8 14 20 30 40 55 70 91 112 140 168 204 a(n) 0 1 1 3 3 6 6 10 10 15 15 21 21 28 28 36 a1(n) 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 a2(n) Problem A1 [YaY64]: How many rectangles do you count? (figures of problem A.) Solution A1: The number of rectangles are easily count. To determine a rectangle we need select two rows and two columns. r(m,n) = C(m+1,2) * C(n+1,2). Now for n=m we get r(n,n) = C(n+1,2)^2 = (n(n+1)/2)^2. By a well known formula 1^3 + 2^3 + 3^3 + ... + n^3 = (n(n+1)/2)^2. * | 111 | 110 011 | 100 010 001 | ---+-----+---------+-------------+ 1 | 111 | 110 011 | 100 010 001 | 1 | 111 | 110 011 | 100 010 001 | 1 | 111 | 110 011 | 100 010 001 | ---+-----+---------+-------------+ 1 | 111 | 110 011 | 100 010 001 | 1 | 111 | 110 011 | 100 010 001 | 0 | 000 | 000 000 | 000 000 000 | | | | | 0 | 000 | 000 000 | 000 000 000 | 1 | 111 | 110 011 | 100 010 001 | 1 | 111 | 110 011 | 100 010 001 | ---+-----+---------+-------------+ 1 | 111 | 110 011 | 100 010 001 | 0 | 000 | 000 000 | 000 000 000 | 0 | 000 | 000 000 | 000 000 000 | | | | | 0 | 000 | 000 000 | 000 000 000 | 1 | 111 | 110 011 | 100 010 001 | 0 | 000 | 000 000 | 000 000 000 | | | | | 0 | 000 | 000 000 | 000 000 000 | 0 | 000 | 000 000 | 000 000 000 | 1 | 111 | 110 011 | 100 010 001 | ---+-----+---------+-------------+ Problem A2: How many squares do you count? (figures of problem A.) The vertices shall form a square. The sides need not be on the lattice. Solution A2: inclusion exclusion principle (order 1) We have the recurences: (1) s(n,m) = s(n,m-1) + C(n+2,3) for m>=n. s(m,n) = 2 C(n+2,4) + (m-m+1)*C(n+2,3). Problem B: How many triangles do you count? n=1 *-------* | \ / | | * | | / \ | *-------* n=2 *-------*-------* | \ / | \ / | | * | * | | / \ | / \ | *-------*-------* | \ / | \ / | | * | * | | / \ | / \ | *-------*-------* Solution B: Let more generally B(n,m) be the figure with height n and width m. Let t(n) be the number of triangles in B(n,n). There are two types of triangles. Let's define tb(n,m) = # triangles of B(n,m) with the hypothenuse not on the diagonals, td(n,m) = # triangles of B(n,m) with the hypothenuse on the diagonals. case: triangles with horizontal or vertical hypothenuse There are several ways to determine tb(n,n). The first method is with the inclusion-exclusion principle. We have the recurences: (1) tb(n,n) = 2tb(n,n-1) - tb(n-1,n-1) + 4 n (2) tb(n,n+1) = 2tb(n,n) - tb(n,n-1) + 2 floor((n+1)/2) These looks similar and can be combined into a single recurence (3) a(n) = 2a(n-1) - a(n-2) + a2(n) with a(2n) = tb(n,n) a(2n+1) = tb(n,n+1) and a2(n) = 2n for n even, a2(n) = 2 floor((n+1)/4) for n odd. The sequence a2 can be found in the difference scheme of a again. Difference Scheme: a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 n ------------------------------------------------------------------- 0 0 4 10 24 40 68 100 148 200 272 350 452 560 696 840 1016 a(n) 0 4 6 14 16 28 32 48 52 72 78 102 108 136 144 176 4 2 8 2 12 4 16 4 20 6 24 6 28 8 32 a2(n) Difference Scheme: tb 0 1 2 3 4 5 6 7 8 9 n --------------------------------------- 0 0 1 6 17 37 68 113 174 254 tb(n,n)/4 0 1 5 11 20 31 45 61 80 1 4 6 9 11 14 16 19 3 2 3 2 3 2 3 case: triangles with diagonal hypothenuse td(n,n) = 4*s(n) with sequence s of problem A. Problem C: How many rectangles do you count? *---*---*---* | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | | | *---*---*---*---*---* | | | | *---*---*---* Solution C: We use the formular found in problem A1. The inclusion exclusion principle shows rectangles = r(3,4) + r(2,5) - r(2,3) = 6*10 + 3*15 - 3*6 = 87 Problem D: [Hem04] How many rectangles do you count? *---*---*---* | | | | *---*---*---*---*---* | | | | | *---*---*---*---* | | | | | *---*---*---*---* | | | | | *---*---*---*---* Solution D: Using the technique of problem C we get rectangles = r(3,4) + r(2,4) - r(2,3) + 3 References: Arc80: R C Archibald; A semicentennial history of the American Mathematical Society 1888-1938 (New York, 1980), 194-201. - Morley loved posing mathematical problems and over a period of 50 years, starting in his undergraduate days, he published over 60 problems in the Educational Times. ArM93: Y. Arzoumanian, W. O. J. Moser; enumerating 3-, 4-, 6-gons with vertices at lattice points, Crux Mathematicorum 19:9 (Nov 1993) 249-254 Part I - Part I counts triangles and others in the triangular lattice ArM93: Y. Arzoumanian, W. O. J. Moser; enumerating 3-, 4-, 6-gons with vertices at lattice points, Crux Mathematicorum 19:10 (Dec 1993) 279-284 Part II - Part II counts squares in the square lattice problem6: How many squares have vertices at lattice points of L(m,n), (m <= n), and sides along lattices lines? solution6: m(m + 1)(3n - m + 1)/6 = C(m+2,3) + C(m+1,3) + (n-m) C(m+1,2) = 2 C(m+1,3) + (n-m+1) C(m+1,2) problem7: How many squares have vertices at lattice points of L(m,n), (m <= n)? The sides need not be along lattices lines. solution7: m(m + 1)(m + 2)(2n - m + 1)/12 = C(m+3,4) + C(m+2,4) + (n-m) C(m+2,3) = 2 C(m+2,4) + (n-m+1) C(m+2,3) problem8: How many isosceles right triangles have vertices at lattice points of L(m,n), (m <= n), and legs along lattice lines? solution8: 2m(m + 1)(3n - m + 1)/3 problem9: How many isosceles right triangles have vertices at lattice points of L(m,m) and hypotenuse along a lattice line? Daw72: J. Dawes; Squares in a square lattice, Mathematical Gazette 56 (1972) 129 Dud26: Henry Ernest Dudeney; Modern Puzzles and how to solve them, London, 1926, - Problem 128: Lines and Squares, p49, 139 Determine m, n such that the number of squares of the n*m grid is 100. That is we are looking for positive m<=n with 100 = m(m + 1)(3n - m + 1)/6. Solution: As 300 = C(m+1,2)*(3n - m + 1) we are looking for triangular numbers dividing 300. These are 1, 3, 6, 10, 15. So we have to check 1<=m<=5. So valid (m,n) are (1,100), (4,11), (5,8). Gar73: Martin Gardner; Look-see, diagrams that offer visual proof of complex algebraic formulas, Scientific American 229:4 (October 1973) 114-118 Gar74: Martin Gardner; Beweis algebraischer Formeln durch Betrachtung graphischer Darstellungen, Didaktik der Mathematik, 2:4 (1974) 314-320 GKP88: Ronald L. Graham, Donald E. Knuth, Oren Pataschnik; Concrete Mathematics, Addison Wessley, Reading (1994) 2nd Ed. - Chapter 2 Sums - Section 2.5: shows 7 ways to find the sum of consecutive squares. - See index: sum of consecutive squares Gra01: Serhiy Grabarchuk; www.puzzles.com/PuzzlePlayground/CountingTriangles2/CountingTriangles2.htm 2001 Hem04: Heinrich Hemme; Gewinnspiel: R\"ubezahls R\"ubenfelder, rowohlt revue 77 (Fr\"uhjahr 2004), p70 Jeg73: Max Jeger; Einf\"uhrung in die Kombinatorik, Band 1, Klett Studienb\"ucher, Stuttgart, 1973, ISBN 3-12-983200-9 - Chap 3.2: Aufgaben 5, 6. \"Ubungen 5, 7. Kor72: Boris A. Kordemsky; The Moscow Puzzles, 1972 - Problem 349: A row of positive integers - 349.f the multiplication table Lan62: Harry Langman; Play Mathematics, Hafner Publishing Co, 1962 - Chapter 3 Geometry - Section 3.2: Lattice points Suppose we have an array of m*n lattice points (m >= n) and inquire how many sets of four of these points will form a square? solution (axis parallel): (n-1)n(3m-n-1)/6 solution: (n-1)n(n+1)(2m-n)/12 (note: Langman uses another definition of n and m than [ArM93].) Pea07: Pearson; 1907. Part II. No. 74: A triangle of triangles, p. 74. - Triangular array with four on a side, but with all the altitudes also drawn. Gets 653 triangles of various shapes. No. 75: Pharoah's seal, pp. 75 & 174. - Isoceles right triangles in a square pattern with some diagonals. Ste71: Robert G. Stein; Mathematics Magazine (May 1971) 161-162 - rectanges in the square YaY64: A. M. Yaglom and I. M. Yaglom; Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, ISBN 0-486-65536-9 (1st. publ.: San Francisco: Holden-Day, Inc., 1964) - problem 48: how many rectangles can be drawn on a n*n chessboard? solution48: ( n(n+1)/2 )^2 - problem 49: how many squares can be drawn on a n*n chessboard? solution49: n(n+1)(2n+1)/6 remark: by a well known formula 1^3 + 2^3 + 3^3 + ... + n^3 = (n(n+1)/2)^2 MT: The MacTutor History of Mathematics archive; entry: Frank Morley http://www-groups.dcs.st-and.ac.uk/%7Ehistory/Mathematicians/Morley.html -- http://www.mathematik.uni-bielefeld.de/~sillke/ mailto:Torsten.Sillke@uni-bielefeld.de