Chessboard counting: solutions and further challenges

And now for some solutions to the chessboard counting challenges.

  1. The first challenge was to count the number of squares of any size on an 8×8 chessboard. The key here (as with many counting problems) is to break the problem down in an appropriate way. In this case, we can think about counting each size square separately. There is only one square with sides of length 8. There are 4 squares of size 7—they can be in one of two positions horizontally, and one of two positions vertically. It’s not hard to see that there are 3^2 = 9 squares of size 6, 4^2 = 16 of size 5, and so on. So the total number of squares is 1^2 + 2^2 + \dots + 8^2 = 204.
  2. This pattern continues; on an n by n chessboard, there are 1^2 + 2^2 + \dots + n^2 = \sum_{k=1}^n k^2 total squares. There’s actually a nice closed formula for this sum for general n: \frac{n(n+1)(2n+1)}{6}. (Showing how to derive this formula is a good subject for another post. We can check it for n = 8: (8 \cdot 9 \cdot 17)/6 = 4 \cdot 3 \cdot 17 = 204, as expected.)
  3. Counting rectangles instead of squares turns out not to be too much harder. There are 8 \cdot 8 1 by 1 rectangles, 8 \cdot 7 1 by 2 rectangles, 7 \cdot 8 2 by 1 rectangles, and so on. In general, there are (8 - j + 1)(8 - k + 1) j by k rectangles. So the total number of rectangles is

    \scriptstyle (8 \cdot 8 + 7 \cdot 8 + \dots + 1 \cdot 8) + (8 \cdot 7 + \dots + 1 \cdot 7) + \dots + (8 \cdot 1 + \dots + 1 \cdot 1)

    That looks annoying to add up, but there’s a clever trick we can pull. Notice that we can factor an 8 out of the first parenthesized expression above, a 7 out of the second, and so on, yielding

    \scriptstyle 8(8 + 7 + \dots + 1) + 7(8 + 7 + \dots + 1) + \dots + 1(8 + 7 + \dots + 1)

    But now we can factor (8 + 7 + \dots + 1) out of this, yielding

    (8 + 7 + \dots + 1)^2 = 36^2 = 1296.

    Ah, that’s much nicer!

  4. For a general m by n chessboard, the same method yields

    (m + (m-1) + \dots + 1)(n + (n-1) + \dots + 1)

    total rectangles. Using the closed formula for the sum of the numbers from 1 through n, we can rewrite this as mn(m+1)(n+1)/4.

See the comments to the previous post for some further analysis. Also in the comments, Veky posed the following follow-up challenge: how many squares (or rectangles) are there if we also allow squares (rectangles) which are not parallel to the sides of the chess board—the only restriction is that their vertices must occur at “crosshair” points in between the squares of the chess board?

About these ads
This entry was posted in challenges, counting, solutions and tagged , , , , . Bookmark the permalink.

2 Responses to Chessboard counting: solutions and further challenges

  1. Jonathan says:

    For the number of rectangles, consider each rectangle to be formed by two horizontal and two vertical gridlines. Then we have C(9,2) horizontal choices by C(9,2) vertical. Far more elegant.

  2. Brent says:

    Aha! You’re right, that is far more elegant. It also amounts to a combinatorial argument why (1 + 2 + … + n) = C(n+1,2).

Comments are closed.