2020 AIME I Problems/Problem 5
Note: Please do not post problems here until after the AIME.
Six cards numbered through are to be lined up in a row. Find the number of arrangements of these six cards where one of the cards can be removed leaving the remaining five cards in either ascending or descending order.
Realize that any sequence that works (ascending) can be reversed for descending, so we can just take the amount of sequences that satisfy the ascending condition and multiply by two.
If we choose any of the numbers through , there are five other spots to put them, so we get . However, we overcount some cases. Take the example of . We overcount this case because we can remove the or the . Therefore, any cases with two adjacent numbers swapped is overcounted, so we subtract cases (namely, ,) to get , but we have to add back one more for the original case, . Therefore, there are cases. Multiplying by gives the desired answer, .
Solution 2 (Inspired by 2018 CMIMC combo round)
Similar to above, a correspondence between ascending and descending is established by subtracting each number from .
We note that the given condition is equivalent to "cycling" for a contiguous subset of it. For example,
It's not hard to see that no overcount is possible, and that the cycle is either "right" or "left." Therefore, we consider how many elements we flip by. If we flip or such elements, then there is one way to cycle them. Otherwise, we have ways. Therefore, the total number of ascending is , and multiplying by two gives ~awang11
|2020 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|