2010 AMC 12B Problems/Problem 17

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)

~edits by glowworm

Solution 3 (Doesn't require the hook length formula, copied from Solution 1)

As Solution number one and the videos said 1 and 9 must go on the top left and top right. The middle must be 4, 5, or 6 because there must be two numbers less than it to fill the top middle and left middle squares (so 2 and 3 can't be in the middle) and two numbers more than it to fil the right middle and bottom middle squares (7 and 8 don’t work).

So, first casework with the middle being 4. 2 and 3 must go in the middle top and the middle left boxes because they are the only boxes smaller than 4. They can flip their places in the middle top and middle left boxes. $\begin{tabular}{|c|c|c|} \hline 1&2&\\ \hline 3&4&\\ \hline &&9\\ \hline \end{tabular} \;\;\; \begin{tabular}{|c|c|c|} \hline 1&3&\\ \hline 2&4&\\ \hline &&9\\ \hline \end{tabular}$

For middle is 5, the numbers 2, 3, and 4 will fill in spaces until the diagonal with 5, and either the top right or bottom left square will be left blank (no blanks before that because the box must increase). So there are 2 choices which one to leave blank. There are 3 choices for the box (either 2, 3, or 4) immediately next to the blank box and the other 2 numbers (from 2, 3, or 4) will sort themselves. Now there are 2 empty spaces in one horizontal or vertical row with 9, and 1 empty space in the middle of the other row with 9 and a value of 2, 3, or 4. Pick either 6, 7, or 8 to fil that box and the other row will sort itself with the remaining two numbers. Thus, there are 2x3x3=18 ways. For middle is 4, the numbers 2 and 3 must go in the middle top and the middle left boxes because those are the only boxes smaller than 4. For the rightmost row, choose 2 from 4 to fill in that row, and on the bottommost row the other two numbers will sort themselves. So there are 4C2 = 6. 6x2 = 12 For middle is 6, it is symmetric to the middle being 4 because 7 or 8 must be in the middle bottom or middle right. Then 4C2 for one of the symmetric other part of the row with 9, and then the numbers wil sort themselves. 6x2 = 12 18+12+12=42

Video Solution by Pi Academy (Fast and Easy)

https://youtu.be/3gwxQ1fjxQM?si=oL0HxnoYSgyl1Rh6

~ Pi Academy

Video Solution 2

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

~IceMatrix

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