There is a grid of 20 squares by 10 squares. How many different rectangles are possible?
(Note that square is a rectangle).

(In reply to The real deal: 11,550? Mine was a little smaller than that... by Benjamin J. Ladd)

The very first comment (by Brian Smith) below nails this one. It is based on the principle, easily verified, that the number of ways to choose i consecutive numbers from 1,2,...,N is N-i+1. Summing these from i=1 to N gives
N(N+1)/2, since they are just 1,2,...,N in reverse order. If a grid has width n and height m, you can choose rectangluar blocks by choosing consecutive blocks horizontally and then stacking these vertically (or vice versa, it doesn't matter). Clearly then, a rectangle made up of blocks in this way can be formed in
n(n+1)/2 * m(m+1)/2 = nm(n+1)(m+1)/4 ways. For n=3 and m=2, you get 6*12/4 = 18, which you can easily verify by manual enumeration. For n=10 and m=20 the answer is 11550 just as Brian Smith says.

Edited on January 21, 2004, 8:59 pm
Edited on January 22, 2004, 1:05 pm

Posted by Richard on 2004-01-21 20:56:15