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 "2022 AMC 12A Problems/Problem 19"

(→‎Solution 3)
(→‎Solution 3)
Line 111: Line 111:
 
==Solution 3==
 
==Solution 3==
 
Let the cards picked up in the first pass be <math>1, 2, \ldots, n</math>, where <math>1 \leq n \leq 12</math>. Then there are <math>\binom{13}{n} -1</math> ways the cards could have originally been arranged, as to place the cards we must choose <math>n</math> of the original <math>13</math> spots to place the <math>n</math> cards from <math>1</math> to <math>n</math> (in that order). However, we must discard the case where the first <math>n</math> spaces are taken up by these cards, as then the cards would all be picked up in one pass. Hence, our desired number of ways to arrange the cards is
 
Let the cards picked up in the first pass be <math>1, 2, \ldots, n</math>, where <math>1 \leq n \leq 12</math>. Then there are <math>\binom{13}{n} -1</math> ways the cards could have originally been arranged, as to place the cards we must choose <math>n</math> of the original <math>13</math> spots to place the <math>n</math> cards from <math>1</math> to <math>n</math> (in that order). However, we must discard the case where the first <math>n</math> spaces are taken up by these cards, as then the cards would all be picked up in one pass. Hence, our desired number of ways to arrange the cards is
−
<cmath>\sum_{n=1}^{12} \left(\binom{13}{n} -1\right) = \left(\sum_{n=1}^{12} \binom{13}{n}\right) - 12 = \left(\sum_{n=0}^{13} \binom{13}{n}\right) - \binom{13}{0} - \binom{13}{13} - 12 = 2^13 - 1 - 1 - 12 = \boxed{8178}.</cmath>
+
<cmath>\sum_{n=1}^{12} \left(\binom{13}{n} -1\right) = \left(\sum_{n=1}^{12} \binom{13}{n}\right) - 12 = \left(\sum_{n=0}^{13} \binom{13}{n}\right) - \binom{13}{0} - \binom{13}{13} - 12 = 2^{13} - 1 - 1 - 12 = \boxed{\textbf{(D)}\ 8178}.</cmath>
  
 
== Video Solution By ThePuzzlr ==  
 
== Video Solution By ThePuzzlr ==  

Revision as of 15:07, 13 November 2022

Problem

Suppose that 13 cards numbered $1, 2, 3, \cdots, 13$ 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 1, 2, 3 are picked up on the first pass, 4 and 5 on the second pass, 6 on the third pass, 7, 8, 9, 10 on the fourth pass, and 11, 12, 13 on the fifth pass. For how many of the $13!$ possible orderings of the cards will the $13$ cards be picked up in exactly two passes?

[asy] size(11cm); draw((0,0)--(2,0)--(2,3)--(0,3)--cycle); label("7", (1,1.5)); draw((3,0)--(5,0)--(5,3)--(3,3)--cycle); label("11", (4,1.5)); draw((6,0)--(8,0)--(8,3)--(6,3)--cycle); label("8", (7,1.5)); draw((9,0)--(11,0)--(11,3)--(9,3)--cycle); label("6", (10,1.5)); draw((12,0)--(14,0)--(14,3)--(12,3)--cycle); label("4", (13,1.5)); draw((15,0)--(17,0)--(17,3)--(15,3)--cycle); label("5", (16,1.5)); draw((18,0)--(20,0)--(20,3)--(18,3)--cycle); label("9", (19,1.5)); draw((21,0)--(23,0)--(23,3)--(21,3)--cycle); label("12", (22,1.5)); draw((24,0)--(26,0)--(26,3)--(24,3)--cycle); label("1", (25,1.5)); draw((27,0)--(29,0)--(29,3)--(27,3)--cycle); label("13", (28,1.5)); draw((30,0)--(32,0)--(32,3)--(30,3)--cycle); label("10", (31,1.5)); draw((33,0)--(35,0)--(35,3)--(33,3)--cycle); label("2", (34,1.5)); draw((36,0)--(38,0)--(38,3)--(36,3)--cycle); label("3", (37,1.5)); [/asy] $\textbf{(A) } 4082 \qquad \textbf{(B) } 4095 \qquad \textbf{(C) } 4096 \qquad \textbf{(D) } 8178 \qquad \textbf{(E) } 8191$

Solution

Solution 1

Since the $13$ cards are picked up in two passes, the first pass must pick up the first $n$ cards and the second pass must pick up the remaining cards $m$ through $13$. Also note that if $m$, which is the card that is numbered one more than $n$, is placed before $n$, then $m$ will not be picked up on the first pass since cards are picked up in order. Therefore we desire $m$ to be placed before $n$ to create a second pass, and that after the first pass, the numbers $m$ through $13$ are lined up in order from least to greatest.

To construct this, $n$ cannot go in the $n$th position because all cards $1$ to $n-1$ will have to precede it and there will be no room for $m$. Therefore $n$ must be in slots $n+1$ to $13$. Let's do casework on which slot $n$ goes into to get a general idea for how the problem works.


$\textbf{Case 1:}$ With $n$ in spot $n+1$, there are $n$ available slots before $n$, and there are $n-1$ cards preceding $n$. Therefore the number of ways to reserve these slots for the $n-1$ cards is $\binom{n}{n-1}$. Then there is only $1$ way to order these cards (since we want them in increasing order). Then card $m$ goes into whatever slot is remaining, and the $13-m$ cards are ordered in increasing order after slot $n+1$, giving only $1$ way. Therefore in this case there are $\binom{n}{n-1}$ possibilities.


$\textbf{Case 2:}$ With $n$ in spot $n+2$, there are $n+1$ available slots before $n$, and there are $n-1$ cards preceding $n$. Therefore the number of ways to reserve slots for these cards are $\binom{n+1}{n-1}$. Then there is one way to order these cards. Then cards $m$ and $m+1$ 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 $m+2$ to $13$ will be ordered in increasing order after slot $n+1$, which yields $1$ way. Therefore, this case has $\binom{n+1}{n-1}$ possibilities.



I think we can see a general pattern now. With $n$ in slot $x$, there are $x-1$ slots to distribute to the previous $n-1$ cards, which can be done in $\binom{x-1}{n-1}$ ways. Then the remaining cards fill in in just $1$ way. Since the cases of $n$ start in slot $n+1$ and end in slot $13$, this sum amounts to: \[\binom{n}{n-1}+\binom{n+1}{n-1}+\binom{n+2}{n-1} + \cdots + \binom{12}{n-1}\] for any $n$.

Hmmm... where have we seen this before?

We use wishful thinking to add a term of $\binom{n-1}{n-1}$: \[\binom{n-1}{n-1}+\binom{n}{n-1}+\binom{n+1}{n-1}+\binom{n+2}{n-1} + \cdots + \binom{12}{n-1}\]

This is just the hockey stick identity! Applying it, this expression is equal to $\binom{13}{n}$. However, we added an extra term, so subtracting it off, the total number of ways to order the $13$ cards for any $n$ is \[\binom{13}{n}-1\]

Finally, to calculate the total for all $n$, we sum from $n=0$ to $13$. This yields us:

\[\sum_{n=0}^{13} \binom{13}{n}-1 \implies \sum_{n=0}^{13} \binom{13}{n} - \sum_{n=0}^{13} 1\] \[\implies 2^{13} - 14 = 8192 - 14 = 8178 = \boxed{D}\]


~KingRavi


Solution 2

To solve this problem, we can use recursion on $n$. Let $A_n$ be the number of arrangements for $n$ numbers. Now, let's look at how these arrangements are formed by case work on the first number $a_1$.

If $a_1 = 1$, the remaining $n-1$ numbers from $2$ to $n$ are arranged in the same way just like number 1 to $n-1$ in the case of $n-1$ numbers. So there are $A_{n-1}$ arrangements.

If $a_1 = 2$, then we need to choose 1 position from position 2 to $n-1$ to put 1, and all remaining numbers must be arranged in increasing order, so there are $\binom{n-1}{1}$ such arrangements.

If $a_1 = k$, then we need to choose $k-1$ positions from position 2 to $n-1$ to put $1, 2,\cdots k-1$, and all remaining numbers must be arranged in increasing order, so there are $\binom{n-1}{k-1}$ such arrangements.

So we can write \[A_n = A_{n-1} + \binom{n-1}{1} + \binom{n-1}{2} + \cdots + \binom{n-1}{n-1}\] which can be simplified to \[A_n = A_{n-1} + 2^{n-1} - 1\] We can solve this recursive sequence by summing up $n-1$ lines of the recursive formula \[A_n - A_{n-1} = 2^{n-1} - 1\] \[A_{n-1} - A_{n-2} = 2^{n-2} - 1\] \[\cdots\] \[A_2 - A_{1} = 2^{1} - 1\] to get \[A_n - A_1 = \sum_{k=1}^{n-1} (2^k - 1) = 2^n - 2 - (n-1) = 2^n - n - 1\] since $A_1=0$, we have \[A_n = 2^n - n - 1\] and $A_{13} = 2^{13} - 14 = \boxed{8178}$.

So the answer is $\boxed{D}$

-- Dan Li

Solution 3

Let the cards picked up in the first pass be $1, 2, \ldots, n$, where $1 \leq n \leq 12$. Then there are $\binom{13}{n} -1$ ways the cards could have originally been arranged, as to place the cards we must choose $n$ of the original $13$ spots to place the $n$ cards from $1$ to $n$ (in that order). However, we must discard the case where the first $n$ spaces are taken up by these cards, as then the cards would all be picked up in one pass. Hence, our desired number of ways to arrange the cards is \[\sum_{n=1}^{12} \left(\binom{13}{n} -1\right) = \left(\sum_{n=1}^{12} \binom{13}{n}\right) - 12 = \left(\sum_{n=0}^{13} \binom{13}{n}\right) - \binom{13}{0} - \binom{13}{13} - 12 = 2^{13} - 1 - 1 - 12 = \boxed{\textbf{(D)}\ 8178}.\]

Video Solution By ThePuzzlr

https://youtu.be/p9xNduqTKLM

~ MathIsChess

Solution by OmegaLearn Using Combinatorial Identities and Overcounting

https://youtu.be/gW8gPEEHSfU

~ pi_is_3.14

Solution

https://youtu.be/ZGqrs5eg6-s

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

See Also

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
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

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=2022_AMC_12A_Problems/Problem_19&oldid=181296"