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 
array include all the digits from 
through 
, arranged so that the entries in every row and column are in increasing order. How many such arrays are there?
Solution 1
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.
- 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}\]](http://latex.artofproblemsolving.com/c/a/f/caf48ebf925e6642ea983260dc322a77a100a088.png)
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. 
- 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}\]](http://latex.artofproblemsolving.com/0/6/2/062f79ecd82412a93b75b35f14a29ed14462fc0c.png)
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 
, logically see that the numbers of cases are then 2,3,3,1 respectively. By symmetry, 
- Case 3: Center 6
By inspection, realize that this is symmetrical to case 1 except that the 7s instead of the 3s are assured.
![\[12+18+12=\boxed{\textbf{D)}42}\]](http://latex.artofproblemsolving.com/3/0/c/30c184c1b20b9078b59d735b5eaba48244e4a096.png)
~BJHHar
Solution 3
This solution is trivial by the hook length theorem. The hooks look like this:
So, the answer is 
= 
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.
Video Solution
https://youtu.be/ZfnxbpdFKjU?t=422
~IceMatrix
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 | |
| 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 | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
