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),$ 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)$

Answer: B

Concepts:combinatorial game invariant

Difficulty rating: 2390

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 lengths $a,b.$ Thus $g(n)$ is the mex of $g(a)\oplus g(b)$ over $a+b=n-1$ or $a+b=n-2.$

Starting with $g(0)=0,$ this recurrence gives $g(1),g(2),\ldots,g(6)$ equal to $1,2,3,1,4,3,$ respectively.

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

Answer: B

Difficulty rating: 2390

Solution:

Problem 22 in Other Years