## Thursday, March 10, 2011

### How many squares are there on a chessboard?? (the answer is not 64) Can you extend your technique to calculate the number of rectangles on a chessbrd

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