Let S be an n x n array of lattice points. Let T be the set of all subsets of S of size 4 which form squares. Let A, B and C be the number of pairs {P, Q} of points of S which belong to respectively no, just two and just three elements of T. Show that A = B + 2C. [Note that there are plenty of squares tilted at an angle to the lattice and that the pair can be adjacent corners or opposite corners of the square.]
Solution
(by Andrei Jorza)
Let D be the number of pairs in just one element of T. Note that a pair cannot be in more than three elements of T. But three can be achieved, for example:
x o x x x x o xThere are n2 points, so n2(n2 - 1)/2 = (n - 1)n2(n + 1)/2 pairs of points. This must equal A + B + C + D. Each square has 6 pairs of vertices, so D + 2B + 3C must equal 6 times the total number of squares. Now notice that (A + B + C + D) - (D + 2B + 3C) = A - B - 2C. So we have to show that the total number of squares is (n - 1)n2(n + 1)/12.
Introduce a coordinate system labeling the points (x, y) with x and y running from 1 to n. Consider a square with two adjacent vertices (a, 1) and (1, b). The other vertices are (a+b, a) and (b, a+b), so 2 ≤ a+b ≤ n. Obviously, any square can be translated to such a square and such a square has (n+2 - (a+b) )2 translates. Hence the total number of squares is ∑a=1n-1 ∑b=2n+1-a (n+2 - (a+b) )2. Put k = a+b. Then there are k-2 points in the range of summation with a+b = k. So we may change to summing over k and get: ∑k=3n+1 (n+2-k)2(k-2). Putting h = k-2, this becomes simply: ∑h=1n-1 (n-h)2h = n2 ∑ h - 2n ∑ h2 + ∑ h3 = n2 (n-1)n/2 - 2n(n-1)n(2n-1)/6 + (n-1)2n2/4 = (n-1)2n2(n+1)/12 as required.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002