AMC 10 · 2012 · #22

Grade 7 counting
Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count
pattern-recognitioncombinations-basic easier-related-problem ↑ Prerequisites: pattern-recognition
📏 Medium solution 💡 3 insights
Problem
You list the numbers 1 through 10 in some order, each exactly once. 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.

Pick an answer.

(A)
$\ 120$
(B)
512
(C)
$\ 1024$
(D)
181,440
(E)
$\ 362,880$

AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Change Focus / Count the Complement

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⁹, and matching the value to the options (tool #3) picks the choice.

1STEP 1

Test tiny versions first

Count small n by hand: n = 2 gives 2 lists, n = 3 gives 4, n = 4 gives 8 — the count doubles each time.

f(2) = 2, f(3) = 4, f(4) = 8 → f(n) = 2^ n-1 ?
2STEP 2

See the numbers as a segment

Plot the written values as dots: each new one must touch the group, so they always form one unbroken block that grows only at an end.

[L, R] ⟶ [L-1, R] or [L, R+1]
3STEP 3

Turn a list into moves

So a list is just 9 left/right moves: k lefts force the start to be k + 1, so moves and lists match one-to-one.

valid list ⟷ a string of 9 moves in {L, R}, start = (#L) + 1
4STEP 4

Count the move strings

Each of the 9 positions is L or R independently, so the multiplication principle gives 2⁹ move strings.

2 × 2 × … × 2₉ factors = 2⁹
5STEP 5

Evaluate and pick the choice

2⁹ = 512, the only listed choice — 120, 1024, 181,440 and 362,880 are all ruled out, so the answer is (B).

2⁹ = 512 → (B)
Answer
512
The small cases match: 2²⁻¹ = 2, 2³⁻¹ = 4, 2⁴⁻¹ = 8 agreed with the hand counts, so 2¹⁰⁻¹ = 512 fits the same rule. A second sanity check: summing over the forced start value gives Σ_k=0⁹ C(9, k) = 2⁹ (choose which of the 9 moves are lefts), the same 512. The distractors are traps: 1024 = 2¹⁰ 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.
💡Key takeaway

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⁹ = 512.

  • Test tiny versions first
  • See the numbers as a segment
  • Turn a list into moves
  • Count the move strings
  • Evaluate and pick the choice

More like this

Same archetype — closest grade level first.