2021 AMC 12B Spring Problema 22

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.