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:
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