AMC 10 · 2021 · #22
Grade 7 logic
Pick an answer.
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.
Value the smallest rows
Start assigning values from the empty row.
Build up Grundy values from the smallest walls — each new Grundy = smallest non-negative integer NOT in the set of options.
7.NS.A.3Solve An Easier Related ProblemA row of three
Take the smallest number not reachable.
Removing the middle brick of 3 gives two separated single bricks — their Grundy XOR is 0.
7.NS.A.3Make A Systematic ListA row of four
The value can drop back down.
The mex jumps DOWN at n = 4 because {0, 2, 3} skips 1.
7.NS.A.3Make A Systematic ListA row of five
Continue the same way.
Single brick from the middle splits 5 into (2, 2) — Grundy 0, a strong defensive option for the mover.
7.NS.A.3Make A Systematic ListA row of six
Compute the last value needed.
Grundy of 6 is 3 — note the mex skips over 3 in the option-set because {0, 1, 2, 4} misses it.
7.NS.A.3Make A Systematic ListCombine for each choice
Combine each choice by exclusive sum.
Independent walls XOR — like independent Nim heaps.
The walls do not interact, so their separate values combine into one value for the whole position.
▸ Why?
A move touches exactly one wall, so the possible moves are the walls' move lists put side by side.
▸ Why?
Combining independent games turns on whether each bit of the tally is matched or unmatched.
Pick the zero
The zero one is six, two, one.
Grundy 0 = the mover is stuck — every move creates a position the opponent can exploit.
7.NS.A.3Eliminate PossibilitiesThis hard AMC 12 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).