Difference between revisions of "2020 AIME I Problems/Problem 5"
(→Solution 4 (No overcounting)) |
|||
Line 32: | Line 32: | ||
== Solution 4 (No overcounting) == | == Solution 4 (No overcounting) == | ||
− | Like in previous solutions, we calculate the number of ascending arrangements and | + | Like in previous solutions, we will calculate the number of ascending arrangements and multiply by 2. |
First, consider the arrangement 1-2-3-4-5-6. That gives us 1 arrangement which works. | First, consider the arrangement 1-2-3-4-5-6. That gives us 1 arrangement which works. | ||
Line 45: | Line 45: | ||
Finally, we calculate that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer <math>\boxed{052}.</math> -i8Pie | Finally, we calculate that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer <math>\boxed{052}.</math> -i8Pie | ||
+ | |||
==See Also== | ==See Also== | ||
{{AIME box|year=2020|n=I|num-b=4|num-a=6}} | {{AIME box|year=2020|n=I|num-b=4|num-a=6}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 10:26, 15 March 2020
Contents
Problem
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.
Solution 1
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,
.
-molocyxu
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
Solution 3
Similarly to above, we find the number of ascending arrangements and multiply by 2.
We can choose cards to be the ascending cards, therefore leaving
places to place the remaining card. There are
to do this. However, since the problem is asking for the number of arrangements, we overcount cases such as
. Notice that the only arrangements that overcount are
(case 1) or if two adjacent numbers of
are switched (case 2).
This arrangement is counted
times. Each time it is counted for any of the
numbers selected. Therefore we need to subtract
cases of overcounting.
Each time
adjacent numbers of switched, there is one overcount. For example, if we have
, both
or
could be removed. Since there are
possible switches, we need to subtract
cases of overcounting.
Therefore, we have total arrangements of ascending numbers. We multiply by two (for descending) to get the answer of
-PCChess
Solution 4 (No overcounting)
Like in previous solutions, we will calculate the number of ascending arrangements and multiply by 2.
First, consider the arrangement 1-2-3-4-5-6. That gives us 1 arrangement which works.
Next, we can switch two adjacent cards. There are 5 ways to pick two adjacent cards, so this gives us 5 arrangements.
Now, we can "cycle" 3 adjacent cards. For example, 1-2-3 becomes 2-3-1 which becomes 3-1-2. There are 4 ways to pick a set of 3 adjacent cards, so this gives us 4x2=8 arrangements.
Cycling 4 adjacent cards, we get the new arrangements 2-3-4-1 (which works,) 3-4-1-2 (which doesn't work,) and 4-1-2-3 (which does work.) We get 6 arrangements.
Similarly, when cycling 5 cards, we get 2x2=4 ways, and when cycling 6 cards, we get 2x1=2 ways.
Finally, we calculate that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer -i8Pie
See Also
2020 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.