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.
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?
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
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
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.
P.S.: I like the tetris approach used in Solution 2 but found it a bit arbitrary. Solution 3 is the best, but not many would know hook length theorem. If the initial observations are unclear, make a tableau with a range of possible numbers in each square.
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.
|2010 AMC 12B (Problems • Answer Key • Resources)|
|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|