Question

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),\text{ 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?

$(6,1,1)$

$(6,2,1)$

$(6,2,2)$

$(6,3,1)$

$(6,3,2)$

Solution:

Treat each wall as a Nim-like heap with a Grundy value. A move removes $1$ or $2$ adjacent bricks, possibly splitting a wall into two, so $g(n)=\operatorname{mex}$ over all resulting XOR values.

Computing, $g(1)=1,$ $g(2)=2,$ $g(3)=3,$ $g(4)=1,$ $g(5)=4,$ $g(6)=3.$

The second player Beth wins exactly when the XOR of the walls' Grundy values is $0.$ Checking each option, only $(6,2,1)$ gives $g(6)\oplus g(2)\oplus g(1)=3\oplus 2\oplus 1=0.$

Thus, the correct answer is B.

2021 AMC 12B Spring Problem 22

Solution:

Problem 22 in Other Years