2021 AMC 10B Problem 24

Step 1: a winning idea, the copycat strategy.

1. Suppose the walls come in identical pairs, like $(2, 2)$ or $(3, 1, 3, 1)$. Then the player who moves second can always win: whatever the other player does to one wall, copy the same move on its twin. After each copy the walls are in identical pairs again.
2. So the copying player always has a move, and the other player eventually runs out. The copier takes the last brick and wins.
3. This means: if a player can move to "identical pairs," that player wins, by copying from then on.

Step 2: rule out four choices. In each of these, Arjun (moving first) can split the $6$-wall so that everything comes in identical pairs. Then Arjun copies Beth and wins.

• $(6, 1, 1)$: Arjun removes the two middle bricks of the $6$ (bricks $3$ and $4$), leaving $2$ and $2$. Walls: $(2, 2, 1, 1)$.
• $(6, 2, 2)$: the same move gives $(2, 2, 2, 2)$.
• $(6, 3, 1)$: Arjun removes bricks $2$ and $3$ of the $6$, leaving $1$ and $3$. Walls: $(1, 3, 3, 1)$.
• $(6, 3, 2)$: Arjun removes brick $3$ of the $6$, leaving $2$ and $3$. Walls: $(2, 3, 3, 2)$.

Step 3: conclude. Arjun wins in (A), (C), (D) and (E), so the configuration where Beth can guarantee a win is $(6, 2, 1)$.

The answer is $\boxed{\textbf{(B)}\ (6,2,1)}$.

In many two-player games, the player who can make the position symmetric wins by copying. Here a single move in the middle of the long wall can create the twin walls. The Alternative Approach below shows how to confirm directly that Beth really does win from $(6, 2, 1)$.

Give each wall a "game number" and combine them.

1. Game number of one wall. List every position you can move to from that wall, find their game numbers, and take the smallest whole number ($0, 1, 2, \ldots$) that is not in the list.
2. Several walls. Write each wall's game number in binary and add the columns without carrying (a column is $1$ if it has an odd number of $1$s). This is called XOR, written $\oplus$. For example, $3 \oplus 2 = 11_2 \oplus 10_2 = 01_2 = 1$.
3. The player about to move loses exactly when the combined number is $0$.

The table of game numbers (an empty position has game number $0$):

For $(6, 2, 1)$: $3 \oplus 2 \oplus 1 = 11_2 \oplus 10_2 \oplus 01_2 = 00_2 = 0$. So Arjun, who moves first, loses, and Beth wins. For the other four choices the combined number is not $0$.

This is a sum of independent games (the walls), so use nim-values. Assign each wall size $k$ a value $g(k)$: the smallest nonnegative integer not among the values of positions reachable from a single wall of $k$, where a multi-wall position's value is the XOR ($\oplus$) of its walls' values. The player to move loses exactly when the total XOR is $0$.

Compute, listing the positions reachable from one wall:

Beth, the second player, wins when the starting XOR is $0$:

• $(6,1,1)$: $3 \oplus 1 \oplus 1 = 3$.
• $(6,2,1)$: $3 \oplus 2 \oplus 1 = 0$. Beth wins.
• $(6,2,2)$: $3 \oplus 2 \oplus 2 = 3$.
• $(6,3,1)$: $3 \oplus 3 \oplus 1 = 1$.
• $(6,3,2)$: $3 \oplus 3 \oplus 2 = 2$.

Only $(6,2,1)$ is a losing position for the first player.

The answer is $\boxed{\textbf{(B)}\ (6,2,1)}$.