Here is a partial solution to problem (c). Let S(m,n) be the sum of areas of all possible rectangles as mentioned in the original problem, with the adjustment that there are m X n squares. Claim: (1) S(1,n) = n(n+1)(n+2)/6; (2) S(m,1) = m(m+1)(m+2)/6; and (3) S(m,n) = S(m-1,n) + S(1,n)*m(m+1)/2. Proof: ************************************************************ (1) S(1,1) = 1 is obvious. Let us denote S(1,0) by 0. S(1,k) = S(1, k-1) + (1+2+3+…+k). ——(*) S(1,k) = S(1, k-1) + k(k+1)/2 S(1,k) – S(1,k-1) = k(k+1)/2 ——(**) Summing up for k = 1, 2, …,n at (**), we have S(1,n) – S(1,0) = 1/2 [ n(n+1)(2n+1)/6 + n(n+1)/2], and hence

S(1,n) = n(n+1)(n+2)/6 { Simplification only.}

Reasoning behind (*): You may imagine that there is a single row of n + 1 squares, with the first n squares coloured black and the last square coloured red. Then the squares connecting the last square will be of area 1X1, 1X2, …., 1Xn.

{Better draw a diagram if you can’t grasp it.}

************************************************************ (2) Similar argument to the proof of (1). ************************************************************ (3) Consider the case of the grid with 1Xn squares first. In order to asist the calculation, let us denote a1 as the number of squares with area of 1 square unit, and a2 as the number of squares with area of 2 square units, … and so forth. Come back to the case of (m+1)Xn squares.

S(m,n) = S(m-1,n) + [(1*a1+2*a1+……+m*a1) +(1*a2+2*a2+…….+m*a2) +……+ (1*an+2*an+……+m*an)]

Thus, S(m,n) = S(m-1,n) + (a1+a2+……+an)(1+2+…..+m)

S(m,n) = S(m-1,n) + S(1,n)*m(m+1)/2.

Q.E.D.

Remark

1. The expression n(n+1)(n+2)/6 is equal to C(n+2,3) and the expression m(m+1)/2 is equal to C(m+1,2). So, is it possible to solve the problem by another counting method? 2. The recurrsion formula in (3) will lead to a close form for S(m,n). See if you can obtain the formula by yourself.

3. I have tried to calculate S(5,5) by the recurrsion formulae and I got the number 1225. {Hope I didn’t make any calculation mistake.}

_________________Beauty is the first test: there is no permanent place in the world for ugly mathematics.

G.H.HARDY

Last edited by Michael on Tue Oct 23, 2007 7:45 pm; edited 1 time in total