Difference between revisions of "2021 AMC 12B Problems/Problem 22"

Revision as of 22:40, 4 June 2021

The following problem is from both the 2021 AMC 10B #24 and 2021 AMC 12B #22, so both problems redirect to this page.

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 1

We say that a game state is an N-position if it is winning for the next player (the player to move), and a P-position if it is winning for the other player. We are trying to find which of the given states is a P-position.

First we note that symmetrical positions are P-positions, as the second player can win by mirroring the first player's moves. It follows that $(6, 1, 1)$ is an N-position, since we can win by moving to $(2, 2, 1, 1)$ ; this rules out $\textbf{(A)}$ . We next look at $(6, 2, 1)$ . The possible next states are $(6, 2), \enskip (6, 1, 1), \enskip (6, 1), \enskip (5, 2, 1), \enskip (4, 2, 1, 1), \enskip (4, 2, 1), \enskip (3, 2, 2, 1), \enskip (3, 2, 1, 1), \enskip (2, 2, 2, 1).$ None of these are symmetrical, so we might reasonably suspect that they are all N-positions. Indeed, it just so happens that for all of these states except $(6, 2)$ and $(6, 1)$ , we can win by moving to $(2, 2, 1, 1)$ ; it remains to check that $(6, 2)$ and $(6, 1)$ are N-positions.

To save ourselves work, it would be nice if we could find a single P-position directly reachable from both $(6, 2)$ and $(6, 1)$ . We notice that $(3, 2, 1)$ is directly reachable from both states, so it would suffice to show that $(3, 2, 1)$ is a P-position. Indeed, the possible next states are $(3, 2), \enskip (3, 1, 1), \enskip (3, 1), \enskip (2, 2, 1), \enskip (2, 1, 1, 1), \enskip (2, 1, 1),$ which allow for the following refutations:

$\begin{align*} &(3, 2) \to (2, 2), && &&(3, 1, 1) \to (1, 1, 1, 1), && &&(3, 1) \to (1, 1), \\ &(2, 2, 1) \to (2, 2), && &&(2, 1, 1, 1) \to (1, 1, 1, 1), && &&(2, 1, 1) \to (1, 1). \end{align*}$

Hence, $(3, 2, 1)$ is a P-position, so $(6, 2)$ and $(6, 1)$ are both N-positions, along with all other possible next states from $(6, 2, 1)$ as noted before. Thus, $(6, 2, 1)$ is a P-position, so our answer is $\boxed{\textbf{(B)}}$ . (For completeness, we could also use the reasoning from Solution 2 to rule out $\textbf{(C)}$ , $\textbf{(D)}$ and $\textbf{(E)}$ .)

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

[Why is the nim-value of it $1$ ? - awesomediabrine

https://en.wikipedia.org/wiki/Mex_(mathematics)]

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 = 6$ , which is winning.

Solution 4

Consider the following, much simpler game.

Arjun and Beth can each either take 1 or 2 bricks from the right-hand-side of a continuous row of initially $n$ bricks. It is easy to see that for $n$ a multiple of 3, Beth can "mirror" whatever Arjun plays: if he takes 1, she takes 2, and if he takes 2, she takes 1. With this strategy, Beth always takes the last brick. If $n$ is not a multiple of 3, then Arjun takes whichever amount puts Beth in the losing position.

The total number of bricks in the initial states given by the answer choices is $8, 9, 10, 10, 11$ . Thus, answer choice $\textbf{(B)}$ appears promising as a winning position for Beth. The difference between this game and the simplified game is that in certain positions, namely those consisting of fragments of size only 1, taking 2 bricks is not allowed. We can assume that for the starting position $(6, 2, 1)$ , Beth always has a move to ensure that she can continue to mirror Arjun throughout the game. (This could be proven rigorously with lots of casework. In particular, she must avoid providing Arjun with a position of 3 continuous bricks, because then he could take the middle block and force a win.) The assumption seems reasonable, so the answer is $\textbf{(B)}$ .

Video Solution by OmegaLearn (Game Theory)

https://youtu.be/zkSBMVAfYLo

~ pi_is_3.14

@@ Line 11: / Line 11: @@
 == Solution 1==
-First we note that symmetrical positions are losing for the player to move. Then we start checking small positions. <math>(n)</math> is always winning for the first player. Furthermore, <math>(3, 2, 1)</math> is losing and so is <math>(4, 1).</math> We look at all the positions created from <math>(6, 2, 1),</math> as <math>(6, 1, 1)</math> is obviously winning by playing <math>(2, 2, 1, 1).</math> There are several different positions that can be played by the first player from <math>(6, 2, 1).</math> They are <math>(2, 2, 2, 1), (1, 3, 2, 1), (4, 2, 1), (6, 1), (5, 2, 1), (4, 1, 2, 1), (3, 2, 2, 1).</math> Now we list refutations for each of these moves:
+We say that a game state is an N-position if it is winning for the next player (the player to move), and a P-position if it is winning for the other player. We are trying to find which of the given states is a P-position.
+First we note that symmetrical positions are P-positions, as the second player can win by mirroring the first player's moves. It follows that <math>(6, 1, 1)</math> is an N-position, since we can win by moving to <math>(2, 2, 1, 1)</math>; this rules out <math>\textbf{(A)}</math>. We next look at <math>(6, 2, 1)</math>. The possible next states are
+<cmath>(6, 2), \enskip (6, 1, 1), \enskip (6, 1), \enskip (5, 2, 1), \enskip (4, 2, 1, 1), \enskip (4, 2, 1), \enskip (3, 2, 2, 1), \enskip (3, 2, 1, 1), \enskip (2, 2, 2, 1).</cmath>
+None of these are symmetrical, so we might reasonably suspect that they are all N-positions. Indeed, it just so happens that for all of these states except <math>(6, 2)</math> and <math>(6, 1)</math>, we can win by moving to <math>(2, 2, 1, 1)</math>; it remains to check that <math>(6, 2)</math> and <math>(6, 1)</math> are N-positions.
-<math>(2, 2, 2, 1) - (2, 1, 2, 1)</math>
+To save ourselves work, it would be nice if we could find a single P-position directly reachable from both <math>(6, 2)</math> and <math>(6, 1)</math>. We notice that <math>(3, 2, 1)</math> is directly reachable from both states, so it would suffice to show that <math>(3, 2, 1)</math> is a P-position. Indeed, the possible next states are
+<cmath>(3, 2), \enskip (3, 1, 1), \enskip (3, 1), \enskip (2, 2, 1), \enskip (2, 1, 1, 1), \enskip (2, 1, 1),</cmath>
+which allow for the following refutations:
+<cmath>\begin{align*}
+&(3, 2) \to (2, 2), && &&(3, 1, 1) \to (1, 1, 1, 1), && &&(3, 1) \to (1, 1), \\
+&(2, 2, 1) \to (2, 2), && &&(2, 1, 1, 1) \to (1, 1, 1, 1), && &&(2, 1, 1) \to (1, 1).
+\end{align*}</cmath>
-<math>(1, 3, 2, 1) - (3, 2, 1)</math>
+Hence, <math>(3, 2, 1)</math> is a P-position, so <math>(6, 2)</math> and <math>(6, 1)</math> are both N-positions, along with all other possible next states from <math>(6, 2, 1)</math> as noted before. Thus, <math>(6, 2, 1)</math> is a P-position, so our answer is <math>\boxed{\textbf{(B)}}</math>. (For completeness, we could also use the reasoning from Solution 2 to rule out <math>\textbf{(C)}</math>, <math>\textbf{(D)}</math> and <math>\textbf{(E)}</math>.)
-<math>(4, 2, 1) - (4, 1)</math>
-<math>(6, 1) - (4, 1)</math>
-<math>(5, 2, 1) - (3, 2, 1)</math>
-<math>(4, 1, 2, 1) - (2, 1, 2, 1)</math>
-<math>(3, 2, 2, 1) - (1, 2, 2, 1)</math>
-This proves that <math>(6, 2, 1)</math> is losing for the first player.
 -Note: In general, this game is very complicated. For example <math>(8, 7, 5, 3, 2)</math> is winning for the first player but good luck showing that.

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