Question

Arjun y Beth juegan un juego en el que se turnan para quitar un ladrillo o dos ladrillos adyacentes de un "muro" entre un conjunto de varios muros de ladrillos, y los huecos pueden crear nuevos muros. Los muros tienen un ladrillo de alto. Por ejemplo, un conjunto de muros de tamaños $4$ y $2$ puede transformarse en cualquiera de los siguientes con un movimiento: $(3,2),$ $\ (2,1,2),$ $\ (4),$ $\ (4,1),$ $\ (2,2),$ o $(1,1,2).$

Arjun juega primero, y el jugador que quita el último ladrillo gana. ¿Para cuál configuración inicial existe una estrategia que garantiza la victoria de Beth?

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

Solución:

Trata cada muro como un montón tipo Nim con un valor de Grundy. Un movimiento quita $1$ o $2$ ladrillos adyacentes, posiblemente dividiendo un muro en dos, así que $g(n)=\operatorname{mex}$ sobre todos los valores XOR resultantes.

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

La segunda jugadora Beth gana exactamente cuando el XOR de los valores de Grundy de los muros es $0.$ Revisando cada opción, solo $(6,2,1)$ da $g(6)\oplus g(2)\oplus g(1)$ $=3\oplus 2\oplus 1=0.$

Por lo tanto, la respuesta correcta es B.

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 Problema 22

Solución:

El Problema 22 en otros años