### Problems

- Count number of squares in chessboard?
- Count number of rectangles in MXN rectangle
- Squares in rectangle

### Solution

**Number of squares in chessboard having 8X8 grid.**

There are four 7x7 squares, one aligned with each corner. There are nine 6x6 squares, etc. So the sum of the first 8 squares 1+4+9+16+25+36+47+64=204 is the answer. In general, the sum of the first n squares is given by the formula

(2n^{3}+3n^{2}+n)/6

Now lets move to next.

**Number of rectangles in MXN rectangle**

The answer to this question is the same as the answer to another question:

How many ways can I draw two horizontal lines and two vertical lines through an array of (m+1) by (n+1) dots?The two horizontal lines can be drawn C(m+1,2) ways, and the two vertical lines can be drawn C(n+1,2) ways, so the total number of rectangles within an m x n rectangle is

(Think of the dots formed at the corners of the little squares within the rectangle)

C(m+1,2) C(n+1,2)

**Squares within rectangle**

How many squares can be found within an m x n rectangle? (m > n)

To answer this question, start with an n x n square, and then you know the number of squares in this portion of it from the first section:

(2nNow, consider adding one row of squares at the bottom, making it an n+1 by n rectangle. Think of the dots formed at the corners of the little squares you added to make the bottom row. Now, for every pair of newly-added dots, you can find one new square. So the number of new squares you can find in the now larger rectangle is the number of pairs of n+1 dots, which is C(n+1,2). If you need convincing, there's another way to think of it. By adding a new row of n little squares, you can now find within the large rectangle one new n x n square, two new n-1 x n-1 squares, three new n-2 x n-2 squares, etc. So the number of new squares added this way is the sum of the first n counting numbers, which is C(n+1,2).^{3}+3n^{2}+n)/6

Now, add another row of squares at the bottom, making it an n+2 by n rectangle. This adds the same number of new squares, C(n+1,2).

Now I'm sure you see the picture. The number of squares that can be found within an m x n rectangle (m > n) is given by this formula:

(2n^{3}+3n^{2}+n)/6 + (m-n) C(n+1,2)

**References**

http://2000clicks.com/mathhelp/CountingRectangles.aspx

## 0 comments:

## Post a Comment