Difference between revisions of "2020 AIME I Problems/Problem 5"
m (→Solution 8(symmetry and case study)) |
MRENTHUSIASM (talk | contribs) (→Solution 12 (Undercount+add cases)) |
||
(25 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | |||
== Problem == | == Problem == | ||
Six cards numbered <math>1</math> through <math>6</math> 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. | Six cards numbered <math>1</math> through <math>6</math> 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. | ||
Line 8: | Line 7: | ||
If we choose any of the numbers <math>1</math> through <math>6</math>, there are five other spots to put them, so we get <math>6 \cdot 5 = 30</math>. However, we overcount some cases. Take the example of <math>132456</math>. We overcount this case because we can remove the <math>3</math> or the <math>2</math>. Therefore, any cases with two adjacent numbers swapped is overcounted, so we subtract <math>5</math> cases (namely, <math>213456, 132456, 124356, 123546, 123465</math>,) to get <math>30-5=25</math>, but we have to add back one more for the original case, <math>123456</math>. Therefore, there are <math>26</math> cases. Multiplying by <math>2</math> gives the desired answer, <math>\boxed{052}</math>. | If we choose any of the numbers <math>1</math> through <math>6</math>, there are five other spots to put them, so we get <math>6 \cdot 5 = 30</math>. However, we overcount some cases. Take the example of <math>132456</math>. We overcount this case because we can remove the <math>3</math> or the <math>2</math>. Therefore, any cases with two adjacent numbers swapped is overcounted, so we subtract <math>5</math> cases (namely, <math>213456, 132456, 124356, 123546, 123465</math>,) to get <math>30-5=25</math>, but we have to add back one more for the original case, <math>123456</math>. Therefore, there are <math>26</math> cases. Multiplying by <math>2</math> gives the desired answer, <math>\boxed{052}</math>. | ||
− | + | ~molocyxu | |
− | == Solution 2 (Inspired by 2018 CMIMC | + | == Solution 2 (Inspired by 2018 CMIMC Combo Round) == |
Similar to above, a <math>1-1</math> correspondence between ascending and descending is established by subtracting each number from <math>7</math>. | Similar to above, a <math>1-1</math> correspondence between ascending and descending is established by subtracting each number from <math>7</math>. | ||
Line 18: | Line 17: | ||
<math>12(345)6 \rightarrow 125346, 124536</math> | <math>12(345)6 \rightarrow 125346, 124536</math> | ||
− | It's not hard to see that no overcount is possible, and that the cycle is either <math>1</math> "right" or <math>1</math> "left." Therefore, we consider how many elements we flip by. If we flip <math>1</math> or <math>2</math> such elements, then there is one way to cycle them. Otherwise, we have <math>2</math> ways. Therefore, the total number of ascending is <math>1 + 5 + 2(4 + 3 + 2 + 1) = 26</math>, and multiplying by two gives <math>\boxed{052}.</math> ~awang11 | + | It's not hard to see that no overcount is possible, and that the cycle is either <math>1</math> "right" or <math>1</math> "left." Therefore, we consider how many elements we flip by. If we flip <math>1</math> or <math>2</math> such elements, then there is one way to cycle them. Otherwise, we have <math>2</math> ways. Therefore, the total number of ascending is <math>1 + 5 + 2(4 + 3 + 2 + 1) = 26</math>, and multiplying by two gives <math>\boxed{052}.</math> |
+ | |||
+ | ~awang11 | ||
== Solution 3 == | == Solution 3 == | ||
Line 29: | Line 30: | ||
<math>\text{Case 2: }</math> Each time <math>2</math> adjacent numbers of switched, there is one overcount. For example, if we have <math>213456</math>, both <math>1</math> or <math>2</math> could be removed. Since there are <math>5</math> possible switches, we need to subtract <math>5</math> cases of overcounting. | <math>\text{Case 2: }</math> Each time <math>2</math> adjacent numbers of switched, there is one overcount. For example, if we have <math>213456</math>, both <math>1</math> or <math>2</math> could be removed. Since there are <math>5</math> possible switches, we need to subtract <math>5</math> cases of overcounting. | ||
− | Therefore, we have <math>36-5-5=26</math> total arrangements of ascending numbers. We multiply by two (for descending) to get the answer of <math>\boxed{052}.</math> | + | Therefore, we have <math>36-5-5=26</math> total arrangements of ascending numbers. We multiply by two (for descending) to get the answer of <math>\boxed{052}.</math> |
+ | |||
+ | ~PCChess | ||
− | == Solution 4 (No | + | == Solution 4 (No Overcounting) == |
Like in previous solutions, we will count the number of ascending arrangements and multiply by 2. | Like in previous solutions, we will count the number of ascending arrangements and multiply by 2. | ||
Line 40: | Line 43: | ||
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. | 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, | + | 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 find 2x2=4 arrangements, and when cycling 6 cards, we find 2x1=2 arrangements. | Similarly, when cycling 5 cards, we find 2x2=4 arrangements, and when cycling 6 cards, we find 2x1=2 arrangements. | ||
− | Adding, we figure out that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer <math>\boxed{052}.</math> | + | Adding, we figure out that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer <math>\boxed{052}.</math> |
+ | |||
+ | ~i8Pie | ||
+ | |||
==Solution 5 (Official MAA 1)== | ==Solution 5 (Official MAA 1)== | ||
− | First count the number of permutations of the cards such that if one card is removed, the remaining cards will be in ascending order. There is <math>1</math> such permutation where all the cards appear in order: <math>123456.</math> There are <math>5</math> such permutations where two adjacent cards are interchanged, as in <math>124356.</math> The other such permutations arise from removing one card from <math>123456</math> and placing it in a position at least two away from its starting location. There are <math>4</math> such positions to place each of the cards numbered <math>1</math> and <math>6,</math> and <math>3</math> such positions for each of the cards numbered <math>2, 3, 4,</math> and <math>5.</math> This accounts for <math>2\cdot4 + 4\cdot3 =20</math> permutations. Thus there are <math>1 + 5 + 20 = 26</math> permutations where one card can be removed so that the remaining cards are in ascending order. There is an equal number of permutations that result in the cards' being in descending order. This gives the total <math>26 + 26 = 52</math>. | + | First count the number of permutations of the cards such that if one card is removed, the remaining cards will be in ascending order. There is <math>1</math> such permutation where all the cards appear in order: <math>123456.</math> There are <math>5</math> such permutations where two adjacent cards are interchanged, as in <math>124356.</math> The other such permutations arise from removing one card from <math>123456</math> and placing it in a position at least two away from its starting location. There are <math>4</math> such positions to place each of the cards numbered <math>1</math> and <math>6,</math> and <math>3</math> such positions for each of the cards numbered <math>2, 3, 4,</math> and <math>5.</math> This accounts for <math>2\cdot4 + 4\cdot3 =20</math> permutations. Thus there are <math>1 + 5 + 20 = 26</math> permutations where one card can be removed so that the remaining cards are in ascending order. There is an equal number of permutations that result in the cards' being in descending order. This gives the total <math>26 + 26 = \boxed{52}</math>. |
+ | |||
==Solution 6 (Official MAA 2)== | ==Solution 6 (Official MAA 2)== | ||
− | More generally, suppose there are <math>n \geq 4</math> cards numbered <math>1, 2, 3, \dots, n</math> arranged in ascending order. If any one of the <math>n</math> cards is removed and placed in one of the <math>n</math> positions in the arrangement, the resulting permutation will have the property that one card can be removed so that the remaining cards are in ascending order. This accounts for <math>n\cdot n = n^2</math> permutations. However, the original ascending order has been counted <math>n</math> times, and each order that arises by switching two neighboring cards has been counted twice. Hence the number of arrangements where one card can be removed resulting in the remaining cards' being in ascending order is <math>n^2-(n-1)-(n-1)=(n-1)^2+1.</math> When <math>n = 6</math>, this is <math>(6-1)^2+1 = 26</math>, and the final answer is <math>2\cdot26 = 52</math>. | + | More generally, suppose there are <math>n \geq 4</math> cards numbered <math>1, 2, 3, \dots, n</math> arranged in ascending order. If any one of the <math>n</math> cards is removed and placed in one of the <math>n</math> positions in the arrangement, the resulting permutation will have the property that one card can be removed so that the remaining cards are in ascending order. This accounts for <math>n\cdot n = n^2</math> permutations. However, the original ascending order has been counted <math>n</math> times, and each order that arises by switching two neighboring cards has been counted twice. Hence the number of arrangements where one card can be removed resulting in the remaining cards' being in ascending order is <math>n^2-(n-1)-(n-1)=(n-1)^2+1.</math> When <math>n = 6</math>, this is <math>(6-1)^2+1 = 26</math>, and the final answer is <math>2\cdot26 = \boxed{52}</math>. |
==Solution 7 (Casework)== | ==Solution 7 (Casework)== | ||
− | For ascending, if the <math>1</math> goes in anything but the first two slots, the rest of the numbers have to go in ascending from <math>2</math>, which are <math>4</math> cases if there are <math>6</math> cards. If <math>1</math> goes in the second spot, then you can put any of the rest in the first slot but then the rest are determined, so in the case of <math>6</math> cards, that gives <math>5</math> more. If <math>1</math> goes in the first slot, that means that you are doing the same problem with <math>n-1</math> cards. So the recursion is <math>a_n=(n-2)+(n-1)+a_{n-1}</math>. There's <math>a_1=1</math> and <math>a_2=2</math>, so you get <math>a_3=2+3=5</math>, <math>a_4=5+5=10</math>, <math>a_5=7+10=17</math>, and <math>a_6=9+17=26</math>. Or you can see that <math>a_n=(n-1)^2+1</math>. We double to account for descending and get <math>\boxed{052}</math>. | + | For ascending, if the <math>1</math> goes in anything but the first two slots, the rest of the numbers have to go in ascending from <math>2</math>, which are <math>4</math> cases if there are <math>6</math> cards. If <math>1</math> goes in the second spot, then you can put any of the rest in the first slot but then the rest are determined, so in the case of <math>6</math> cards, that gives <math>5</math> more. If <math>1</math> goes in the first slot, that means that you are doing the same problem with <math>n-1</math> cards. So the recursion is <math>a_n=(n-2)+(n-1)+a_{n-1}</math>. There's <math>a_1=1</math> and <math>a_2=2</math>, so you get <math>a_3=2+3=5</math>, <math>a_4=5+5=10</math>, <math>a_5=7+10=17</math>, and <math>a_6=9+17=26</math>. Or you can see that <math>a_n=(n-1)^2+1</math>. We double to account for descending and get <math>\boxed{052}</math>. |
− | ==Solution 8( | + | ~ahclark11 |
+ | |||
+ | ==Solution 8 (Symmetry and Case Study)== | ||
First, we know that ascending order and descending order are symmetrical to each other (namely, if we get 132456 where after we take out 3, it will be one scenario; and if we flip it and write 654231, it will be another scenario) | First, we know that ascending order and descending order are symmetrical to each other (namely, if we get 132456 where after we take out 3, it will be one scenario; and if we flip it and write 654231, it will be another scenario) | ||
Line 59: | Line 68: | ||
WLOG let us consider ascending order | WLOG let us consider ascending order | ||
− | Case 1: after we take out 1, the rest will be in ascending order | + | Case 1: after we take out 1, the rest will be in ascending order: |
+ | <center>2 3 4 5 6</center> | ||
+ | Notice that 1 can be tucked in any one of the 6 spaces, thus there are 6 scenarios. | ||
− | 2 3 4 5 6 | + | Case 2: after we take out 2, the rest will be in ascending order: |
+ | <center>1 3 4 5 6</center> | ||
+ | Notice that if we put 2 next to 1 (to the right or to the left of 1), it will be an overcount, so there are only 4 cases for 2. | ||
− | + | It is easy to see that this is the same for 3, 4, 5, and 6. | |
+ | |||
+ | Thus, in total, we have <cmath>(6+4\times5)\times2=\boxed{052}</cmath> | ||
+ | ~Adali | ||
+ | |||
+ | ==Solution 9 (Illustration)== | ||
+ | We start with five cards in ascending order, then insert the sixth card to obtain a valid arrangement. | ||
+ | |||
+ | Based on the card to be inserted, we have six cases. As shown below, the red squares indicate the possible positions to insert the sixth card. | ||
+ | <asy> | ||
+ | /* Made by MRENTHUSIASM */ | ||
+ | unitsize(7mm); | ||
− | + | void drawSquare(real x, real y) | |
+ | { | ||
+ | draw((x+0.5,y+0.5)--(x-0.5,y+0.5)--(x-0.5,y-0.5)--(x+0.5,y-0.5)--cycle,red); | ||
+ | } | ||
− | + | label("$2$",(0.5,8)); | |
+ | label("$3$",(2.5,8)); | ||
+ | label("$4$",(4.5,8)); | ||
+ | label("$5$",(6.5,8)); | ||
+ | label("$6$",(8.5,8)); | ||
+ | label("Insert $1.$",(13.5,8),red); | ||
+ | drawSquare(-0.5,8); | ||
+ | drawSquare(1.5,8); | ||
+ | drawSquare(3.5,8); | ||
+ | drawSquare(5.5,8); | ||
+ | drawSquare(7.5,8); | ||
+ | drawSquare(9.5,8); | ||
− | + | label("$1$",(0.5,6.5)); | |
+ | label("$3$",(2.5,6.5)); | ||
+ | label("$4$",(4.5,6.5)); | ||
+ | label("$5$",(6.5,6.5)); | ||
+ | label("$6$",(8.5,6.5)); | ||
+ | label("Insert $2.$",(13.5,6.5),red); | ||
+ | drawSquare(3.5,6.5); | ||
+ | drawSquare(5.5,6.5); | ||
+ | drawSquare(7.5,6.5); | ||
+ | drawSquare(9.5,6.5); | ||
− | + | label("$1$",(0.5,5)); | |
+ | label("$2$",(2.5,5)); | ||
+ | label("$4$",(4.5,5)); | ||
+ | label("$5$",(6.5,5)); | ||
+ | label("$6$",(8.5,5)); | ||
+ | label("Insert $3.$",(13.5,5),red); | ||
+ | drawSquare(-0.5,5); | ||
+ | drawSquare(5.5,5); | ||
+ | drawSquare(7.5,5); | ||
+ | drawSquare(9.5,5); | ||
+ | |||
+ | label("$1$",(0.5,3.5)); | ||
+ | label("$2$",(2.5,3.5)); | ||
+ | label("$3$",(4.5,3.5)); | ||
+ | label("$5$",(6.5,3.5)); | ||
+ | label("$6$",(8.5,3.5)); | ||
+ | label("Insert $4.$",(13.5,3.5),red); | ||
+ | drawSquare(-0.5,3.5); | ||
+ | drawSquare(1.5,3.5); | ||
+ | drawSquare(7.5,3.5); | ||
+ | drawSquare(9.5,3.5); | ||
+ | |||
+ | label("$1$",(0.5,2)); | ||
+ | label("$2$",(2.5,2)); | ||
+ | label("$3$",(4.5,2)); | ||
+ | label("$4$",(6.5,2)); | ||
+ | label("$6$",(8.5,2)); | ||
+ | label("Insert $5.$",(13.5,2),red); | ||
+ | drawSquare(-0.5,2); | ||
+ | drawSquare(1.5,2); | ||
+ | drawSquare(3.5,2); | ||
+ | drawSquare(9.5,2); | ||
+ | |||
+ | label("$1$",(0.5,0.5)); | ||
+ | label("$2$",(2.5,0.5)); | ||
+ | label("$3$",(4.5,0.5)); | ||
+ | label("$4$",(6.5,0.5)); | ||
+ | label("$5$",(8.5,0.5)); | ||
+ | label("Insert $6.$",(13.5,0.5),red); | ||
+ | drawSquare(-0.5,0.5); | ||
+ | drawSquare(1.5,0.5); | ||
+ | drawSquare(3.5,0.5); | ||
+ | drawSquare(5.5,0.5); | ||
+ | </asy> | ||
+ | Note that all arrangements of the six cards are distinct. | ||
+ | |||
+ | There are <math>26</math> arrangements in which removing one card will leave the remaining five cards in ascending order. By symmetry, there are <math>26</math> arrangements in which removing one card will leave the remaining five cards in descending order. So, the answer is <math>26\cdot2=\boxed{052}.</math> | ||
+ | |||
+ | ~MRENTHUSIASM | ||
+ | |||
+ | ==Solution 10 == | ||
+ | We first realize that as long as we have an ascending sequence of <math>5</math> numbers, we can just plug in a <math>6</math>th to make a sequence that works. For example, if we have <math>12345</math>, we can plug in a <math>6</math> in any of <math>6</math> spaces, before <math>1</math>, between <math>1</math> and <math>2</math>, and so on to after <math>5</math>. We can also realize that this is completely symmetrical if the sequence is in descending order. For example, we could have <math>54321</math>, and we could plug in a 6 in 6 of the spaces. For the total number of combinations, we have 6 ascending cases multiplied by the <math>6</math> places that can hold whatever number is missing, and multiply by 2 because there is descending and ascending number cases. | ||
+ | |||
+ | But wait, what if we have <math>12345</math> and plug in a <math>6</math> at the end and <math>12346</math> and plug in a <math>5</math> at the <math>5</math>th spot? We have overcounted, so we need to subtract off the identical pairs. Assume that one of them is the "right" combination. That means that there are <math>1</math> "right" combination because all the rest will have <math>2</math> of their combinations taken by the previous one. For example, if I have <math>12356</math> and <math>12346</math>, I would count those <math>123456</math> as <math>12356</math>'s instead of <math>12346</math>'s. Therefore, we have <math>6+4+4+4+4+4 = 26</math> combinations of ascending order, and since we need to count those of descending order as well, we have <math>26\cdot2=\boxed{052}.</math> | ||
+ | |||
+ | Side note: We could have just realized that the first part was unnecessary, but it does help you understand the problem better. | ||
+ | |||
+ | ~Arcticturn | ||
+ | |||
+ | ==Solution 11== | ||
+ | Like the previous solutions, we calculate ascending possibilities then multiply by two. Then, the configuration can look like +++++ or +-+++ (the minus can go anywhere), where "+" indicates an increase, and "-" indicates a decrease. Obviously, for the first case, the only possibility is 123456. For the second case, we can start with 123456, and then take either a card after the "-" and put it before the "-", or we could take a card before the "-" and put it after the "-". This means that every card other than the one at the position of the "-" can be used in one way. There are five ways to have 4 plus's, and one minus, and for each way, there are 5 ways to rearrange 123456 to achieve that. So, our answer is <math>2(5\cdot5+1)=\boxed{052}</math> | ||
+ | |||
+ | ==Solution 12 (Undercount+add cases)== | ||
+ | First, we select <math>5</math> of the <math>6</math> cards to put in ascending or descending order. Then, we must add the other card to the group to arrange the six cards such that one can be removed so that the remaining cards are in ascending or descending order. Then, it would seem that the answer is <math>(6C5)*2</math>(ascending or descending)*<math>6</math>(the number of ways to place the last card). However, this overcounts some cases. For example, 123456 and 654321 can be made with 12345 and 6, 12346 and 5, etc. Furthermore, 654312 can be made with 65432 and 1 or 65431 and 2. Therefore, we first find that <math>(6C5)*2*4</math>=<math>48</math>. Then, we add the special cases (<math>123456</math>, <math>654321</math>, <math>654312</math>, <math>123465</math>) to obtain <math>\boxed{052}</math>. | ||
− | + | ~mathMagicOPS | |
− | |||
− | ~ | ||
− | == Video Solution == | + | ==Video Solution== |
https://www.youtube.com/watch?v=5iwdFd2OLKM&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=5 ~ MathEx | https://www.youtube.com/watch?v=5iwdFd2OLKM&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=5 ~ MathEx | ||
Line 84: | Line 192: | ||
https://www.youtube.com/watch?v=E6YJh7vsLPU | https://www.youtube.com/watch?v=E6YJh7vsLPU | ||
− | ==Video | + | ==Video Solution== |
https://youtu.be/ctVf7X6fTLI | https://youtu.be/ctVf7X6fTLI | ||
− | |||
==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}} | ||
[[Category: Intermediate Combinatorics Problems]] | [[Category: Intermediate Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 19:05, 11 July 2023
Contents
- 1 Problem
- 2 Solution 1
- 3 Solution 2 (Inspired by 2018 CMIMC Combo Round)
- 4 Solution 3
- 5 Solution 4 (No Overcounting)
- 6 Solution 5 (Official MAA 1)
- 7 Solution 6 (Official MAA 2)
- 8 Solution 7 (Casework)
- 9 Solution 8 (Symmetry and Case Study)
- 10 Solution 9 (Illustration)
- 11 Solution 10
- 12 Solution 11
- 13 Solution 12 (Undercount+add cases)
- 14 Video Solution
- 15 Video Solution
- 16 Video Solution
- 17 See Also
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 count 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 find 2x2=4 arrangements, and when cycling 6 cards, we find 2x1=2 arrangements.
Adding, we figure out that there are 1+5+8+6+4+2=26 ascending arrangements. Multiplying by 2, we get the answer
~i8Pie
Solution 5 (Official MAA 1)
First count the number of permutations of the cards such that if one card is removed, the remaining cards will be in ascending order. There is such permutation where all the cards appear in order:
There are
such permutations where two adjacent cards are interchanged, as in
The other such permutations arise from removing one card from
and placing it in a position at least two away from its starting location. There are
such positions to place each of the cards numbered
and
and
such positions for each of the cards numbered
and
This accounts for
permutations. Thus there are
permutations where one card can be removed so that the remaining cards are in ascending order. There is an equal number of permutations that result in the cards' being in descending order. This gives the total
.
Solution 6 (Official MAA 2)
More generally, suppose there are cards numbered
arranged in ascending order. If any one of the
cards is removed and placed in one of the
positions in the arrangement, the resulting permutation will have the property that one card can be removed so that the remaining cards are in ascending order. This accounts for
permutations. However, the original ascending order has been counted
times, and each order that arises by switching two neighboring cards has been counted twice. Hence the number of arrangements where one card can be removed resulting in the remaining cards' being in ascending order is
When
, this is
, and the final answer is
.
Solution 7 (Casework)
For ascending, if the goes in anything but the first two slots, the rest of the numbers have to go in ascending from
, which are
cases if there are
cards. If
goes in the second spot, then you can put any of the rest in the first slot but then the rest are determined, so in the case of
cards, that gives
more. If
goes in the first slot, that means that you are doing the same problem with
cards. So the recursion is
. There's
and
, so you get
,
,
, and
. Or you can see that
. We double to account for descending and get
.
~ahclark11
Solution 8 (Symmetry and Case Study)
First, we know that ascending order and descending order are symmetrical to each other (namely, if we get 132456 where after we take out 3, it will be one scenario; and if we flip it and write 654231, it will be another scenario)
Thus, we only need to consider either descending or ascending and then times 2. WLOG let us consider ascending order
Case 1: after we take out 1, the rest will be in ascending order:
Notice that 1 can be tucked in any one of the 6 spaces, thus there are 6 scenarios.
Case 2: after we take out 2, the rest will be in ascending order:
Notice that if we put 2 next to 1 (to the right or to the left of 1), it will be an overcount, so there are only 4 cases for 2.
It is easy to see that this is the same for 3, 4, 5, and 6.
Thus, in total, we have
~Adali
Solution 9 (Illustration)
We start with five cards in ascending order, then insert the sixth card to obtain a valid arrangement.
Based on the card to be inserted, we have six cases. As shown below, the red squares indicate the possible positions to insert the sixth card.
Note that all arrangements of the six cards are distinct.
There are arrangements in which removing one card will leave the remaining five cards in ascending order. By symmetry, there are
arrangements in which removing one card will leave the remaining five cards in descending order. So, the answer is
~MRENTHUSIASM
Solution 10
We first realize that as long as we have an ascending sequence of numbers, we can just plug in a
th to make a sequence that works. For example, if we have
, we can plug in a
in any of
spaces, before
, between
and
, and so on to after
. We can also realize that this is completely symmetrical if the sequence is in descending order. For example, we could have
, and we could plug in a 6 in 6 of the spaces. For the total number of combinations, we have 6 ascending cases multiplied by the
places that can hold whatever number is missing, and multiply by 2 because there is descending and ascending number cases.
But wait, what if we have and plug in a
at the end and
and plug in a
at the
th spot? We have overcounted, so we need to subtract off the identical pairs. Assume that one of them is the "right" combination. That means that there are
"right" combination because all the rest will have
of their combinations taken by the previous one. For example, if I have
and
, I would count those
as
's instead of
's. Therefore, we have
combinations of ascending order, and since we need to count those of descending order as well, we have
Side note: We could have just realized that the first part was unnecessary, but it does help you understand the problem better.
~Arcticturn
Solution 11
Like the previous solutions, we calculate ascending possibilities then multiply by two. Then, the configuration can look like +++++ or +-+++ (the minus can go anywhere), where "+" indicates an increase, and "-" indicates a decrease. Obviously, for the first case, the only possibility is 123456. For the second case, we can start with 123456, and then take either a card after the "-" and put it before the "-", or we could take a card before the "-" and put it after the "-". This means that every card other than the one at the position of the "-" can be used in one way. There are five ways to have 4 plus's, and one minus, and for each way, there are 5 ways to rearrange 123456 to achieve that. So, our answer is
Solution 12 (Undercount+add cases)
First, we select of the
cards to put in ascending or descending order. Then, we must add the other card to the group to arrange the six cards such that one can be removed so that the remaining cards are in ascending or descending order. Then, it would seem that the answer is
(ascending or descending)*
(the number of ways to place the last card). However, this overcounts some cases. For example, 123456 and 654321 can be made with 12345 and 6, 12346 and 5, etc. Furthermore, 654312 can be made with 65432 and 1 or 65431 and 2. Therefore, we first find that
=
. Then, we add the special cases (
,
,
,
) to obtain
.
~mathMagicOPS
Video Solution
https://www.youtube.com/watch?v=5iwdFd2OLKM&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=5 ~ MathEx
Video Solution
https://www.youtube.com/watch?v=E6YJh7vsLPU
Video Solution
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.