2012 AMC 12B Problems/Problem 18
Let be a list of the first 10 positive integers such that for each either or or both appear somewhere before in the list. How many such lists are there?
Let . Assume that . If , the first number appear after that is greater than must be , otherwise if it is any number larger than , there will be neither nor appearing before . Similarly, one can conclude that if , the first number appear after that is larger than must be , and so forth.
On the other hand, if , the first number appear after that is less than must be , and then , and so forth.
To count the number of possibilities when is given, we set up spots after , and assign of them to the numbers less than and the rest to the numbers greater than . The number of ways in doing so is choose .
Therefore, when summing up the cases from to , we get
This problem is worded awkwardly. More simply, it asks: “How many ways can you order numbers 1-10 so that each number is one above or below some previous term?”
Then, the method becomes clear. For some initial number, WLOG examine the numbers greater than it. They always must appear in ascending order later in the list, though not necessarily as adjacent terms. Then, for some initial number, the number of possible lists is just the number of combination where this number of terms can be placed in 9 slots. For 9, that’s 1 number in 9 potential slots. For 8, that’s 2 numbers in 9 potential slots.
Solution 3 (Noticing Stuff)
If there is only 1 number, the number of ways to order would be 1. If there are 2 numbers, the number of ways to order would be 2. If there are 3 numbers, by listing out, the number of ways is 4. We can then make a conjecture that the problem is simply powers of 2.
Solution 4 (fast and clever)
Assume that the first element is any integer. Since we can only add the integer 1 more than the current max or 1 less the current min, there are 2 possibilities for each element after the first. Once we have created a set of 10 elements, we can shift all of the elements by some constant so that they will be the first 10 positive integers. Thus the total possibilities is .
Solution 5 (Recursion)
For a list with terms, valid lists with terms can be created by ways:
1. Add to the end of the list, making a new list
2. Increase the value of all existing terms by one, making a new list . Then add to the end of the list, making a new list
Let be the number of lists with elements, . As , ,
Video Solution by Richard Rusczyk
Video Solution by IceMatrix
|2012 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|