2010 AIME II Problems/Problem 11
Define a T-grid to be a matrix which satisfies the following two properties:
- Exactly five of the entries are 's, and the remaining four entries are 's.
- Among the eight rows, columns, and long diagonals (the long diagonals are and , no more than one of the eight has all three entries equal.
Find the number of distinct T-grids.
The T-grid can be considered as a tic-tac-toe board: five 's (or X's) and four 's (or O's).
There are only ways to fill the board with five 's and four 's. Now we just need to subtract the number of bad grids. Bad grids are ones with more than one person winning, or where someone has won twice.
Let three-in-a-row/column/diagonal be a "win" and let player be the one that fills in and player fills in .
Case : Each player wins once.
If player X takes a diagonal, player Y cannot win. If either takes a row, all the columns are blocked, and visa versa. Therefore, they either both take a row or they both take a column.
- Both take a row:
- There are ways for player to pick a row,
- ways for player to pick a row and,
- ways for player to take a single box in the remaining row.
Therefore, there are cases.
- Both take a column: Using similar reasoning, there are cases.
Case : cases
Case : Player wins twice. (Player cannot win twice because he only has 4 moves.)
- Player picks a row and a column.
- There are ways to pick the row
- and ways to pick the column.
So there are cases.
- Player picks a row/column and a diagonal.
- There are ways to pick the row/column
- and to pick the diagonal,
so there are cases
- 2 diagonals
- It is clear that there is only case. (Make a X).
Thus, the answer is
We can use generating functions to compute the case that no row or column is completely filled with 's. Given a row, let , , be the events that the first, second, third respective squares are 's. Then the generating function representing the possible events that exclude a row of or from occuring is Therefore, the generating function representing the possible grids where no row is filled with 's and 's is We expand this by the Binomial Theorem to find Recall that our grid has five 's, hence we only want terms where the sum of the exponents is . This is given by When we expand this, we find We also want to make sure that each of , , appears at least once (so there is no column filled with 's) and the power of each of , , is not greater than or equal to (so there is no column filled with 's). The sum of the coefficients of the above polynomial is clearly (using ), and the sum of the coefficients of the terms , , and is , hence the sum of the coefficients of the desired terms is . This counts the number of grids where no column or row is filled with 's or 's. However, we could potentially have both diagonals filled with 's, but this is the only exception to our possibilities, hence the number of -grids with no row or column filled with the same digit is .
On the other hand, if a row (column) is filled with 's, then by the Pigeonhole Principle, another row (column) must be filled with 's. Hence this is impossible, so all other possible -grids have a row (column) filled with 's. If the top row is filled with 's, then we have two 's left to place. Clearly they cannot go in the same row, because then the other row is filled with 's. They also cannot appear in the same column. This leaves arrangements--3 choices for the location of the in the second row, and 2 choices for the location of the in the last row. However, two of these arrangements will fill a diagonal with 's. Hence there are only -grids where the top row is filled with 's. The same argument applies if any other row or column is filled with 's. Hence there are such -grids.
Thus the answer is .
|2010 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|