CUNY Math Challenge Blog

Solutions, Resources, Further Information & Discussion

Posts Tagged ‘enumerative combinatorics

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.

Written by Administrator

March 16, 2009 at 00:03

Round 1: Problem 2 Solution

with 3 comments

This problem at first glance appears somewhat cumbersome, but with an easy trick the answer should be found very quickly.

In contrast to the way the problem is written, for simplicity’s sake let us ignore Team B and simply focus on Team A. When Team A wins, we will denote the game with a W. When A loses, an L. Then, we should end up with some combination of W’s and L’s, such as WLWLLWW. Each of these strings of W’s and L’s correspond to a sequence of wins and losses that may occur in the series.

The Principle of Inclusion / Exclusion really should not be needed here. It works, but it’s not necessary. The easiest way to solve the problem is to think about how problematic combinations occur only when a L occurs in the final game. Note that the series can extend to 4, 5, 6, or 7 games. Then to eliminate the problematic combinations, let us force ourselves to pick a W in the final spot. Now all we have to do is consider each series length and pick the other three games that Team A is going to win.

For 4 games, besides the W that was already chosen in the 4th game, there are 3 remaining games, in which we need to place 3 more W’s, which can be done in 3C3 = 1 way.

For 5 games, 4 games remain to place the 3 W’s in 4C3 = 4 ways.

For 6 games, 5 remaining games for the 3 W’s in 5C3 = 10 ways.

Finally, for 7 games, 6 remaining games for the 3 W’s in 6C3 = 20 ways.

In total, that sums to 35 ways. We now multiply by 2 to compensate for the fact that either Team A or Team B can win in any of these ways, giving the final answer of 70 ways for the sequence to occur.

As always, please post any comments, corrections or alternate solutions in the comments. In particular if you’ve worked out the Inclusion / Exclusion, might as well post it.

Written by Administrator

March 16, 2009 at 00:01