2012 AMC 10B Problems/Problem 22
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?
If we have 1 as the first number, then the only possible list is .
If we have 2 as the first number, then we have 9 ways to choose where the goes, and the numbers ascend from the first number, , with the exception of the . For example, , or . There are ways to do so.
If we use 3 as the first number, we need to choose 2 spaces to be 2 and 1, respectively. There are ways to do this.
In the same way, the total number of lists is:
By the binomial theorem, this is = , or
Arrange the spaces and put arrows pointing either up or down between them. Then for each arrangement of arrows there is one and only one list that corresponds to up. For example, all arrows pointing up is . There are 9 arrows, so the answer is =
NOTE: Solution cited from: http://www.artofproblemsolving.com/Videos/external.php?video_id=269.
Notice that the answer to the problem is solely based on the length of the lists, i.e. 10. We can replace 10 with smaller values, such as 2 and 3, and try to find a pattern. If we replace it with 2, we can easily see that there are two possible lists, and . If we replace it with 3, there are four lists, and . Since 2 and 4 are both powers of 2, it is likely that the number of lists is , where is the length of the lists.
We define 'transition' as the move from the th index to the th index. Note that from the transition from the th index to the th index, you can either move to or . Therefore, there are options for each transition. Since there are 9 total transitions (from the first index to the tenth index), the answer is .
Video Solution by Richard Rusczyk
|2012 AMC 10B (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 10 Problems and Solutions|