AMC 10 · 2012 · #22
Grade 7 countingLet (a1, a2, ... a10) be a list of the first 10 positive integers such that for each 2≤ i ≤10 either ai+1 or ai−1 or both appear somewhere before ai in the list. How many such lists are there?
Pick an answer.
AMC 10 2012 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: You list the numbers $1$ through $10$ in some order. The rule: from the second number onward, every number you write must already have a neighbor — a value exactly $1$ larger or $1$ smaller — somewhere earlier in the list. Count how many different orderings obey this rule.
Givens: The list is an ordering (permutation) of the first $10$ positive integers $1, 2, \dots, 10$.; For each position $i$ with $2 \le i \le 10$, at least one of $a_i - 1$ or $a_i + 1$ appears somewhere before position $i$.; The first number $a_1$ carries no restriction.; Answer choices: (A) $120$, (B) $512$, (C) $1024$, (D) $181{,}440$, (E) $362{,}880$.
Unknowns: The number of valid lists (orderings) of $1$ through $10$.
Understand
Restated: You list the numbers $1$ through $10$ in some order. The rule: from the second number onward, every number you write must already have a neighbor — a value exactly $1$ larger or $1$ smaller — somewhere earlier in the list. Count how many different orderings obey this rule.
Givens: The list is an ordering (permutation) of the first $10$ positive integers $1, 2, \dots, 10$.; For each position $i$ with $2 \le i \le 10$, at least one of $a_i - 1$ or $a_i + 1$ appears somewhere before position $i$.; The first number $a_1$ carries no restriction.; Answer choices: (A) $120$, (B) $512$, (C) $1024$, (D) $181{,}440$, (E) $362{,}880$.
Plan
Primary tool: #16 Change Focus / Count the Complement
Secondary: #9 Solve an Easier Related Problem, #1 Draw a Diagram, #2 Make a Systematic List, #3 Eliminate Possibilities
Counting the $10$-long lists head-on is hopeless, so we change what we count (tool #16). First shrink the problem (tool #9): for $n = 2, 3, 4$ the counts are $2, 4, 8$, hinting at $2^{\,n-1}$. A number-line picture (tool #1) reveals the key structure — the values written so far always form one unbroken block that can only grow at its left or right end. That lets us re-describe each list as a string of $9$ left/right moves, with the starting number forced by the requirement that the block end as $[1, 10]$. Counting those strings is a plain multiplication-principle list (tool #2), giving $2^9$, and matching the value to the options (tool #3) picks the choice.
Execute — Answer: B
4.OA.C.5 Step 1 Test tiny versions first
- Replace $10$ with a small $n$ and count by hand.
- For $n = 2$: both $(1,2)$ and $(2,1)$ work, so $2$ lists.
- For $n = 3$: the valid lists are $(1,2,3),\ (2,1,3),\ (2,3,1),\ (3,2,1)$, so $4$ lists.
- A careful count for $n = 4$ gives $8$.
- The counts $2, 4, 8$ double each time, suggesting $2^{\,n-1}$ valid lists for length $n$.
💡 Shrinking the list makes the hidden doubling visible before we try to prove it.
6.NS.C.6 Step 2 See the numbers as a segment
- Picture the values already written as dots on a number line.
- The first number is a single dot.
- Every later number must sit next to a dot that is already there, so it can only attach at the left end or the right end of the current group.
- Therefore the written numbers always form one unbroken block of consecutive integers $[L, R]$ — never a gap.
- Adding a number turns $[L, R]$ into either $[L-1, R]$ or $[L, R+1]$.
💡 A new value differs by $1$ from an old one, so the covered numbers stay glued into a single stretch.
7.SP.C.8 Step 3 Turn a list into moves
- Because the block grows by exactly one step each time — left ($L$) or right ($R$) — a whole list is just its starting value followed by $9$ moves, each an $L$ or an $R$.
- But the start is not free: after all $9$ moves the block must be the full $[1, 10]$.
- If the moves contain $k$ lefts and $9 - k$ rights, the block ends at $[\text{start} - k,\ \text{start} + (9 - k)] = [1, 10]$, which forces $\text{start} = k + 1$.
- So every string of $9$ moves gives exactly one valid list, and every valid list gives exactly one string — a perfect one-to-one match.
💡 Stop counting orderings; count the left/right decisions instead — the starting number takes care of itself.
7.SP.C.8 Step 4 Count the move strings
- Now the question is only: how many strings of length $9$ use the two letters $L$ and $R$?
- Each of the $9$ positions is filled independently with one of $2$ choices, so by the multiplication principle the total is $2 \times 2 \times \dots \times 2$ with nine factors.
💡 Nine independent two-way forks multiply into $2^9$ outcomes.
6.EE.A.1 Step 5 Evaluate and pick the choice
- Evaluate $2^9 = 512$.
- Among the answer choices only $512$ appears, so the others — $120$, $1024$, $181{,}440$, $362{,}880$ — are all ruled out.
- There are $512$ valid lists, which is choice $\textbf{(B)}$.
💡 The clean power of two, $2^9$, lands exactly on one listed choice.
4.OA.C.5 Replace $10$ with a small $n$ and count by hand. For $n = 2$: both $(1,2)$ and $ 6.NS.C.6 Picture the values already written as dots on a number line. The first number is 7.SP.C.8 Because the block grows by exactly one step each time — left ($L$) or right ($R$ 7.SP.C.8 Now the question is only: how many strings of length $9$ use the two letters $L$ 6.EE.A.1 Evaluate $2^9 = 512$. Among the answer choices only $512$ appears, so the others Review
Reasonableness: The small cases match: $2^{2-1} = 2$, $2^{3-1} = 4$, $2^{4-1} = 8$ agreed with the hand counts, so $2^{10-1} = 512$ fits the same rule. A second sanity check: summing over the forced start value gives $\sum_{k=0}^{9} \binom{9}{k} = 2^9$ (choose which of the $9$ moves are lefts), the same $512$. The distractors are traps: $1024 = 2^{10}$ over-counts by treating the start as an extra free choice, while $362{,}880 = 9!$ and $181{,}440 = 9!/2$ imagine far more freedom than the neighbor rule allows.
Alternative: Recursion (tool #9 again). In any valid list of $\{1, \dots, n\}$ the last number written must be $1$ or $n$, because the final block is $[1, n]$ and only an end can be added last. Deleting it leaves a valid list of a size-$(n-1)$ set, and conversely each shorter list extends in exactly $2$ ways (attach the new smallest or the new largest). So $f(n) = 2\,f(n-1)$ with $f(1) = 1$, giving $f(10) = 2^9 = 512$ directly.
CCSS standards used (min grade 7)
4.OA.C.5Generate a number or shape pattern following a given rule (Counting the tiny cases $n = 2, 3, 4$ to $2, 4, 8$ and spotting the doubling pattern $2^{\,n-1}$.)6.NS.C.6Understand a rational number as a point on the number line (Picturing the written values as dots on a number line to see they always form one unbroken block $[L, R]$ that can grow only at an end.)7.SP.C.8Find probabilities of compound events using organized lists, tables, and simulation (Reframing each list as a string of $9$ independent left/right moves and applying the multiplication principle to get $2^9$.)6.EE.A.1Write and evaluate numerical expressions involving whole-number exponents (Evaluating $2^9 = 512$ to identify choice (B).)
⭐ When a rule only ever lets you add to the left end or the right end of a block, forget the numbers and just count the left/right choices — here that turns a scary ordering problem into $2^9 = 512$.
⭐ When a rule only ever lets you add to the left end or the right end of a block, forget the numbers and just count the left/right choices — here that turns a scary ordering problem into $2^9 = 512$.
More like this
Same archetype — closest grade level first.