2021 AMC 12B Problems/Problem 22

Problem

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

$[asy] unitsize(4mm); real[] boxes = {0,1,2,3,5,6,13,14,15,17,18,21,22,24,26,27,30,31,32,33}; for(real i:boxes){ draw(box((i,0),(i+1,3))); } draw((8,1.5)--(12,1.5),Arrow()); defaultpen(fontsize(20pt)); label(",",(20,0)); label(",",(29,0)); label(",...",(35.5,0)); [/asy]$

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?

$\textbf{(A) }(6,1,1) \qquad \textbf{(B) }(6,2,1) \qquad \textbf{(C) }(6,2,2)\qquad \textbf{(D) }(6,3,1) \qquad \textbf{(E) }(6,3,2)$

Solution

First we note that symmetrical positions are losing for the player to move. Then we start checking small positions. $(n)$ is always winning for the first player. Furthermore, $(3, 2, 1)$ is losing and so is $(4, 1).$ We look at all the positions created from $(6, 2, 1),$ as $(6, 1, 1)$ is obviously winning by playing $(2, 2, 1, 1).$ There are several different positions that can be played by the first player from $(6, 2, 1).$ They are $(2, 2, 2, 1), (1, 3, 2, 1), (4, 2, 1), (6, 1), (5, 2, 1), (4, 1, 2, 1), (3, 2, 2, 1).$ Now we list refutations for each of these moves:

$(2, 2, 2, 1) - (2, 1, 2, 1)$

$(1, 3, 2, 1) - (3, 2, 1)$

$(4, 2, 1) - (4, 1)$

$(6, 1) - (4, 1)$

$(5, 2, 1) - (3, 2, 1)$

$(4, 1, 2, 1) - (2, 1, 2, 1)$

$(3, 2, 2, 1) - (1, 2, 2, 1)$

This proves that $(6, 2, 1)$ is losing for the first player.

-Note: In general, this game is very complicated. For example $(8, 7, 5, 3, 2)$ is winning for the first player but good luck showing that.

Solution 2 (Process of Elimination)

$(6,1,1)$ can be turned into $(2,2,1,1)$ by Arjun, which is symmetric, so Beth will lose.

$(6,3,1)$ can be turned into $(3,1,3,1)$ by Arjun, which is symmetric, so Beth will lose.

$(6,2,2)$ can be turned into $(2,2,2,2)$ by Arjun, which is symmetric, so Beth will lose.

$(6,3,2)$ can be turned into $(3,2,3,2)$ by Arjun, which is symmetric, so Beth will lose.

That leaves $(6,2,1)$ or $\boxed{\textbf{(B)}}$ .

Solution 3 (Nim-values)

Let the nim-value of the ending game state, where someone has just removed the final brick, be $0$ . Then, any game state with a nim-value of $0$ is losing. It is well-known that the nim-value of a supergame (a combination of two or more individual games) is the binary xor function on the nim-values of the individual games that compose the supergame. Therefore, we calculate the nim-values of the states with a single wall up to $6$ bricks long (since the answer choices only go up to $6$ ).

First, the game with $1$ brick has a nim-value of $1$ .

Similarly, the game with $2$ bricks has a nim-value of $2$ .

Next, we consider a $3$ brick wall. After the next move, the possible resulting game states are $1$ brick, a $2$ brick wall, or $2$ separate bricks. The first two options have nim-values of $1$ and $2$ . The final option has a nim-value of $1\oplus 1 = 0$ , so the nim-value of this game state is $3$ .

Next, the $4$ brick wall. The possible states are a $2$ brick wall, a $3$ brick wall, a $2$ brick wall and a $1$ brick wall, or a $1$ brick wall and a $1$ brick wall. The nim-values of these states are $2$ , $3$ , $3$ , and $0$ , respectively, and hence the nim-value of this game state is $1$ .

The possible game states after the $5$ brick wall are the following: a $3$ brick wall, a $4$ brick wall, a $3$ brick wall and a $1$ brick wall, a two $2$ brick walls, and a $2$ brick wall plus a $1$ brick wall. The nim-values of these are $3$ , $1$ , $2$ , $0$ , and $3$ , respectively, meaning the nim-value of a $5$ brick wall is $4$ .

Finally, we find the nim-value of a $6$ brick wall. The possible states are a $5$ brick wall, a $4$ brick wall and a $1$ brick wall, a $3$ brick wall and a $2$ brick wall, a $4$ brick wall, a $3$ brick wall and a $1$ brick wall, and finally two $2$ brick walls. The nim-values of these game states are $4$ , $0$ , $1$ , $1$ , $2$ , and $0$ , respectively. This means the $6$ brick wall has a nim-value of $3$ .

The problem is asking which of the answer choices is losing, or has a nim-value of $0$ . We see that option $\textbf{(A)}$ has a nim-value of $3\oplus1\oplus1=3$ , option $\textbf{(B)}$ has a nim-value of $3\oplus2\oplus1=0$ , option $\textbf{(C)}$ has a nim-value of $3\oplus2\oplus2=3$ , option $\textbf{(D)}$ has a nim-value of $3\oplus3\oplus1=1$ , and option $\textbf{(E)}$ has a nim-value of $3\oplus3\oplus2=2$ , so the answer is $\boxed{\textbf{(B) }(6, 2, 1)}$ .

This method can also be extended to solve the note after the first solution. The nim-values of the $7$ brick wall and the $8$ brick wall are $2$ and $1$ , using the same method as above. The nim-value of $(8, 7, 5, 3, 2)$ is therefore $1\oplus2\oplus4\oplus3\oplus2 = 5$ , which is winning.

Video Solution by OmegaLearn (Game Theory)

https://youtu.be/zkSBMVAfYLo

~ pi_is_3.14

2021 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 21	Followed by Problem 23
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

2021 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 23	Followed by Problem 25
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search