AMC 10 · 2022 · #22
Grade 8 arithmeticProblem
Suppose that 13 cards numbered 1,2,3,…,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?
Pick an answer.
AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: We arrange $13$ numbered cards $1, 2, \ldots, 13$ in a row. In each pass we scan left to right and pick up the next-numbered uncollected card whenever it lies to the right of the previously picked card in that pass. How many of the $13!$ orderings get the cards picked up in exactly two passes?
Givens: $13$ cards labeled $1, 2, \ldots, 13$ in a row; Pass rule: left-to-right scan, pick the smallest uncollected number whose position is to the right of the previously picked card in this pass; Total orderings: $13!$; Answer choices: (A) $4082$, (B) $4095$, (C) $4096$, (D) $8178$, (E) $8191$
Unknowns: The number of orderings finished in exactly two passes
Understand
Restated: We arrange $13$ numbered cards $1, 2, \ldots, 13$ in a row. In each pass we scan left to right and pick up the next-numbered uncollected card whenever it lies to the right of the previously picked card in that pass. How many of the $13!$ orderings get the cards picked up in exactly two passes?
Givens: $13$ cards labeled $1, 2, \ldots, 13$ in a row; Pass rule: left-to-right scan, pick the smallest uncollected number whose position is to the right of the previously picked card in this pass; Total orderings: $13!$; Answer choices: (A) $4082$, (B) $4095$, (C) $4096$, (D) $8178$, (E) $8191$
Plan
Primary tool: #9 Solve an Easier Related Problem
Secondary: #2 Make a Systematic List, #5 Look for a Pattern, #16 Change Focus / Count the Complement, #3 Eliminate Possibilities
Tool #9 (Easier Problem) and #2 (Systematic List): try the question for $n = 2, 3, 4$ cards by listing every permutation and counting passes. The data points fit the formula $2^n - n - 1$ (Tool #5). Why? Tool #16 (Complement / re-cast): pass 1 collects an initial segment $\{1, \ldots, k\}$, and an ordering uses at most two passes iff cards $\{1, \ldots, k\}$ are in increasing relative order AND cards $\{k+1, \ldots, 13\}$ are in increasing relative order — that is, the permutation is the shuffle of two increasing subsequences. There are $\binom{13}{k}$ such shuffles for each $k$, but each non-trivial labeling of cards as 'first set' vs 'second set' is unique except for the fully sorted permutation which counts in every $k$. Tool #3 confirms the magnitude $\approx 8000$ rules out (A)-(C).
Execute — Answer: D
3.OA.D.9 Step 1 - Try $n = 2$.
- The two orderings are $12$ (one pass) and $21$ (two passes).
- Two-pass count $= 1$.
💡 Grade 3 — try a tiny case to feel out the rule.
4.OA.C.5 Step 2 - Try $n = 3$.
- List all $6$ orderings and simulate.
- $123$: one pass.
- $132$: pass 1 picks $1, 2$, pass 2 picks $3$ — two passes.
- $213$: pass 1 picks $1$, pass 2 picks $2, 3$ — two passes.
- $231$: pass 1 picks $1$, pass 2 picks $2, 3$ — two passes.
- $312$: pass 1 picks $1, 2$, pass 2 picks $3$ — two passes.
- $321$: pass 1 picks $1$, pass 2 picks $2$, pass 3 picks $3$ — three passes.
- Two-pass count $= 4 = 2^3 - 3 - 1$.
💡 Grade 4 — enumerate by rule and tally; pattern $2^n - n - 1$ shows up after just two data points.
7.SP.C.8 Step 3 - Generalize.
- In any ordering, pass 1 collects exactly the cards $\{1, 2, \ldots, k\}$ where $k$ is the largest number such that card $1$, card $2$, ..., card $k$ appear in left-to-right order in the row (positions strictly increasing).
- Pass 2 then collects $\{k+1, \ldots, 13\}$ in one pass iff their positions are also strictly increasing.
- So 'at most two passes' is the same as 'the row is the shuffle of two increasing subsequences $\{1, \ldots, k\}$ and $\{k+1, \ldots, 13\}$ for some $0 \le k \le 13$'.
💡 Grade 7 — recast the picking process as a structural property of the permutation.
7.SP.C.8 Step 4 - Count 'at most 2 passes' for $n = 13$.
- Pick the subset $A \subseteq \{1, \ldots, 13\}$ of positions that will hold the 'low' cards.
- Once $A$ is chosen, the low cards $\{1, \ldots, |A|\}$ go into $A$ in increasing order and the high cards $\{|A|+1, \ldots, 13\}$ go into the rest in increasing order — exactly one ordering per subset.
- So the number of 'at most 2-pass' orderings equals the number of subsets of $\{1, \ldots, 13\}$: $2^{13} = 8192$.
💡 Grade 7 — each subset of positions for the low cards gives exactly one valid ordering.
8.EE.A.1 Step 5 - Remove over-counts and subtract one-pass.
- Two different subsets can give the same permutation only when that permutation is fully sorted: for the sorted ordering, every prefix $A = \{1, 2, \ldots, k\}$ ($k = 0, 1, \ldots, 13$) places the low cards correctly, so the sorted permutation is counted $14$ times.
- All other $\le 2$-pass orderings are counted exactly once.
- So distinct $\le 2$-pass orderings $= (2^{13} - 14) + 1 = 8179$.
- Exactly one of these (the sorted permutation) uses one pass, leaving two-pass count $= 8179 - 1 = 8178$, choice (D).
💡 Grade 8 — $2^{13}$ from powers of $2$; remove the $13$ duplicates of the sorted ordering, then subtract the sorted ordering itself as one-pass.
3.OA.D.9 Try $n = 2$. The two orderings are $12$ (one pass) and $21$ (two passes). Two-pa 4.OA.C.5 Try $n = 3$. List all $6$ orderings and simulate. $123$: one pass. $132$: pass 1 7.SP.C.8 Generalize. In any ordering, pass 1 collects exactly the cards ${1, 2, \ldots, 7.SP.C.8 Count 'at most 2 passes' for $n = 13$. Pick the subset $A \subseteq {1, \ldots, 8.EE.A.1 Remove over-counts and subtract one-pass. Two different subsets can give the sam Review
Reasonableness: Pattern check from the small cases: $n=2$ gave $1 = 4 - 3$, $n=3$ gave $4 = 8 - 4$. The formula $2^n - n - 1$ matches both, and for $n=13$ gives $8192 - 14 = 8178$, exactly one of the offered choices. The answer is well under $13!$ (about $6.2 \times 10^9$), as expected — the two-pass orderings are a tiny structured subset of all permutations.
Alternative: Tool #3 (Eliminate). The answer must be close to $2^{13} = 8192$ because $\le 2$ pass orderings already cap at $2^{13}$, and the one-pass count is tiny. Choices (A) $4082$, (B) $4095$, (C) $4096$ are all near $2^{12}$, ruling them out — those would correspond to one-sided shuffles, not the full two-pass count. (E) $8191 = 2^{13} - 1$ over-counts by one. Only (D) $8178$ matches '$2^{13}$ minus the small overcorrection'.
CCSS standards used (min grade 8)
3.OA.D.9Identify arithmetic patterns (including patterns in the addition table or multiplication table), and explain them using properties of operations (Trying the smallest case $n=2$ to feel the picking rule.)4.OA.C.5Generate a number or shape pattern that follows a given rule (Enumerating all $6$ permutations for $n=3$ and tallying two-pass cases.)7.SP.C.8Find probabilities of compound events using organized lists, tables, tree diagrams, and simulation (Counting orderings by choosing a subset of positions for the 'low' cards — one ordering per subset.)8.EE.A.1Know and apply the properties of integer exponents to generate equivalent numerical expressions (Evaluating $2^{13} = 8192$ and subtracting the $14$ over-counted sorted-ordering cases.)
⭐ This AMC 10 problem only needs Grade 8 powers of $2$ you already know — try $n=2$ and $n=3$ by hand, spot the pattern $2^n - n - 1$, then plug in $n = 13$ to get $8192 - 14 = 8178$.
⭐ This AMC 10 problem only needs Grade 8 powers of $2$ you already know — try $n=2$ and $n=3$ by hand, spot the pattern $2^n - n - 1$, then plug in $n = 13$ to get $8192 - 14 = 8178$.