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

(Problem)
m (Solution)
(9 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2021 AMC 10B Problems#Problem 24|2021 AMC 10B #24]] and [[2021 AMC 12B Problems#Problem 22|2021 AMC 12B #22]]}}
 +
 
==Problem==
 
==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 <math>4</math> and <math>2</math> can be changed into any of the following by one move: <math>(3,2),(2,1,2),(4),(4,1),(2,2),</math> or <math>(1,1,2).</math>
 
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 <math>4</math> and <math>2</math> can be changed into any of the following by one move: <math>(3,2),(2,1,2),(4),(4,1),(2,2),</math> or <math>(1,1,2).</math>
Line 8: Line 10:
 
<math>\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)</math>
 
<math>\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)</math>
  
==Solution==
+
== Solution 1==
{{solution}}
+
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:
 +
 
 +
 
 +
<math>(2, 2, 2, 1) - (2, 1, 2, 1)</math>
 +
 
 +
 
 +
<math>(1, 3, 2, 1) - (3, 2, 1)</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.
 +
 
 +
== Solution 2 (Process of Elimination)==
 +
 
 +
<math>(6,1,1)</math> can be turned into <math>(2,2,1,1)</math> by Arjun, which is symmetric, so Beth will lose.
 +
 
 +
<math>(6,3,1)</math> can be turned into <math>(3,1,3,1)</math> by Arjun, which is symmetric, so Beth will lose.
 +
 
 +
<math>(6,2,2)</math> can be turned into <math>(2,2,2,2)</math> by Arjun, which is symmetric, so Beth will lose.
 +
 
 +
<math>(6,3,2)</math> can be turned into <math>(3,2,3,2)</math> by Arjun, which is symmetric, so Beth will lose.
 +
 
 +
That leaves <math>(6,2,1)</math> or <math>\boxed{\textbf{(B)}}</math>.
 +
 
 +
== Solution 3 (Nim-values) ==
 +
 
 +
Let the nim-value of the ending game state, where someone has just removed the final brick, be <math>0</math>. Then, any game state with a nim-value of <math>0</math> 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 <math>6</math> bricks long (since the answer choices only go up to <math>6</math>).
 +
 
 +
First, the game with <math>1</math> brick has a nim-value of <math>1</math>.
 +
 
 +
Similarly, the game with <math>2</math> bricks has a nim-value of <math>2</math>.
 +
 
 +
Next, we consider a <math>3</math> brick wall. After the next move, the possible resulting game states are <math>1</math> brick, a <math>2</math> brick wall, or <math>2</math> separate bricks. The first two options have nim-values of <math>1</math> and <math>2</math>. The final option has a nim-value of <math>1\oplus 1 = 0</math>, so the nim-value of this game state is <math>3</math>.
 +
 
 +
Next, the <math>4</math> brick wall. The possible states are a <math>2</math> brick wall, a <math>3</math> brick wall, a <math>2</math> brick wall and a <math>1</math> brick wall, or a <math>1</math> brick wall and a <math>1</math> brick wall. The nim-values of these states are <math>2</math>, <math>3</math>, <math>3</math>, and <math>0</math>, respectively, and hence the nim-value of this game state is <math>1</math>.
 +
 
 +
[Why is the nim-value of it <math>1</math>? - awesomediabrine
 +
 
 +
https://en.wikipedia.org/wiki/Mex_(mathematics)]
 +
 
 +
The possible game states after the <math>5</math> brick wall are the following: a <math>3</math> brick wall, a <math>4</math> brick wall, a <math>3</math> brick wall and a <math>1</math> brick wall, a two <math>2</math> brick walls, and a <math>2</math> brick wall plus a <math>1</math> brick wall. The nim-values of these are <math>3</math>, <math>1</math>, <math>2</math>, <math>0</math>, and <math>3</math>, respectively, meaning the nim-value of a <math>5</math> brick wall is <math>4</math>.
 +
 
 +
Finally, we find the nim-value of a <math>6</math> brick wall. The possible states are a <math>5</math> brick wall, a <math>4</math> brick wall and a <math>1</math> brick wall, a <math>3</math> brick wall and a <math>2</math> brick wall, a <math>4</math> brick wall, a <math>3</math> brick wall and a <math>1</math> brick wall, and finally two <math>2</math> brick walls. The nim-values of these game states are <math>4</math>, <math>0</math>, <math>1</math>, <math>1</math>, <math>2</math>, and <math>0</math>, respectively. This means the <math>6</math> brick wall has a nim-value of <math>3</math>.
 +
 
 +
The problem is asking which of the answer choices is losing, or has a nim-value of <math>0</math>. We see that option <math>\textbf{(A)}</math> has a nim-value of <math>3\oplus1\oplus1=3</math>, option <math>\textbf{(B)}</math> has a nim-value of <math>3\oplus2\oplus1=0</math>, option <math>\textbf{(C)}</math> has a nim-value of <math>3\oplus2\oplus2=3</math>, option <math>\textbf{(D)}</math> has a nim-value of <math>3\oplus3\oplus1=1</math>, and option <math>\textbf{(E)}</math> has a nim-value of <math>3\oplus3\oplus2=2</math>, so the answer is <math>\boxed{\textbf{(B) }(6, 2, 1)}</math>.
 +
 
 +
This method can also be extended to solve the note after the first solution. The nim-values of the <math>7</math> brick wall and the <math>8</math> brick wall are <math>2</math> and <math>1</math>, using the same method as above. The nim-value of <math>(8, 7, 5, 3, 2)</math> is therefore <math>1\oplus2\oplus4\oplus3\oplus2 = 6</math>, 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 <math>n</math> bricks.
 +
It is easy to see that for <math>n</math> 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 <math>n</math> 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 <math>8, 9, 10, 10, 11</math>. Thus, answer choice <math>\textbf{(B)}</math> 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 <math>(6, 2, 1)</math>, 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 <math>\textbf{(B)}</math>.
 +
 
 +
 
 +
== Video Solution by OmegaLearn (Game Theory) ==
 +
https://youtu.be/zkSBMVAfYLo
 +
 
 +
~ pi_is_3.14
  
 
==See Also==
 
==See Also==
 
{{AMC12 box|year=2021|ab=B|num-b=21|num-a=23}}
 
{{AMC12 box|year=2021|ab=B|num-b=21|num-a=23}}
 +
{{AMC10 box|year=2021|ab=B|num-b=23|num-a=25}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 17:05, 6 April 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

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

[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

See Also

2021 AMC 12B (ProblemsAnswer KeyResources)
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 (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png