Difference between revisions of "2010 AMC 12B Problems/Problem 17"

Latest revision as of 04:46, 13 June 2024

The following problem is from both the 2010 AMC 12B #17 and 2010 AMC 10B #23, so both problems redirect to this page.

Problem

The entries in a $3 \times 3$ array include all the digits from $1$ through $9$ , arranged so that the entries in every row and column are in increasing order. How many such arrays are there?

$\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60$

Solution 1

Observe that all tables must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each table, there exists a valid table diagonally symmetrical across the diagonal extending from the top left to the bottom right.

Case 1: Center 4

$\begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline 3&4&8\\ \hline &&9\\ \hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline 3&4&\\ \hline &8&9\\ \hline \end{tabular}$

3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant. So, there are 3 cases each and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. $2*6=12$

Case 2: Center 5

$\begin{tabular}{|c|c|c|} \hline 1&2&3\\ \hline 4&5&\\ \hline &8&9\\ \hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline 3&5&\\ \hline &8&9\\ \hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline 3&5&8\\ \hline &&9\\ \hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&2&3\\ \hline 4&5&8\\ \hline &&9\\ \hline \end{tabular}$

Here, no 3s or 7s are assured, but this is only a teensy bit trickier and messier. WLOG, casework with 3 instead of 7 as above. Remembering that $4<5$ , logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, $2*9=18$

Case 3: Center 6

By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured. $2*6=12$

$12+18+12=\boxed{\textbf{D)}42}$

~BJHHar

Solution 2

This solution is trivial by the hook length theorem. The hooks look like this:

$\begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\ \hline 4 & 3 & 2\\ \hline 3 & 2 & 1\\ \hline \end{tabular}$

So, the answer is $\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}$ = $\boxed{\text{(D) }42}$

P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.

Hook length theorem: take any shape made out of congruent squares and say the rules are just like the problem described. Now if you count how many squares are to the right and to the down of it, INCLUDING THE NUMBER ITSELF, then multiply the numbers that have been written down, that is the denominator of the fraction. The numerator is simpler: the factorial of the number of squares. Ex:

$\begin{tabular}{|c|c|c|} \hline 4 & 3 & 2\\ \hline 3 & 2 & 1\\ \hline \end{tabular}$ Therefore answer will be 6!/(4 * 3 * 3 * 2 * 2)

Video Solution

https://youtu.be/ZfnxbpdFKjU?t=422

~IceMatrix

@@ Line 1: / Line 1: @@
+{{duplicate|[[2010 AMC 12B Problems|2010 AMC 12B #17]] and [[2010 AMC 10B Problems|2010 AMC 10B #23]]}}
 == Problem ==
 The entries in a <math>3 \times 3</math> array include all the digits from <math>1</math> through <math>9</math>, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?
@@ Line 5: / Line 7: @@
 == Solution 1 ==
-First, making a chart of ranges of numbers that can exist in each square, observe that all tableaus must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each tableau, there exists a valid tableau diagonally symmetrical across the diagonal extending from the top left to the bottom right.
+Observe that all tables must have 1s and 9s in the corners, 8s and 2s next to those corner squares, and 4-6 in the middle square. Also note that for each table, there exists a valid table diagonally symmetrical across the diagonal extending from the top left to the bottom right.
 *'''Case 1: Center 4'''
@@ Line 16: / Line 19: @@
 \hline \end{tabular}</cmath>
-With 4 in center, 3 necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant in the remaining slots. Then, there are 3 cases per tableau template and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math>
+necessarily must be placed as above. Any number could fill the isolated square, but the other 2 are then invariant. So, there are 3 cases each and 6 overall cases. Given diagonal symmetry, alternate 2 and 8 placements yield symmetrical cases. <math>2*6=12</math>
 *'''Case 2: Center 5'''
@@ Line 39: / Line 42: @@
 <math>2*6=12</math>
-Then, <math>12+18+12=\boxed{\textbf{D)}42}</math>
+<cmath>12+18+12=\boxed{\textbf{D)}42}</cmath>
 ~BJHHar
-P.S.: I like the tetris approach used in 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem.
 == Solution 2==
-The first 4 numbers will form one of 3 tetris "shapes".
+This solution is trivial by the hook length theorem. The hooks look like this:
-First, let's look at the numbers that form a <math>2\times2</math> block, sometimes called tetris <math> O</math>:
+<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\
+\hline 4 & 3 & 2\\
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\
+\hline 3 & 2 & 1\\
-\hline 3 & 4 & \\
-\hline & & \\
 \hline \end{tabular}</math>
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\
+So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math>
-\hline 2 & 4 & \\
-\hline & & \\
-\hline \end{tabular}</math>
-Second, let's look at the numbers that form a vertical "L", sometimes called tetris <math> J</math>:
+P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 4 & \\
+Hook length theorem: take any shape made out of congruent squares and say the rules are just like the problem described. Now if you count how many squares are to the right and to the down of it, INCLUDING THE NUMBER ITSELF, then multiply the numbers that have been written down, that is the denominator of the fraction. The numerator is simpler: the factorial of the number of squares. Ex:
-\hline 2 & & \\
-\hline 3 & & \\
-\hline \end{tabular}</math>
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & \\
+<math> \begin{tabular}{|c|c|c|}
-\hline 2 & & \\
-\hline 4 & & \\
-\hline \end{tabular}</math>
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & \\
-\hline 3 & & \\
-\hline 4 & & \\
-\hline \end{tabular}</math>
-Third, let's look at the numbers that form a horizontal "L", sometimes called tetris <math> L</math>:
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 3 \\
-\hline 4 & & \\
-\hline & & \\
-\hline \end{tabular}</math>
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 2 & 4 \\
-\hline 3 & & \\
-\hline & & \\
-\hline \end{tabular}</math>
-<math> \begin{tabular}{|c|c|c|} \hline 1 & 3 & 4 \\
-\hline 2 & & \\
-\hline & & \\
-\hline \end{tabular}</math>
-Now, the numbers 6-9 will form similar shapes (rotated by 180 degrees, and anchored in the lower-right corner of the 3x3 grid).
-If you match up one tetris shape from the numbers 1-4 and one tetris shape from the numbers 6-9, there is only one place left for the number 5 to be placed.
-So what shapes will physically fit in the 3x3 grid, together?
-<math> \begin{array}{ccl} 1 - 4 \text{ shape} & 6 - 9 \text{ shape} & \text{number of pairings} \\
-O & J & 2\times 3 = 6 \\
-O & L & 2\times 3 = 6 \\
-J & O & 3\times 2 = 6 \\
-J & J & 3 \times 3 = 9 \\
-L & O & 3 \times 2 = 6 \\
-L & L & 3 \times 3 = 9 \\
-O & O & \qquad \text{They don't fit} \\
-J & L & \qquad \text{They don't fit} \\
-L & J & \qquad \text{They don't fit} \\
-\end{array}</math>
-The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.
-== Solution 3==
-This solution is trivial by the hook length theorem. The hooks look like this:
-<math> \begin{tabular}{|c|c|c|} \hline 5 & 4 & 3 \\
 \hline 4 & 3 & 2\\
 \hline 3 & 2 & 1\\
 \hline \end{tabular}</math>
+Therefore answer will be 6!/(4 * 3 * 3 * 2 * 2)
-So, the answer is <math>\frac{9!}{5 \cdot 4 \cdot 3 \cdot 4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1}</math> = <math>\boxed{\text{(D) }42}</math>
+==Video Solution==
+https://youtu.be/ZfnxbpdFKjU?t=422
-P.S. The hook length formula is a formula to calculate the number of standard Young tableaux of a Young diagram. Numberphile has an easy-to-understand video about it here: https://www.youtube.com/watch?v=vgZhrEs4tuk The full proof is quite complicated and is not given in the video, although the video hints at possible proofs.
+~IceMatrix
 == See also ==
 {{AMC12 box|year=2010|num-b=16|num-a=18|ab=B}}
+{{AMC10 box|year=2010|num-b=22|num-a=24|ab=B}}
 [[Category:Introductory Combinatorics Problems]]
 {{MAA Notice}}

2010 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 16	Followed by Problem 18
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

2010 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 22	Followed by Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search