Difference between revisions of "2010 AIME II Problems/Problem 11"
m (Semi-automated contest formatting - script by azjps) |
m (→Solution 2) |
||
(9 intermediate revisions by 8 users not shown) | |||
Line 11: | Line 11: | ||
== Solution == | == Solution == | ||
− | The <i>T-grid</i> can be | + | === Solution 1 === |
+ | The <i>T-grid</i> can be considered as a tic-tac-toe board: five <math>1</math>'s (or X's) and four <math>0</math>'s (or O's). | ||
− | There are <math>\dbinom{9}{5} = 126</math> ways to fill the board with five <math>1</math>'s and four <math>0</math>'s. Now we need to subtract the number of bad grids. | + | There are only <math>\dbinom{9}{5} = 126</math> ways to fill the board with five <math>1</math>'s and four <math>0</math>'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 <math>0</math> be the one that fills in <math>0</math> and player <math>1</math> fills in <math>1</math>. | Let three-in-a-row/column/diagonal be a "win" and let player <math>0</math> be the one that fills in <math>0</math> and player <math>1</math> fills in <math>1</math>. | ||
Line 19: | Line 20: | ||
<b>Case <math>1</math>:</b> Each player wins once. | <b>Case <math>1</math>:</b> Each player wins once. | ||
− | If player takes a diagonal, | + | 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. |
− | |||
<OL> | <OL> | ||
− | <LI>Both | + | <LI>Both take a row: |
<UL> | <UL> | ||
− | <LI><math>3</math> ways for player <math>1</math> to pick a row, </LI> | + | <LI>There are <math>3</math> ways for player <math>1</math> to pick a row, </LI> |
− | <LI><math>2</math> ways for player <math>0</math>, </LI> | + | <LI><math>2</math> ways for player <math>0</math> to pick a row and, </LI> |
<LI><math>3</math> ways for player <math>0</math> to take a single box in the remaining row. </LI> | <LI><math>3</math> ways for player <math>0</math> to take a single box in the remaining row. </LI> | ||
</UL> | </UL> | ||
− | + | Therefore, there are <math>3 \cdot 2 \cdot 3=18</math> cases. | |
</LI> | </LI> | ||
− | <LI>Both | + | <LI>Both take a column: |
− | Using | + | Using similar reasoning, there are <math>18</math> cases. |
</OL> | </OL> | ||
Line 45: | Line 45: | ||
<br/> | <br/> | ||
− | <b>Case <math>2</math>:</b> Player <math>1</math> wins twice. | + | <b>Case <math>2</math>:</b> Player <math>1</math> wins twice. (Player <math>0</math> cannot win twice because he only has 4 moves.) |
<OL> | <OL> | ||
− | <LI> | + | <LI>Player <math>1</math> picks a row and a column. |
<UL> | <UL> | ||
− | <LI><math>3</math> ways to pick the row | + | <LI>There are <math>3</math> ways to pick the row</LI> |
− | <LI><math>3</math> to pick the column. </LI> | + | <LI>and <math>3</math> ways to pick the column. </LI> |
− | + | So there are <math>9</math> cases. | |
</UL></LI> | </UL></LI> | ||
− | <LI> | + | <LI>Player <math>1</math> picks a row/column and a diagonal. |
<UL> | <UL> | ||
− | <LI><math>6</math> ways to pick the row/column | + | <LI>There are <math>6</math> ways to pick the row/column </LI> |
− | <LI><math>2</math> to pick the diagonal | + | <LI>and <math>2</math> to pick the diagonal, </LI> |
− | + | </UL> | |
− | + | so there are <math>12</math> cases | |
+ | </LI> | ||
<LI>2 diagonals | <LI>2 diagonals | ||
− | + | <UL> | |
− | It is clear that there is only <math>1</math> case.</LI> | + | <LI>It is clear that there is only <math>1</math> case. (Make a X).</LI> |
+ | </UL> | ||
+ | </LI> | ||
</OL> | </OL> | ||
Line 71: | Line 74: | ||
<br/> | <br/> | ||
− | Thus, the answer is <math>126-22-36=\boxed{ | + | Thus, the answer is <math>126-22-36=\boxed{68}</math> |
+ | |||
+ | === Solution 2 === | ||
+ | |||
+ | We can use [[generating functions]] to compute the case that no row or column is completely filled with <math>1</math>'s. Given a row, let <math>a</math>, <math>b</math>, <math>c</math> be the events that the first, second, third respective squares are <math>1</math>'s. Then the generating function representing the possible events that exclude a row of <math>1,1,1</math> or <math>0,0,0</math> from occuring is | ||
+ | <cmath>ab+bc+ca+a+b+c.</cmath> | ||
+ | Therefore, the generating function representing the possible grids where no row is filled with <math>0</math>'s and <math>1</math>'s is | ||
+ | <cmath>P(a,b,c)=((ab+bc+ca)+(a+b+c))^3.</cmath> | ||
+ | We expand this by the Binomial Theorem to find | ||
+ | <cmath>P(a,b,c)=(ab+bc+ca)^3+3(ab+bc+ca)^2(a+b+c)+3(ab+bc+ca)(a+b+c)^2+(a+b+c)^3.</cmath> | ||
+ | Recall that our grid has five <math>1</math>'s, hence we only want terms where the sum of the exponents is <math>5</math>. This is given by | ||
+ | <cmath>3(ab+bc+ca)^2(a+b+c).</cmath> | ||
+ | When we expand this, we find | ||
+ | <cmath>3(2abc(a+b+c)+a^2b^2+b^2c^2+c^2a^2)(a+b+c).</cmath> | ||
+ | We also want to make sure that each of <math>a</math>, <math>b</math>, <math>c</math> appears at least once (so there is no column filled with <math>0</math>'s) and the power of each of <math>a</math>, <math>b</math>, <math>c</math> is not greater than or equal to <math>3</math> (so there is no column filled with <math>1</math>'s). The sum of the coefficients of the above polynomial is clearly <math>81</math> (using <math>a,b,c=1</math>), and the sum of the coefficients of the terms <math>a^3bc</math>, <math>ab^3c</math>, and <math>abc^3</math> is <math>6+6+6+3+3+3+3+3+3=36</math>, hence the sum of the coefficients of the desired terms is <math>81-36=45</math>. This counts the number of grids where no column or row is filled with <math>0</math>'s or <math>1</math>'s. However, we could potentially have both diagonals filled with <math>1</math>'s, but this is the only exception to our <math>45</math> possibilities, hence the number of <math>T</math>-grids with no row or column filled with the same digit is <math>44</math>. | ||
+ | |||
+ | On the other hand, if a row (column) is filled with <math>0</math>'s, then by the Pigeonhole Principle, another row (column) must be filled with <math>1</math>'s. Hence this is impossible, so all other possible <math>T</math>-grids have a row (column) filled with <math>1</math>'s. If the top row is filled with <math>1</math>'s, then we have two <math>1</math>'s left to place. Clearly they cannot go in the same row, because then the other row is filled with <math>0</math>'s. They also cannot appear in the same column. This leaves <math>3\cdot 2</math> arrangements--3 choices for the location of the <math>1</math> in the second row, and 2 choices for the location of the <math>1</math> in the last row. However, two of these arrangements will fill a diagonal with <math>1</math>'s. Hence there are only <math>4</math> <math>T</math>-grids where the top row is filled with <math>1</math>'s. The same argument applies if any other row or column is filled with <math>1</math>'s. Hence there are <math>4\cdot 6=24</math> such <math>T</math>-grids. | ||
+ | |||
+ | Thus the answer is <math>44+24=\boxed{68}</math>. | ||
== See also == | == See also == | ||
{{AIME box|year=2010|num-b=10|num-a=12|n=II}} | {{AIME box|year=2010|num-b=10|num-a=12|n=II}} | ||
− | + | [[Category:Intermediate Combinatorics Problems]] | |
− | [[Category:Intermediate | + | {{MAA Notice}} |
Latest revision as of 00:58, 8 January 2023
Contents
[hide]Problem
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.
Solution
Solution 1
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).
Case total:
Thus, the answer is
Solution 2
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 .
See also
2010 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.