|
|
| Line 1: |
Line 1: |
| − | ==Problem==
| + | #redirect [[2010 AMC 12B Problems/Problem 17]] |
| − | | |
| − | The entries in a <math>3 \times 3</math> 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?
| |
| − | | |
| − | <math> \textbf{(A)}\ 18\qquad\textbf{(B)}\ 24 \qquad\textbf{(C)}\ 36\qquad\textbf{(D)}\ 42\qquad\textbf{(E)}\ 60 </math>
| |
| − | | |
| − | ==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:
| |
| − | <cmath>
| |
| − | \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}
| |
| − | </cmath>
| |
| − | 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:
| |
| − | <cmath>
| |
| − | \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,
| |
| − | </cmath>
| |
| − | where the notation <math>\times 2</math> denotes two possible cases, either by switching a row and column or by switching the 7 and 8 or 2 and 3. Finally, there are respectively 1, 2, 2, 6 ways to complete these four cases. This gives a total of
| |
| − | <cmath>
| |
| − | 2\cdot\left(1+2\times2+2\times2+2\times6\right)=\boxed{\textbf{(D)}\ 42}
| |
| − | </cmath>
| |
| − | 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 [http://en.wikipedia.org/wiki/Young_tableau#Dimension_of_a_representation hook-length formula].
| |
| − | | |
| − | == See also ==
| |
| − | {{AMC10 box|year=2010|ab=B|num-b=22|num-a=24}}
| |
| − | {{MAA Notice}}
| |
