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 | + | 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
Contents
[hide]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: 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: 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 \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 (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.