2021 AMC 10B Problem 24

Problem 24 of 25HarderCounting & Probability

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

(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?

Show solution

Solution

For a single wall of length

n,

compute its Sprague-Grundy value from the possible moves. For the wall lengths needed here, the values are

\begin{aligned} &g(1)=1,\quad g(2)=2, \\ &g(3)=3,\quad g(4)=1, \\ &g(5)=4,\quad g(6)=3. \end{aligned}

For several walls, the position is losing for the player to move exactly when the xor of the wall values is

0.

Evaluating the choices gives

(6,1,1): 3\oplus1\oplus1=3,

(6,2,1): 3\oplus2\oplus1=0,

(6,2,2): 3\oplus2\oplus2=3,

(6,3,1): 3\oplus3\oplus1=1,

(6,3,2): 3\oplus3\oplus2=2.

Only

(6,2,1)

is losing for the player to move, so Beth has a guaranteed win exactly for that starting configuration. Thus, the answer is B .

Answer choices

Solution

More practice