AMC 10 · 2015 · #22

Grade 9 counting

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

permutations-basicrecursive-sequencemodular-arithmetic easier-related-problemsystematic-enumeration ↑ Prerequisites: permutations-basicrecursive-sequence

📏 Long solution 💡 4 insights

Problem

Everyone reseats around a circle and nobody may take their own chair or either neighbour's. Count the seatings.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

How to solve

Strategy Solve an Easier Related Problem

Tool #4 (Introduce a Variable) numbers the chairs 0 through 5 and measures each person's move by its clockwise shift, which turns the two written rules into one short list of legal shifts: 2, 3, or 4. Those three numbers are each exactly 3 away from -1, 0, 1, so Tool #15 (Organize Information in More Ways) rotates every landing chair back by three places; because that rotation is reversible it pairs the hard seatings one-to-one with seatings where everybody either stays put or steps to a neighbouring chair. Tool #9 (Solve an Easier Related Problem) then handles the easy rule in a straight row before a circle, where the leftmost person has only two futures and each future hands back a shorter row — that is the recurrence F_n = F_n-1 + F_n-2, and it is the load-bearing claim of the whole solution, so it is argued, not quoted. Tool #2 (Make a Systematic List) checks the short rows by writing every arrangement out, so the recurrence starts from verified numbers rather than a guessed pattern. Finally Tool #7 (Identify Subproblems) closes the circle by splitting on where one chosen person goes, which reduces each branch to a row that is already counted.

1STEP 1

Measure every move as a shift

Each move is measured as a shift.

d_i = σ(i) - i (mod 6), d_i ∈ {2, 3, 4}

2STEP 2

Rotate the landing chairs by three

Rotating turns the bans into a friendly range.

τ(i) = σ(i) - 3 (mod 6) ⟺ τ(i) - i ∈ {-1, 0, 1} (mod 6)

3STEP 3

Straighten the circle into a row

Straightening the circle gives a familiar recursion.

F_n = F_n-1 + F_n-2 (n ≥ 3)

4STEP 4

Check the short rows by listing

Short rows are checked by hand.

F₁ = 1, F₂ = 2, F₃ = 3, F₄ = 5, F₅ = 8

5STEP 5

Close the circle at person 0

Closing the circle splits it into three cases.

8 + 6 + 6

6STEP 6

Add up and rotate back

Adding gives 20, choice (D).

8 + 6 + 6 = 20 → (D) 20

Answer

Test the answer against the original rules, not the rotated ones. Take the easy arrangement where the pairs (0,1), (2,3), (4,5) each swap, add 3 to every landing chair, and person 0 goes to chair 4, person 1 to chair 3, person 2 to chair 0, person 3 to chair 5, person 4 to chair 2, person 5 to chair 1. The landing chairs 4, 3, 0, 5, 2, 1 are all different, and each person moved 2, 3, or 4 places, never 0 or 1 — legal. Size is also plausible: the three whole-table moves alone (everyone shifts 2, everyone shifts 3, everyone shifts 4) already give 3 seatings, while an upper bound that ignores the one-person-per-chair rule allows 3⁶ = 729, so a total of 20 sits sensibly between the two. Note that all five choices 14 through 24 are in that plausible band, so no shortcut by size can decide this; the case split has to be done. The three branches 8, 6, 6 are separated by where person 0 sits, so nothing is double counted, and the 8 and the 6 rest on F₅ and F₄, which were checked by hand.

💡Key takeaway

Rotate the finished picture until the hard rule turns into an easy one, straighten the circle into a row so the end person has only two futures, and prove the small cases by writing them out — then the count builds itself, step by step, up to 20.

Measure every move as a shift
Rotate the landing chairs by three
Straighten the circle into a row
Check the short rows by listing
Close the circle at person 0
Add up and rotate back