2021 AMC 12B Problem 22
Problem 22 of 25HarderCounting & Probability
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 and can be changed into any of the following by one move: or
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?
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?Answer choices
Show solution
Solution
Treat each wall as a Nim-like heap with a Grundy value. A move removes or adjacent bricks, possibly splitting a wall into lengths Thus is the mex of over or
Starting with this recurrence gives equal to respectively.
The second player Beth wins exactly when the XOR of the walls’ Grundy values is Checking each option, only gives
Thus, the correct answer is B.