## Posts Tagged ‘**counting**’

## Round 1: Problem 4 Solution

For this problem, we will need first to count all the rectangles on the 8×8 chessboard, and then to subtract out all the squares on the board.

The easiest way to count the total number of rectangles (including squares) is to visualize the chessboard as being bound by 9 vertical lines and 9 horizontal lines. These 9 lines in each direction form the 8×8 grid in their interiors. By visualizing the board in such a way, finding the number of rectangles becomes trivial using a bit of combinatorial thinking. Within the board, a rectangle may be of any size, and start at any point. So we must merely pick at which of these 9 lines to start from, and at which of these 9 lines to end. Doing this for both horizontal and vertical lines then forms a rectangle. For example, if we were to pick the first line and the ninth line both horizontally and vertically, the rectangle that would be formed is the outer frame of the board. In total, then, we can pick horizontal bounds in 9C2 ways, and independently we can pick vertical bounds in 9C2 ways. Therefore the total number of rectangles is simply 9C2 x 9C2 = **1296 rectangles**.

To arrive at a final answer, we need to subtract out the number of squares. The number of squares on the board are interestingly enough the square numbers. There are 64 1×1 squares, 49 2×2 squares, 36 3×3 squares, 25 4×4 squares, 16 5×5 squares, 9 6×6 squares, 4 7×7 squares and 1 8×8 square = **204 squares**. Try it: start drawing them out and notice the pattern.

Subtracting the two, the answer is then **1092 non-square rectangles**.

For a similar problem, check out Project Euler’s Problem 85. On a personal note, I happen to love combinatorics, especially enumerative combinatorics, and most recently I’ve developed an affinity for chess-related problems. For an extensive discussion see the book Across the Board: The Mathematics of Chessboard Problems, which in my humble opinion is a fantastic book of just about everything you ever did or didn’t want to know about math and chess.

As always, please post any comments, corrections or alternate solutions in the comments.

Credit for the (great) Chessboard Photo goes to Otbora.