AMC 10 · 2021 · #24

Grade 7 arithmetic

Archetype Branching State Enumeration └ Sub-archetype Rule-Governed Process Simulation

sprague-grundy-theoremnim-gamerecursive-sequencepattern-recognition easier-related-problempattern-recognitionsystematic-enumeration ↑ Prerequisites: pattern-recognition

📏 Long solution 💡 4 insights 📊 Diagram

Problem

Arjun and Beth play a take-away game on a row of "walls" (groups of contiguous bricks). On each turn a player picks ONE wall and removes either a single brick from it OR two adjacent bricks; gaps split the wall into smaller walls. Arjun moves first; the player who takes the last brick wins. Find the starting configuration (among five choices, each consisting of three walls) for which Beth (the second player) has a winning strategy.

Pick an answer.

(A)

(6,1,1)

(B)

(6,2,1)

(C)

(6,2,2)

(D)

(6,3,1)

(E)

(6,3,2)

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

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Problem) — start with single walls of size 1, 2, 3, …, 6. Their Grundy numbers solve the whole problem because each candidate splits into independent sub-walls. Tool #2 (Systematic List) — for each n, list every possible move's resulting Grundy number and apply mex (minimum excludant). Tool #5 (Pattern) — Grundy numbers grow nicely as n increases. Tool #7 (Subproblems) — three-wall positions decompose into XOR of single-wall Grundy numbers (Sprague-Grundy theorem). Tool #3 (Eliminate) — XOR each candidate and pick the one equal to 0. We need this theorem from above grade 8, but the small-case mex calculations are bare arithmetic and pattern-spotting.

1STEP 1

Smallest walls by mex of one-move options: G(0)=0, G(1)=1, and G(2)=2.

G(0) = 0, G(1) = 1, G(2) = 2

2STEP 2

Size 3: removing the middle brick gives (1,1) with XOR 0, so options {0,1,2} and G(3)=3.

G(3) = mex{0, 1, 2} = 3

3STEP 3

Size 4: the options {0,2,3} skip 1, so the mex drops — G(4)=1.

G(4) = mex{0, 2, 3} = 1

4STEP 4

Size 5: the middle removal splits into (2,2) with XOR 0; options {0,1,2,3} give G(5)=4.

G(5) = mex{0, 1, 2, 3} = 4

5STEP 5

Size 6: the options {0,1,2,4} miss 3, so the key wall value is G(6)=3.

G(6) = mex{0, 1, 2, 4} = 3

6STEP 6

Apply the Sprague-Grundy XOR rule to each choice's three walls: A=3, B=0, C=3, D=1, E=2.

G(A) = 3, G(B) = 0, G(C) = 3, G(D) = 1, G(E) = 2

7STEP 7

The unique P-position has nim-value 0 — choice B; every Arjun move breaks it and Beth restores XOR 0 to win.

G(B) = 0 → (B) (6, 2, 1)

Answer

(6,2,1)

Sanity. We can cross-check (B) by the symmetry-mirror strategy mentioned in published solutions: from (6, 2, 1), Arjun's 11 possible moves include shrinking the 6 to (3, 3, 2, 1) — but Beth would rather split into a symmetric pair. More concretely: Arjun must move on the 6-wall, the 2-wall, or the 1-wall, and a careful case analysis shows every move leaves a non-zero-XOR position. The Grundy-value table G(1..6) = (1, 2, 3, 1, 4, 3) matches the Sprague-Grundy values referenced in AoPS Solution 3 for this problem. None of the other four candidates XOR to 0, so they're all wins for Arjun.

💡Key takeaway

This hard AMC 10 game-theory problem boils down to a Grade 7 small-case search you already know — compute the Grundy number (mex of next-move Grundy values) for single walls of size 1 through 6, getting 1, 2, 3, 1, 4, 3. The position (6, 2, 1) has XOR 3 ⊕ 2 ⊕ 1 = 0, meaning the first player (Arjun) has no good move — every move leaves a non-zero XOR Beth can answer perfectly. So the answer is (B) (6, 2, 1).

More like this