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

Its quite easy to see this one is you consider one direction at a time. Take a general rectangle of a x b squares and consider first the "a" direction.

There is first of all the largest possible side (a)

Then there are 2 possible ways of placing the length (a-1), 3 ways of placing (a-2) etc all the way down to the single square where there are "a" ways. Adding up there is the sum:
1+2+3+4+5+6+......+a
The sum of an arithmetic series is the average of the first and last term multiplied by the number of terms i.e. (1+a)*a/2

Similarly in the b direction there are (1+b)*b/2 possibilities. So overall in both directions there are (1+a)*a*(1+b)*b/4.

The values here give 11,550.

Interestingly this can be taken to three dimensions - (1+a)*a*(1+b)*b/6 etc

Posted by Jils on 2004-01-22 12:05:49