2010 AMC 10B Problems/Problem 23
Contents
Problem
The entries in a 
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?
Solution
The upper-left corner must contain the entry 1, and similarly the lower-right corner must contain the entry 9. Consider the entries 2 and 3 -- they may either both lie in the first row, both lie in the first column, or lie in the two squares neighboring 1. By symmetry (which we will take into account by a factor of 2 in the end), we may assume that 2 lies in the cell to the right of 1 and that 3 lies either in the cell to the right of 2 or in the cell below 1:
![\[\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\\hline && \\\hline &&\\\hline \end{array} \qquad \begin{array}{|c|c|c|} \hline 1 & 2 & \\\hline 3&& \\\hline &&\\\hline \end{array}\]](http://latex.artofproblemsolving.com/c/c/0/cc0e860552ea33aa90357bd58a50746ea31eaac8.png)
Similarly, the entries 7 and 8 may either both lie in the last row, or lie in the two squares neighboring 9. This gives the following cases:
![\[\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\\hline && \\\hline 7&8&9\\\hline \end{array} \qquad \begin{array}{|c|c|c|} \hline 1 & 2 & \\\hline 3&& \\\hline 7&8&9\\\hline \end{array} \times 2 \qquad \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\\hline &&7 \\\hline &8&9\\\hline \end{array}\times 2 \qquad \begin{array}{|c|c|c|} \hline 1 & 2 & \\\hline 3&&7 \\\hline &8&9\\\hline \end{array}\times 2,\]](http://latex.artofproblemsolving.com/4/f/e/4fe29c889bda6c95e711dab81a8327808534f0e7.png)
where the notation 
denotes two possible cases, either by switching a row and column or by switching the 7 and 8. Finally, there are respectively 1, 2, 2, 6 ways to complete these four cases. This gives a total of
![\[2\cdot\left(1+2\times2+2\times2+2\times6\right)=\boxed{\textbf{(D)}\ 42}\]](http://latex.artofproblemsolving.com/2/7/0/270c5005493b7e74a9ca94c760ec626cbf9836a5.png)
possible ways to fill the diagram.
Notes
In fact, there is a general formula (coming from the fields of combinatorics and representation theory) to answer problems of this form; it is known as the hook-length formula.
See also
| 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. 
