Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 AIME I Problems/Problem 5"

(→‎Solution 7 (Simple and Easy, don't know why it's hard))
(→‎Solution 7 (Casework))
Line 58: Line 58:
 
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 = 52</math>.
  
−
==Solution 7 (Simple and Easy, don't know why it's hard)==
+
==Solution 7 (Casework)==
−
For ascending you can place the <math>1</math> in <math>6</math> locations and the rest of the numbers in <math>4</math> locations based on the sequence <math>1, 2, 3, 4, 5, 6</math>. <math>6 + 4*5 = 26</math>. Multiply by <math>2</math> to account for the descending and get <math>\boxed{52}</math>. ~Lopkiloinm
+
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>. ~ahclark11
  
 
== Video Solution ==
 
== Video Solution ==

Revision as of 16:52, 4 January 2021

Problem

Six cards numbered $1$ through $6$ 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 $1$ through $6$, there are five other spots to put them, so we get $6 \cdot 5 = 30$. However, we overcount some cases. Take the example of $132456$. We overcount this case because we can remove the $3$ or the $2$. Therefore, any cases with two adjacent numbers swapped is overcounted, so we subtract $5$ cases (namely, $213456, 132456, 124356, 123546, 123465$,) to get $30-5=25$, but we have to add back one more for the original case, $123456$. Therefore, there are $26$ cases. Multiplying by $2$ gives the desired answer, $\boxed{052}$.

-molocyxu

Video Solution:

https://www.youtube.com/watch?v=E6YJh7vsLPU

Video solution

https://youtu.be/ctVf7X6fTLI

Solution 2 (Inspired by 2018 CMIMC combo round)

Similar to above, a $1-1$ correspondence between ascending and descending is established by subtracting each number from $7$.

We note that the given condition is equivalent to "cycling" $123456$ for a contiguous subset of it. For example,

$12(345)6 \rightarrow 125346, 124536$

It's not hard to see that no overcount is possible, and that the cycle is either $1$ "right" or $1$ "left." Therefore, we consider how many elements we flip by. If we flip $1$ or $2$ such elements, then there is one way to cycle them. Otherwise, we have $2$ ways. Therefore, the total number of ascending is $1 + 5 + 2(4 + 3 + 2 + 1) = 26$, and multiplying by two gives $\boxed{052}.$ ~awang11

Solution 3

Similarly to above, we find the number of ascending arrangements and multiply by 2.

We can choose $5$ cards to be the ascending cards, therefore leaving $6$ places to place the remaining card. There are $\binom{6}{5}\cdot 6=36$ to do this. However, since the problem is asking for the number of arrangements, we overcount cases such as $123456$. Notice that the only arrangements that overcount are $123456$ (case 1) or if two adjacent numbers of $123456$ are switched (case 2).

$\text{Case 1: }$ This arrangement is counted $6$ times. Each time it is counted for any of the $5$ numbers selected. Therefore we need to subtract $5$ cases of overcounting.

$\text{Case 2: }$ Each time $2$ adjacent numbers of switched, there is one overcount. For example, if we have $213456$, both $1$ or $2$ could be removed. Since there are $5$ possible switches, we need to subtract $5$ cases of overcounting.

Therefore, we have $36-5-5=26$ total arrangements of ascending numbers. We multiply by two (for descending) to get the answer of $\boxed{052}.$ -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 $\boxed{052}.$ -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 $1$ such permutation where all the cards appear in order: $123456.$ There are $5$ such permutations where two adjacent cards are interchanged, as in $124356.$ The other such permutations arise from removing one card from $123456$ and placing it in a position at least two away from its starting location. There are $4$ such positions to place each of the cards numbered $1$ and $6,$ and $3$ such positions for each of the cards numbered $2, 3, 4,$ and $5.$ This accounts for $2\cdot4 + 4\cdot3 =20$ permutations. Thus there are $1 + 5 + 20 = 26$ 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 $26 + 26 = 52$.

Solution 6 (Official MAA 2)

More generally, suppose there are $n \geq 4$ cards numbered $1, 2, 3, \dots, n$ arranged in ascending order. If any one of the $n$ cards is removed and placed in one of the $n$ 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 $n\cdot n = n^2$ permutations. However, the original ascending order has been counted $n$ 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 $n^2-(n-1)-(n-1)=(n-1)^2+1.$ When $n = 6$, this is $(6-1)^2+1 = 26$, and the final answer is $2\cdot26 = 52$.

Solution 7 (Casework)

For ascending, if the $1$ goes in anything but the first two slots, the rest of the numbers have to go in ascending from $2$, which are $4$ cases if there are $6$ cards. If $1$ 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 $6$ cards, that gives $5$ more. If $1$ goes in the first slot, that means that you are doing the same problem with $n-1$ cards. So the recursion is $a_n=(n-2)+(n-1)+a_{n-1}$. There's $a_1=1$ and $a_2=2$, so you get $a_3=2+3=5$, $a_4=5+5=10$, $a_5=7+10=17$, and $a_6=9+17=26$. Or you can see that $a_n=(n-1)^2+1$. We double to account for descending and get $\boxed{052}$. ~ahclark11

Video Solution

https://www.youtube.com/watch?v=5iwdFd2OLKM&list=PLLCzevlMcsWN9y8YI4KNPZlhdsjPTlRrb&index=5 ~ MathEx

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AIME_I_Problems/Problem_5&oldid=141508"