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)
(→‎Solution)
Line 39: Line 39:
 
Finally, to calculate the total for all <math>n</math>, we sum from <math>n=0</math> to <math>13</math>. This yields us:
 
Finally, to calculate the total for all <math>n</math>, we sum from <math>n=0</math> to <math>13</math>. This yields us:
  
−
<cmath>\sum_{n=0}^{13} \binom{13}{n}-1 \implies \sum_{n=0}^{13} \binom{13}{n} - \sum_{n=0}^{13} -1</cmath>
+
<cmath>\sum_{n=0}^{13} \binom{13}{n}-1 \implies \sum_{n=0}^{13} \binom{13}{n} - \sum_{n=0}^{13} 1</cmath>
 
<cmath>\implies 2^{13} - 14 = 8192 - 14 = 8178 = \boxed{D}</cmath>
 
<cmath>\implies 2^{13} - 14 = 8192 - 14 = 8178 = \boxed{D}</cmath>
  

Revision as of 12:13, 12 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?

XXX [Image]

$\textbf{(A) } 4082 \qquad \textbf{(B) } 4095 \qquad \textbf{(C) } 4096 \qquad \textbf{(D) } 8178 \qquad \textbf{(E) } 8191$

Solution

Solution

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

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=181022"