2022 AMC 10A Problems/Problem 22
Contents
[hide]Problem
Suppose that cards numbered are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards are picked up on the first pass, and on the second pass, on the third pass, on the fourth pass, and on the fifth pass. For how many of the possible orderings of the cards will the cards be picked up in exactly two passes?
Solution 1 (Casework)
For suppose that cards are picked up on the first pass. It follows that cards are picked up on the second pass.
Once we pick the spots for the cards on the first pass, there is only one way to arrange all cards.
For each value of there are ways to pick the spots for the cards on the first pass: We exclude the arrangement in which the first pass consists of all cards.
Therefore, the answer is
~MRENTHUSIASM
Solution 2 (Casework)
Since the cards are picked up in two passes, the first pass must pick up the first cards and the second pass must pick up the remaining cards through . Also note that if , which is the card that is numbered one more than , is placed before , then will not be picked up on the first pass since cards are picked up in order. Therefore we desire to be placed before to create a second pass, and that after the first pass, the numbers through are lined up in order from least to greatest.
To construct this, cannot go in the th position because all cards to will have to precede it and there will be no room for . Therefore must be in slots to . Let's do casework on which slot goes into to get a general idea for how the problem works.
With in spot , there are available slots before , and there are cards preceding . Therefore the number of ways to reserve these slots for the cards is . Then there is only way to order these cards (since we want them in increasing order). Then card goes into whatever slot is remaining, and the cards are ordered in increasing order after slot , giving only way. Therefore in this case there are possibilities.
With in spot , there are available slots before , and there are cards preceding . Therefore the number of ways to reserve slots for these cards are . Then there is one way to order these cards. Then cards and must go in the remaining two slots, and there is only one way to order them since they must be in increasing order. Finally, cards to will be ordered in increasing order after slot , which yields way. Therefore, this case has possibilities.
I think we can see a general pattern now. With in slot , there are slots to distribute to the previous cards, which can be done in ways. Then the remaining cards fill in in just way. Since the cases of start in slot and end in slot , this sum amounts to: for any .
Hmmm ... where have we seen this before?
We use wishful thinking to add a term of :
This is just the hockey stick identity! Applying it, this expression is equal to . However, we added an extra term, so subtracting it off, the total number of ways to order the cards for any is
Finally, to calculate the total for all , we sum from to . This yields us:
~KingRavi
Solution 3 (Recursion)
To solve this problem, we can use recursion on . Let be the number of arrangements for numbers. Now, let's look at how these arrangements are formed by case work on the first number .
If , the remaining numbers from to are arranged in the same way just like number 1 to in the case of numbers. So there are arrangements.
If , then we need to choose 1 position from position 2 to to put 1, and all remaining numbers must be arranged in increasing order, so there are such arrangements.
If , then we need to choose positions from position 2 to to put , and all remaining numbers must be arranged in increasing order, so there are such arrangements.
So we can write which can be simplified to We can solve this recursive sequence by summing up lines of the recursive formula to get since , we have and .
-- Dan Li
Solution 4 (Engineer's Induction)
When we have cards arranged in a row, after listing out all possible arrangements, we see that we have ones: and . When we have cards, we find possible arrangements: and Hence, we recognize the pattern that for cards, we have valid arrangements, so our answer is ~eibc
Solution 5 (Alternative)
Notice that for each card "position", we can choose for it to be picked up on the first or second pass, for a total of options. However, if all of the cards selected to be picked up first are before all of the cards to be picked up second, then this means that the list is in consecutive ascending order (and thus all cards will be picked up on the first pass instead). This can happen in 14 ways, so our answer is .
~pooh_bear
Video Solution by ThePuzzlr
~ MathIsChess
Video Solution by OmegaLearn (Combinatorial Identities and Overcounting)
~ pi_is_3.14
Video Solution by Steven Chen
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
See Also
2022 AMC 10A (Problems • Answer Key • Resources) | ||
Preceded by Problem 21 |
Followed by Problem 23 | |
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 |
2022 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 18 |
Followed by Problem 20 |
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 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.