AMC 10 · 2009 · #21

Grade 7 counting

Archetype Branching State Enumeration └ Sub-archetype Constrained Sequence or Path Count

recursive-sequencepattern-recognitionpermutations-basic easier-related-problemcasework ↑ Prerequisites: recursive-sequencepermutations-basic

📏 Long solution 💡 3 insights

Problem

Ten people in a row all sit down again, each in their old seat or one directly beside it. Count the possible seatings.

Pick an answer.

(A)

(B)

(C)

120

(D)

$2^{10}$

(E)

$2^2 3^8$

How to solve

Strategy Solve an Easier Related Problem

The rule that makes this hard is the collision rule, and the way to get a grip on it is to look at the end of the row, where the fewest people can reach the seat in question. Tool #14 picks that spot. There the whole problem splits into exactly two cases, and each case uses up a block of seats and leaves the identical puzzle on a shorter row — that is tool #9, and it is the engine of the whole solution. Tool #4 supplies the name S_n so the two cases can be written as one equation instead of described in words. Tool #2 does two separate jobs: it produces the short list of people who could occupy the end seat, and it checks the small rows by hand so the rule is verified rather than guessed. Tool #5 carries the rule up to ten seats. Tool #3 closes the problem by showing what each wrong choice is a record of, and by killing the two large choices with a bound that needs no arithmetic.

1STEP 1

Model it as a matching

The rule is that everyone moves at most one seat.

|σ(k) - k| ≤ 1 for all k, σ one-to-one; 2 · 3⁸ · 2 = 2² 3⁸ = 26244

2STEP 2

Ask who takes the end seat

The end seat can only go to two people.

σ(k) = 1 → k ∈ {1, 2}

3STEP 3

Only stays and swaps can happen

Following that along, only stays and swaps happen.

{legal reseatings} ⟷ {ways to cut a row of 10 into pieces of length 1 and 2}

4STEP 4

Turn the split into a rule

That is a way of cutting the row into short pieces.

S_n = S_n-1 + S_n-2 (n ≥ 3), S₁ = 1, S₂ = 2

5STEP 5

Run the rule up to ten

Splitting on the last piece gives a simple recursion.

S₃ = 3, S₄ = 5, S₅ = 8, S₆ = 13, S₇ = 21, S₈ = 34, S₉ = 55, S₁₀ = 89

6STEP 6

Read the wrong choices

Running it up gives 89, choice (A).

S₁₀ = 89 ＜ 2⁹ = 512 ＜ 2¹⁰ = 1024 ＜ 2² 3⁸ = 26244 → (A)

Answer

Three checks, each catching a different kind of failure. First, the rule was tested where full listing is still possible: rows of 1, 2, 3, 4 women give 1, 2, 3, 5 by hand, which is exactly what S_n = S_n-1 + S_n-2 predicts. That matters because the rule was derived first and the table only confirms it — reading 1, 2, 3, 5, 8 off small cases and assuming it continues would prove nothing about ten women. Second, both directions of the key correspondence were established, not just the convenient one. Showing that every legal seating must be stays and neighbouring swaps is only half; the other half is that every arrangement of stays and neighbouring swaps really is a legal seating, filling all ten seats with nobody moving more than one place. Without the second half the sum could be an overcount, and without the first half it could miss seatings such as a long rotation — which is precisely the possibility the end-seat argument rules out. Third, size: with 9 neighbouring pairs and no two of them allowed to overlap, the answer must be far below 2⁹ = 512 but well above 10, and 89 sits comfortably in that window.

💡Key takeaway

Ask only about the seat at the end of the row: the woman there either stayed or traded with her one neighbour, and either answer leaves the very same puzzle on a shorter row, so the counts grow as 1, 2, 3, 5, 8, … and the tenth one is 89.

Model it as a matching
Ask who takes the end seat
Only stays and swaps can happen
Turn the split into a rule
Run the rule up to ten
Read the wrong choices