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

Respuesta: B

Conceptos:juego combinatorio invariante

Nivel de dificultad: 2390

Pista pequeña:

Calcula el valor de Grundy de un solo muro de longitud $n,$ donde un movimiento quita $1$ o $2$ ladrillos adyacentes y puede dividir el muro

Compute the Grundy value of a single wall of length $n,$ where a move removes $1$ or $2$ adjacent bricks and may split the wall

Pista grande:

Beth (la segunda jugadora) gana exactamente cuando el XOR de los valores de Grundy de los muros es $0$

Beth (the second player) wins exactly when the XOR of the walls’ Grundy values is $0$

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 longitudes $a,b.$ Así, $g(n)$ es el mex de $g(a)\oplus g(b)$ para todos los casos con $a+b=n-1$ o $a+b=n-2.$

Empezando con $g(0)=0,$ esta recurrencia da $g(1),g(2),\ldots,g(6)$ iguales a $1,2,3,1,4,3,$ respectivamente.

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

Respuesta: B

Nivel de dificultad: 2390

Pista pequeña:

Pista grande:

Solución:

El Problema 22 en otros años