Just For Fun 8X8

[kuiperbelt]

Would I dare to be so mean as to ask how many squares and rectangles can be found on a standard chessboard LOL Of course not!!

[ClareTG0ld]

I must have seen this problem multiple times, and I keep forgetting the surprisingly simple solution.

Stat with a 2x2 chessboard. There are four small squares, four 1x2 rectangles, and one large square for a total of 9. It's useful to write this in the following way:

Total = 1*1 + 1*2 + 2*1 + 2*2 = (1+2)*(1+2)

We'll now extend to a 3x3 board. This time there are many more rectangle sizes available: specifically, you can have 1x2, 1x3, 2x3. As each dimension increases by one, you can fit one fewer per row, or one fewer per column. So the pattern is that you can fit:

3*3 + 3*2 + 2*3 + 3*1 + 1*3 + 2*2 + 2*1 + 1*2 + 1*1 = (3+2+1)*(3+2+1) = 6^2 = 36 rectangles and squares.

The important thing here is the factorisation, which becomes just the sum of the whole numbers up to the size of the chessboard in question.

We can therefore answer the question for an 8*8 chessboard: there will be (1+2+3+4+5+6+7+8)^2 = 36^2 = 1296 rectangles of various size.

The general formula is then given by squaring the known formula for sums of whole numbers: 1+2+3...+n = n(n+1)/2, so that the general result is

Total squares/rectangles= (n*(n+1))^2)/4

This is, perhaps not coincidentally, also the formula for the sum of the first n cubic numbers.

[Old_Geezer]

So glad it was a simple solution ;-D

[Gizmonster]

Consider just the top row.
There are 8 (1 X 1) squares; 7 (1 X 2) rectangles; 6 (1 X 3); 5 (1 X 4); 4 (1 X 5); 3 (1 X 6); 2 (1 X 7); 1 (1 X 8).
8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 shapes in total from the top row alone.
Now consider what other shapes are formed when introducing more rows below, when the top row forms part of the shape.
When you introduce 1 extra row it doubles the amount, when you introduce 2 extra rows it trebles the amount .... the addition of 7 more rows increases the amount by a factor of 8, therefore the total number of shapes in an 8 X 8 grid where the top row is the top part of the shape is 8 X 36.
Similarly for the second row down, the total number of shapes formed where the 2nd row down is the top part of the shape is 7 X 36.
Repeating for all 8 rows gives us a total of:
(8 X 36) + (7 X 36) + (6 X 36) + (5 X 36) + (4 X 36) + (3 X 36) + (2 X 36) + 36
This simplifies to:
(8 + 7 + 6 + 5 + 4 + 3 + 2 + 1) X 36
Which simplifies further to:
36 X 36 = 1296.

Same as above :)

[ClareTG0ld]

// So glad it was a simple solution ;-D //

:P

I normally hate using "judgmental words" in my posts -- "simple", "obvious", "clearly", "trivial", etc. -- because they feel quite presumptuous and often the very fact that the question is asked means that the answer *isn't* simple, clear, obvious or whatever. Here it seems appropriate because I'm comparing the answer to what it *could* have been, some horribly large and arbitrary number that you'd have to get by exhaustive counting, or derive in some hideously complex way. So it's comparatively "simple" in that respect: you can deduce the pattern either by thinking about smaller chessboards, as I did it, or by considering a single row and the effect of adding further rows above/below, a la Gizmonster.

A couple of useful extensions:

1. The number of arbitrary rectangles on an n*m chessboard is n(n+1)m(m+1)/4, or just T_n*T_m for triangle numbers T_i = 1,3,6,10...

2. The number of arbitrary squares on an n*n chessboard is equal to the sum of the first n square numbers, and has the formula n(n+1)(2n+1)/6 -- for a standard 8*8 chessboard this comes to 204.

3. The number of arbitrary squares on an n*m chessboard is a formula I'm not aware of having come across before, but turns out to be also relatively compact. Assuming n is smaller than m, then the result is:

No. of squares = n(n+1)(3m-n+1)/6

With m and n reversed in this formula if n is larger. For example, there are 276 squares of various size on a Capablanca chessboard: https://en.wikipedia.org/wiki/Capablanca_chess

[kuiperbelt]

Clare \ Stat with a 2x2 chessboard. There are four small squares, four 1x2 rectangles, and one large square for a total of 9. It's useful to write this in the following way:

Total = 1*1 + 1*2 + 2*1 + 2*2 = (1+2)*(1+2) \

Thanks Clare for your contribution. I am having difficulty formulating the words into the Total = equaton above.

Gizmonster \ Consider just the top row.
There are 8 (1 X 1) squares; 7 (1 X 2) rectangles; 6 (1 X 3); 5 (1 X 4); 4 (1 X 5); 3 (1 X 6); 2 (1 X 7); 1 (1 X 8).

8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 shapes in total from the top row alone. \

This I can get to grips with. Therefore BA to you Giz!!

[ClareTG0ld]

I might have skipped a step in going from the words to the formula, but it's possible to bridge the gap in the following way

there is 1 = 1*1 large square; there are 4 = 2*2 small squares; there are 4 = 2 + 2 = 2*1 + 1*2 of the 1x2 rectangles, where this choice of splitting is perhaps "magic", or at least apparently coming from nowhere, but the point is to split so that I can do the factorising in the next step.

I hope that the full general solution, the several extensions, and a result that is at least much less commonly-encountered, prove useful to you.

[kuiperbelt]

^^^^^^^ Thanks for that Clare!!