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

Okay, here's a solution for *ALL* the numbers of squares and rectangles in a 20x10 grid (just in case you ever wondered...)

If you apply brute force to the grid (here assumed to be a width of 20 squares and a height of 10 squares) to derive a general formula for the sum of all the rectangles, the final solution is 55 * 20! or 133,809,610,449,715,200,000.

If we start by taking the # of 1x1 squares we get:
1x1 = 20 * 10

Then add this to the # of 1x2 squares:
1x2 = 20 * 9

And 1x3...
1x3 = 20 * 8

.
.
.

And so on and so forth to...
1x10 = 20 * 1

And then start over with 2x1:
2x1 = 19 * 10

.
.
.

2x10 = 19 * 1

Continuing to apply this method and adding up all of these values, we arrive at the staggering formula:

10 * 20 + 9 * 20 + 8 * 20 + 7 * 20 + 6 * 20 + 5 * 20 + 4 * 20 + 3 * 20 + 2 * 20 + 1 * 20 + 10 * 19 + 9 * 19 + 8 * 19 + 7 * 19 + 6 * 19 + 5 * 19 + 4 * 19 + 3 * 19 + 2 * 19 + 1 * 19 + 10 * 18 + 9 * 18 + 8 * 18 + 7 * 18 + 6 * 18 + 5 * 18 + 4 * 18 + 3 * 18 + 2 * 18 + 1 * 18 + 10 * 17 + 9 * 17 + 8 * 17 + 7 * 17 + 6 * 17 + 5 * 17 + 4 * 17 + 3 * 17 + 2 * 17 + 1 * 17 + 10 * 16 + 9 * 16 + 8 * 16 + 7 * 16 + 6 * 16 + 5 * 16 + 4 * 16 + 3 * 16 + 2 * 16 + 1 * 16 + 10 * 15 + 9 * 15 + 8 * 15 + 7 * 15 + 6 * 15 + 5 * 15 + 4 * 15 + 3 * 15 + 2 * 15 + 1 * 15 + 10 * 14 + 9 * 14 + 8 * 14 + 7 * 14 + 6 * 14 + 5 * 14 + 4 * 14 + 3 * 14 + 2 * 14 + 1 * 14 + 10 * 13 + 9 * 13 + 8 * 13 + 7 * 13 + 6 * 13 + 5 * 13 + 4 * 13 + 3 * 13 + 2 * 13 + 1 * 13 + 10 * 12 + 9 * 12 + 8 * 12 + 7 * 12 + 6 * 12 + 5 * 12 + 4 * 12 + 3 * 12 + 2 * 12 + 1 * 12 + 10 * 11 + 9 * 11 + 8 * 11 + 7 * 11 + 6 * 11 + 5 * 11 + 4 * 11 + 3 * 11 + 2 * 11 + 1 * 11 + 10 * 10 + 9 * 20 + 8 * 20 + 7 * 20 + 6 * 20 + 5 * 20 + 4 * 20 + 3 * 20 + 2 * 20 + 1 * 20 + 10 * 9 + 9 * 9 + 8 * 9 + 7 * 9 + 6 * 9 + 5 * 9 + 4 * 9 + 3 * 9 + 2 * 9 + 1 * 9 + 10 * 8 + 9 * 8 + 8 * 8 + 7 * 8 + 6 * 8 + 5 * 8 + 4 * 8 + 3 * 8 + 2 * 8 + 1 * 8 + 10 * 7 + 9 * 7 + 8 * 7 + 7 * 7 + 6 * 7 + 5 * 7 + 4 * 7 + 3 * 7 + 2 * 7 + 1 * 7 + 10 * 6 + 9 * 6 + 8 * 6 + 7 * 6 + 6 * 6 + 5 * 6 + 4 * 6 + 3 * 6 + 2 * 6 + 1 * 6 + 10 * 5 + 9 * 5 + 8 * 5 + 7 * 5 + 6 * 5 + 5 * 5 + 4 * 5 + 3 * 5 + 2 * 5 + 1 * 5 + 10 * 4 + 9 * 4 + 8 * 4 + 7 * 4 + 6 * 4 + 5 * 4 + 4 * 4 + 3 * 4 + 2 * 4 + 1 * 4 + 10 * 3 + 9 * 3 + 8 * 3 + 7 * 3 + 6 * 3 + 5 * 3 + 4 * 3 + 3 * 3 + 2 * 3 + 1 * 3 + 10 * 2 + 9 * 2 + 8 * 2 + 7 * 2 + 6 * 2 + 5 * 2 + 4 * 2 + 3 * 2 + 2 * 2 + 1 * 2 + 10 * 1 + 9 * 1 + 8 * 1 + 7 * 1 + 6 * 1 + 5 * 1 + 4 * 1 + 3 * 1 + 2 * 1 + 1 * 1

Which looks bad, but can really be grouped together quite easily to make up the following formula:

20!(10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) or 55 * 20!

55 * 20! = 133,809,610,449,715,200,000 rectangles

(Note: It's official, "I'm an idiot and didn't read the question properly...")
Edited on January 21, 2004, 5:41 pm

Posted by Benjamin J. Ladd on 2004-01-21 17:30:46