Treebeard's Stumper Answer 15 May 98

Chess Squares

Last year at this time, Chess master Garry Kasparov was having trouble with IBM's Deep Blue program. Here's an easier chess problem for the rest of us. There are 64 single squares on a normal 8 by 8 chessboard. But the chessboard itself is also one big 8 by 8 square, there are lots of overlapping 2 by 2 squares on the board, and there are many others. So how many squares are there altogether, of any integer size? Hint: start at the upper left corner and count different size squares across and down, looking for a pattern. What about an arbitrary size n-by-n or n-by-m chessboard?

There's one big 8 by 8 square on a chessboard. It's easy to see that there are also four 7 by 7 squares. Start at the upper left corner with one 7 by 7 square, then shift it one square to the right for a second. Drop it down one row for two more. Two rows with two squares each gives 2x2 = 4 squares. With 6 by 6 squares, there are three rows of three squares each for 3x3 = 9 squares. The pattern is now clear. There are 1+(2x2)+(3x3)+...+(8x8) = 204 squares total. The same pattern holds for any size chessboard.

Note: The general answer for a n-by-n chessboard is the sum of the squares of the integers to n. This number is given by the formula:

            n(n+1)(2n+1)
     sum =  ------------
                 6      

This sum is also the number of cannonballs in a 4-sided pyramid n layers high. It is related to the Twelve Days of Christmas stumper, in which n(n+1)(n+2)/6 gives the number of cannonballs that can be stacked in a 3-sided pyramid.

Counting squares in an n-by-m chessboard is considerably more difficult!

Consider a 3-by-5 grid, with the short side on top.

• Place a 3 by 3 square at the top, as large as can be. We can't shift it across, but we can shift it down twice, for a total of 1 x 3 = 3 big squares.

• Now place a 2 by 2 square at the top. We can shift it 1 square to the right, for 2 squares on a row. We can also shift it down 3 times, so there are 4 rows total. That's 2 x 4 = 8 squares.

• Finally, there are 3 single squares in each row, and 5 rows, so there are 3 x 5 = 15 more squares.

The total is therefore:

        3 x 5 = 15
     +  2 x 4 =  8
     +  1 x 3 =  3
     -------------
                26 squares total

This example shows the pattern. In general, for n >= m the number of squares is:

     sum = (m)(n) + (m-1)(n-1) + (m-2)(n-2) + ... + (1)(n-m+1)

In the special case of a square chessboard, n = m, so this reduces to the answer given above. With some algebra, I managed to reduce this series to a simple formula:

     sum = m(m+1)(3n-m+1)/6

It works! Note that if n = m, this reduces to n(n+1)(2n+1)/6 as it should.

This stumper can be further generalized. How many rectangles are there in a n-by-n or n-by-m chessboard? What about higher dimensions? What about other tiling shapes? Are there interesting general solutions?

Back to Stumper

Last modified .