Difference between revisions of "2010 AMC 10B Problems/Problem 23"

(Problem)
(Add an elementary proof, demote the HLF to a note.)
Line 6: Line 6:
  
 
==Solution==
 
==Solution==
By the [http://en.wikipedia.org/wiki/Young_tableau#Dimension_of_a_representation hook-length formula], the answer is <math> \frac{9!}{5\cdot 4^{2}\cdot 3^{3}\cdot 2^{2}\cdot 1}= \boxed{\textbf{(D)}\ 42}</math>
+
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, both lie in the last column, 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.  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 \times 2 + 2\times 6) = \boxed{\textbf{(D)}\ 42}
 +
</cmath>
 +
possible ways to fill the digram.
 +
 
 +
==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 ==
 
== See also ==
 
{{AMC10 box|year=2010|ab=B|num-b=22|num-a=24}}
 
{{AMC10 box|year=2010|ab=B|num-b=22|num-a=24}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 17:18, 27 January 2014

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

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}\] Similarly, the entries 7 and 8 may either both lie in the last row, both lie in the last column, 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,\] where the notation $\times 2$ 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 \times 2 + 2\times 6) =  \boxed{\textbf{(D)}\ 42}\] (Error compiling LaTeX. Unknown error_msg)

possible ways to fill the digram.

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 (ProblemsAnswer KeyResources)
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. AMC logo.png