AMC 10 · 2021 · #24

Grade 7 arithmetic

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 game in which they take turns removing one brick or two adjacent bricks from one "wall" among a set of several walls of bricks, with gaps possibly creating new walls. The walls are one brick tall. For example, a set of walls of sizes $4$ and $2$ can be changed into any of the following by one move: $(3,2),(2,1,2),(4),(4,1),(2,2),$ or $(1,1,2).$

Arjun plays first, and the player who removes the last brick wins. For which starting configuration is there a strategy that guarantees a win for Beth?

$\textbf{(A) }(6,1,1) \qquad \textbf{(B) }(6,2,1) \qquad \textbf{(C) }(6,2,2)\qquad \textbf{(D) }(6,3,1) \qquad \textbf{(E) }(6,3,2)$

Pick an answer.

(A)

(6,1,1)

(B)

(6,2,1)

(C)

(6,2,2)

(D)

(6,3,1)

(E)

(6,3,2)

View mode:

Toolkit + CCSS Solution

Understand

Restated: 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.

Givens: Two players, Arjun first, alternating turns; On each turn: pick one wall and remove either $1$ brick or $2$ adjacent bricks from it; Removing creates gaps which split the wall into new (smaller) walls; Last brick taken wins; Five candidate starting configurations of three walls each: (A) $(6,1,1)$, (B) $(6,2,1)$, (C) $(6,2,2)$, (D) $(6,3,1)$, (E) $(6,3,2)$

Unknowns: Which starting configuration is a P-position (loss for the player to move = win for Beth)

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #2 Make a Systematic List, #7 Identify Subproblems, #3 Eliminate Possibilities

Tool #9 (Easier Problem) — start with single walls of size $1, 2, 3, \ldots, 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.

Execute — Answer: B

#9 Solve an Easier Related Problem 7.NS.A.3 Step 1

Grundy values for empty wall and tiny walls.
$G(0) = 0$ (no moves; previous player just won).
For wall size $1$: only move removes the one brick, leading to empty (Grundy $0$).
So options-set is $\{0\}$, and $G(1) = \text{mex}\{0\} = 1$.
For wall size $2$: remove $1$ brick $\to$ wall size $1$ (Grundy $1$); remove $2$ adjacent bricks $\to$ empty (Grundy $0$).
Options $\{0, 1\}$, $G(2) = \text{mex}\{0, 1\} = 2$.

$$G(0) = 0,\; G(1) = 1,\; G(2) = 2$$

💡 Build up Grundy values from the smallest walls — each new Grundy = smallest non-negative integer NOT in the set of options.

#2 Make a Systematic List 7.NS.A.3 Step 2

Wall size $3$.
Moves: remove brick at position $1$ $\to$ wall $(2)$, Grundy $2$; position $2$ (middle) $\to (1, 1)$ with Grundy $1 \oplus 1 = 0$; position $3$ $\to (2)$, Grundy $2$; remove $2$ adjacent positions $1$-$2$ $\to (1)$, Grundy $1$; positions $2$-$3$ $\to (1)$, Grundy $1$.
Distinct options: $\{0, 1, 2\}$.
$G(3) = \text{mex}\{0, 1, 2\} = 3$.

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

💡 Removing the middle brick of $3$ gives two separated single bricks — their Grundy XOR is $0$.

#2 Make a Systematic List 7.NS.A.3 Step 3

Wall size $4$.
Moves: remove $1$ brick at position $1$ or $4$ $\to (3)$ Grundy $3$; at position $2$ $\to (1, 2)$ Grundy $1 \oplus 2 = 3$; at position $3$ $\to (2, 1)$ Grundy $2 \oplus 1 = 3$; remove $2$ adjacent at positions $1$-$2$ or $3$-$4$ $\to (2)$ Grundy $2$; positions $2$-$3$ $\to (1, 1)$ Grundy $1 \oplus 1 = 0$.
Distinct: $\{0, 2, 3\}$.
$G(4) = \text{mex}\{0, 2, 3\} = 1$.

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

💡 The mex jumps DOWN at $n = 4$ because $\{0, 2, 3\}$ skips $1$.

#2 Make a Systematic List 7.NS.A.3 Step 4

Wall size $5$.
Moves to states $(4)$ G $1$; $(1, 3)$ G $1 \oplus 3 = 2$; $(2, 2)$ G $2 \oplus 2 = 0$; $(3, 1)$ G $2$; $(4)$ G $1$ (mirror); $(3)$ G $3$; $(1, 2)$ G $3$; $(2, 1)$ G $3$; $(3)$ G $3$.
Distinct: $\{0, 1, 2, 3\}$.
$G(5) = \text{mex}\{0, 1, 2, 3\} = 4$.

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

💡 Single brick from the middle splits $5$ into $(2, 2)$ — Grundy $0$, a strong defensive option for the mover.

#2 Make a Systematic List 7.NS.A.3 Step 5

Wall size $6$.
Moves to states (with $G$): remove $1$ at end positions $1, 6$ $\to (5)$ G $4$; at position $2$ or $5$ $\to (1, 4)$ G $1 \oplus 1 = 0$; at position $3$ or $4$ $\to (2, 3)$ G $2 \oplus 3 = 1$; remove $2$ adjacent at $1$-$2$ or $5$-$6$ $\to (4)$ G $1$; at $2$-$3$ or $4$-$5$ $\to (1, 3)$ or $(3, 1)$ G $1 \oplus 3 = 2$; at $3$-$4$ $\to (2, 2)$ G $0$.
Distinct options: $\{0, 1, 2, 4\}$.
$G(6) = \text{mex}\{0, 1, 2, 4\} = 3$.

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

💡 Grundy of $6$ is $3$ — note the mex skips over $3$ in the option-set because $\{0, 1, 2, 4\}$ misses it.

#7 Identify Subproblems 7.NS.A.3 Step 6

Apply Sprague-Grundy XOR rule to each answer choice (three independent walls in each): $G(\text{position}) = G(w_1) \oplus G(w_2) \oplus G(w_3)$.
(A) $(6, 1, 1)$: $G = 3 \oplus 1 \oplus 1 = 3$.
(B) $(6, 2, 1)$: $G = 3 \oplus 2 \oplus 1 = 0$.
(C) $(6, 2, 2)$: $G = 3 \oplus 2 \oplus 2 = 3$.
(D) $(6, 3, 1)$: $G = 3 \oplus 3 \oplus 1 = 1$.
(E) $(6, 3, 2)$: $G = 3 \oplus 3 \oplus 2 = 2$.

$$G(\text{A}) = 3,\; G(\text{B}) = 0,\; G(\text{C}) = 3,\; G(\text{D}) = 1,\; G(\text{E}) = 2$$

💡 Independent walls XOR — like independent Nim heaps.

#3 Eliminate Possibilities 7.NS.A.3 Step 7

A P-position (loss for the player to move) has nim-value $0$.
The only choice with $G = 0$ is (B) $(6, 2, 1)$.
So if Arjun starts at $(6, 2, 1)$, every move he makes leaves a non-zero Grundy position, from which Beth can XOR back to $0$ on her reply.
Beth wins.

$$G(\text{B}) = 0 \Rightarrow \textbf{(B)} \;(6, 2, 1)$$

💡 Grundy $0$ = the mover is stuck — every move creates a position the opponent can exploit.

[1] #9 7.NS.A.3 Grundy values for empty wall and tiny walls. $G(0) = 0$ (no moves; previous play

[2] #2 7.NS.A.3 Wall size $3$. Moves: remove brick at position $1$ $\to$ wall $(2)$, Grundy $2$;

[3] #2 7.NS.A.3 Wall size $4$. Moves: remove $1$ brick at position $1$ or $4$ $\to (3)$ Grundy $

[4] #2 7.NS.A.3 Wall size $5$. Moves to states $(4)$ G $1$; $(1, 3)$ G $1 \oplus 3 = 2$; $(2, 2)

[5] #2 7.NS.A.3 Wall size $6$. Moves to states (with $G$): remove $1$ at end positions $1, 6$ $\

[6] #7 7.NS.A.3 Apply Sprague-Grundy XOR rule to each answer choice (three independent walls in

[7] #3 7.NS.A.3 A P-position (loss for the player to move) has nim-value $0$. The only choice wi

Review

Reasonableness: 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.

Alternative: Tool #5 (Pattern + small cases) without the heavy Sprague-Grundy machinery: directly verify that $(6, 2, 1)$ is a P-position by symmetry pairing. From any move by Arjun on $(6, 2, 1)$, Beth can find a counter-move that leaves a perfectly symmetric configuration (e.g., $(3, 3, x, x)$-style mirrors). After that, Beth mirrors every Arjun move forever, guaranteeing she takes the last brick. The published Solution 1 / Solution 4 use exactly this paired-mirror argument for the easier eliminations.

CCSS standards used (min grade 7)

7.NS.A.3 Solve real-world problems involving the four operations with rational numbers (Computing mex (minimum non-negative integer missing from a set), XOR of small non-negative integers via base-$2$ bit comparison, and the recursive Grundy-value bookkeeping for walls of size $1$ through $6$.)

⭐ 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 \oplus 2 \oplus 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)$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: B

Review

CCSS standards used (min grade 7)

More like this