CUNY Math Challenge Blog

Solutions, Resources, Further Information & Discussion

Round 1: Problem 4 Solution

with 2 comments

Chess Board

Chess Board

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.

Advertisements

Written by Administrator

March 16, 2009 at 00:03

2 Responses

Subscribe to comments with RSS.

  1. Richard Stanley (a professor of combinatorics at MIT) has a graduate-level text called Enumerative Combinatorics (2 vols) which has among its many exercises a number that are chess-related. Unfortunately, none of them seem to be available on his website 😦

    JBL

    March 17, 2009 at 18:01

    • His textbook is fabulous. It’s my “favorite” math textbook, and it really is a beautiful compendium of combinatorics.

      Administrator

      March 17, 2009 at 23:02


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: