Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 1)
Line 4: Line 4:
 
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math>
 
<math>\textbf{(A)}\ 18 \qquad \textbf{(B)}\ 24 \qquad \textbf{(C)}\ 36 \qquad \textbf{(D)}\ 42 \qquad \textbf{(E)}\ 60</math>
  
−
== Solution 1==
+
== 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 the middle square having either of 4-6. Also note that each tableau has a valid symmetrical tableau across the top left square to the bottom right square diagonal. Then, the number of charts is double the following cases.
 +
 
 +
*'''Case 1: Center 4'''
 +
With 4 in center, 3 necessarily must be placed <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\
 +
\hline 3&4&8\\
 +
\hline &&9\\
 +
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\
 +
\hline 3&4&\\
 +
\hline &8&9\\
 +
\hline \end{tabular}</math>, leaving the numbers 5,6,7.
 +
 
 +
Any number could fit into the isolated square in each case, but the next 2 must follow sequentially in the remaining 2 slots. As there are 3 numbers, there are 3 cases for each tableau, leaving 6 overall cases with 4 in the center. Given the diagonal symmetry observed before, the other placements of the 2s and 8s are symmetrical, so multiply by 2. <math>2*6=12</math>
 +
 
 +
*'''Case 2: Center 5'''
 +
<math>\begin{tabular}{|c|c|c|} \hline 1&2&\\
 +
\hline &5&8\\
 +
\hline &&9\\
 +
\hline \end{tabular}</math> and <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\
 +
\hline &5&\\
 +
\hline &8&9\\
 +
\hline \end{tabular}</math>. No 3s or 7s are assured, so this is only a bit trickier and messier. One more level of casework.
 +
 
 +
<math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\
 +
\hline 4&5&\\
 +
\hline &8&9\\
 +
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\
 +
\hline 3&5&\\
 +
\hline &8&9\\
 +
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&\\
 +
\hline 3&5&8\\
 +
\hline &&9\\
 +
\hline \end{tabular}</math> <math>\begin{tabular}{|c|c|c|} \hline 1&2&3\\
 +
\hline 4&5&8\\
 +
\hline &&9\\
 +
\hline \end{tabular}</math>
 +
 
 +
Remembering that 4 cannot go after 5, the numbers of cases are then 2,3,3,1 respectively. As before, multiply by 2 because of symmetry. <math>2*9=18</math>
 +
 
 +
*'''Case 3: Center 6'''
 +
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.
 +
<math>2*6=12</math>
 +
 
 +
Then, <math>12+18+12=\boxed{\textbf{D)}42}</math>
 +
 
 +
~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".
 
The first 4 numbers will form one of 3 tetris "shapes".
  
Line 73: Line 124:
 
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.
 
The answer is <math> 4\times 6 + 2\times 9 = \boxed{\text{(D) }42}</math>.
  
−
== Solution 2==
+
== Solution 3==
 
This solution is trivial by the hook length theorem. The hooks look like this:
 
This solution is trivial by the hook length theorem. The hooks look like this:
  

Revision as of 14:27, 28 December 2019

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

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 the middle square having either of 4-6. Also note that each tableau has a valid symmetrical tableau across the top left square to the bottom right square diagonal. Then, the number of charts is double the following cases.

  • Case 1: Center 4

With 4 in center, 3 necessarily must be placed $\begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline 3&4&8\\ \hline &&9\\ \hline \end{tabular}$ and $\begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline 3&4&\\ \hline &8&9\\ \hline \end{tabular}$, leaving the numbers 5,6,7.

Any number could fit into the isolated square in each case, but the next 2 must follow sequentially in the remaining 2 slots. As there are 3 numbers, there are 3 cases for each tableau, leaving 6 overall cases with 4 in the center. Given the diagonal symmetry observed before, the other placements of the 2s and 8s are symmetrical, so multiply by 2. $2*6=12$

  • Case 2: Center 5

$\begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline &5&8\\ \hline &&9\\ \hline \end{tabular}$ and $\begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline &5&\\ \hline &8&9\\ \hline \end{tabular}$. No 3s or 7s are assured, so this is only a bit trickier and messier. One more level of casework.

$\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}$

Remembering that 4 cannot go after 5, the numbers of cases are then 2,3,3,1 respectively. As before, multiply by 2 because of 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$

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

~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".

First, let's look at the numbers that form a $2\times2$ block, sometimes called tetris $O$:

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

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

Second, let's look at the numbers that form a vertical "L", sometimes called tetris $J$:

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

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

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

Third, let's look at the numbers that form a horizontal "L", sometimes called tetris $L$:

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

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

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

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?

$\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}$

The answer is $4\times 6 + 2\times 9 = \boxed{\text{(D) }42}$.

Solution 3

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.

See also

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_12B_Problems/Problem_17&oldid=113604"