AMC 10 · 2022 · #22

Grade 8 arithmetic

combinations-basiccomplementary-countingpattern-recognition easier-related-problemcomplementary-countingpattern-recognition ↑ Prerequisites: combinations-basic

📏 Medium solution 💡 3 insights 📊 Diagram

Problem

Suppose that $13$ cards numbered $1, 2, 3, \ldots, 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?

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

Pick an answer.

(A)

4082

(B)

4095

(C)

4096

(D)

8178

(E)

8191

View mode:

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

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

#9 Solve an Easier Related Problem 3.OA.D.9 Step 1

Try $n = 2$.
The two orderings are $12$ (one pass) and $21$ (two passes).
Two-pass count $= 1$.

$$n=2: \text{two-pass} = 1 = 2^2 - 2 - 1$$

💡 Grade 3 — try a tiny case to feel out the rule.

#2 Make a Systematic List 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$.

$$n=3: \text{two-pass} = 4 = 2^3 - 3 - 1$$

💡 Grade 4 — enumerate by rule and tally; pattern $2^n - n - 1$ shows up after just two data points.

#16 Change Focus / Count the Complement 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$'.

$$\text{at most 2 passes} \Leftrightarrow \text{both prefixes increasing in position}$$

💡 Grade 7 — recast the picking process as a structural property of the permutation.

#2 Make a Systematic List 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$.

$$\#\{\le 2 \text{ passes}\} = 2^{13} = 8192$$

💡 Grade 7 — each subset of positions for the low cards gives exactly one valid ordering.

#5 Look for a Pattern 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).

$$(2^{13} - 14) + 1 - 1 = 8192 - 14 = 8178 \;\Rightarrow\; \textbf{(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.

[1] #9 3.OA.D.9 Try $n = 2$. The two orderings are $12$ (one pass) and $21$ (two passes). Two-pa

[2] #2 4.OA.C.5 Try $n = 3$. List all $6$ orderings and simulate. $123$: one pass. $132$: pass 1

[3] #16 7.SP.C.8 Generalize. In any ordering, pass 1 collects exactly the cards ${1, 2, \ldots,

[4] #2 7.SP.C.8 Count 'at most 2 passes' for $n = 13$. Pick the subset $A \subseteq {1, \ldots,

[5] #5 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.9 Identify 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.5 Generate 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.8 Find 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.1 Know 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$.