4th Brazil 1982 Problem 3 S is a (k+1) x (k+1) array of lattice points. How many squares have their vertices in S?
k(k+1) 2 (k+2)/12 Solution The key is to consider how many squares have their vertices on the perimeter of given n+1 x n+1 array whose side are parallel to the sides of the array. The diagram shows that there are n such squares. There are (k+1-n) 2 such arrays. So the total number of squares is k·1 2 + (k-1)2 2 + ... + 1·k 2 = ∑ 1 k (k+1-i)i 2 = (k+1)k(k+1)(2k+1)/6 - k 2 (k+1) 2 /4 = k(k+1) 2 (k+2)/12. 4th Brazil 1982 © John Scholes jscholes@kalva.demon.co.uk 24 Oct 2003 Last corrected/updated 24 Oct 03