2021 AMC 10B Problem 24

P21-25~10 minPrint

Games & Processes Define states/recurrence and iterate Exploit symmetry to reduce work or pair up objects

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?

Show solution without answering

Key insight

If the walls come in identical pairs, the second player wins by copying each move on the twin wall. In every wrong choice, Arjun can make such pairs at once.

Solution

Step 1: a winning idea, the copycat strategy.

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.
So the copying player always has a move, and the other player eventually runs out. The copier takes the last brick and wins.
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)}$ .

Why this works

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

Alternative approach

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

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

wall	positions you can reach	their numbers	game number
$1$	nothing left	$0$	$1$
$2$	$(1)$ , nothing	$1, 0$	$2$
$3$	$(2), (1,1), (1)$	$2, 0, 1$	$3$
$4$	$(3), (1,2), (2), (1,1)$	$3, 3, 2, 0$	$1$
$5$	$(4), (1,3), (2,2), (3), (1,2)$	$1, 2, 0, 3, 3$	$4$
$6$	$(5), (1,4), (2,3), (4), (1,3), (2,2)$	$4, 0, 1, 1, 2, 0$	$3$

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

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

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:

$k$	reachable positions	their values	$g(k)$
1	$()$	$0$	$1$
2	$(1), ()$	$1, 0$	$2$
3	$(2), (1,1), (1)$	$2, 0, 1$	$3$
4	$(3), (1,2), (2), (1,1)$	$3, 3, 2, 0$	$1$
5	$(4), (1,3), (2,2), (3), (1,2)$	$1, 2, 0, 3, 3$	$4$
6	$(5), (1,4), (2,3), (4), (1,3), (2,2)$	$4, 0, 1, 1, 2, 0$	$3$

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

Review in the AoPS books

Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Intermediate Counting & Probability, Chapter 10: Recursion
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.4)