All the red squares in the above picture would count as valid squares, so we are asking how many squares of any dimension from 1x1 to 8x8 there are on a chess board.

The key is to think how many positions there are that each size of square can be located...

A 2x2 square, for example, can be located in 7 loactions horizontally and 7 locations vertically. ie in 49 different positions. Consider the table below...

size horizontal positions vertical positions positons

1x1 8 8 64

2x2 7 7 49

3x3 6 6 36

4x4 5 5 25

5x5 4 4 16

6x6 3 3 9

7x7 2 2 4

8x8 1 1 1

total 204

There is a formula for the sum of squares of the integers

1^2 + 2^2 + 3^2 + ... + n^2

n(n+1)(2n+1)

Sum = ------------

6

In our case, with n = 8, this formula gives 8 x 9 x 17/6 = 204.

In total there are 204 positions. this is the sum of the number of possible positions for all the different sized squares.

Can you extend your technique to calculate the number of rectangles on a chessboard?

Below are some examples of possible rectangles...

All of the above examples would be vailid rectanges...

The key to this problem is to think of each rectangle individually and consider the number of positions it can be located. For example a 3x7 rectangle can be located in 6 positions horizontally and 2 vertically. From this we can build a matrix of all the possible rectangles and sum.

dimesions 1 2 3 4 5 6 7 8

positions 8 7 6 5 4 3 2 1

1 8 64 56 48 40 32 24 16 8

2 7 56 49 42 35 28 21 14 7

3 6 48 42 36 30 24 18 12 6

4 5 40 35 30 25 20 15 10 5

5 4 32 28 24 20 16 12 8 4

6 3 24 21 18 15 12 9 6 3

7 2 16 14 12 10 8 6 4 2

8 1 8 7 6 5 4 3 2 1

1296

In total then there are 1296 possible rectangles.

More Explaination

There are 64 one-by-one squares,

49 two-by-two squares, ...

(8-n)^2 n-by-n squares, ...

1 eight-by-eight square;

2 x (7x8) one-by-two rectangles,

2 x (6x8) one-by-three rectangles, ...

2 x (1x8) one-by-eight rectangles;

2 x (6x7) two-by-three rectangles, ...

2 x (1x7) two-by-eight rectangles; ...;

2 x (1x2) seven-by-eight rectangles.

This can all be simplified to find the sum total as the sum of the

cubes of integers 1 to 8, which is 8^2 x 9^2 / 4 or 36^2 = 1296.

Count the rectangles by rows.

In row 1 there are n 1 by 1s , n-1 1 by 2s, ... two 1 by n-1s and

one 1 by n. Row Total =

n + (n-1) + (n-2) + ... + 3 + 2 + 1 = n(n+1)/2 rectangles.

But of course there are n rows, giving n (row sum).

Now count all rectangles of height 2. Start in the bottom row. There are

n 2 by 1s and n-1 2 by 2s and ... and one 2 by n. Row Total =

n + (n-1) + (n-2) + ... + 3 + 2 + 1 = n (n+1)/2

The row total is the same, as it will be for all the rectangles of height

3, 4, ... n because they all share the same bases at the bottom of the

board. However, there are only n-1 rows of height 2 and n-2 rows of

height 3 etc. Thus,

number 1 by any totals: n [n(n+1)/2]

number 2 by any totals: (n-1) [n(n+1)/2]

number 3 by any totals: (n-2) [n(n+1)/2]

...

number n by any totals: 1 [n(n+1)/2]

So the total number of rectangles is [n(n+1)/2](n + n-1) + ... + 3+ 2+1)

or Total = [n(n+1)/2]^2

which,is the sum of the cubes from 1 to n.

Source :

**puzzles**.

**nigelcoldwell**.

**co**.

**uk**/twentyseven.htm

## 2 comments:

this is the best answer which i found

mathematically fit and it is a logical answer.

Post a Comment