Difference between revisions of "2021 AMC 12B Problems/Problem 22"
(→Solution 3 (Nim-values)) |
|||
Line 59: | Line 59: | ||
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, 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>. | + | 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>. |
+ | (Wait why is the nim-value of it <math>1</math>? - awesomediabrine) | ||
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>. | 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>. | ||
Line 67: | Line 68: | ||
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>. | 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 = 5</math>, which is winning. | + | 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 = 5</math>, which is winning. |
== Video Solution by OmegaLearn (Game Theory) == | == Video Solution by OmegaLearn (Game Theory) == |
Revision as of 00:24, 16 February 2021
Contents
[hide]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 and can be changed into any of the following by one move: or
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?
Solution
First we note that symmetrical positions are losing for the player to move. Then we start checking small positions. is always winning for the first player. Furthermore, is losing and so is We look at all the positions created from as is obviously winning by playing There are several different positions that can be played by the first player from They are Now we list refutations for each of these moves:
This proves that is losing for the first player.
-Note: In general, this game is very complicated. For example is winning for the first player but good luck showing that.
Solution 2 (Process of Elimination)
can be turned into by Arjun, which is symmetric, so Beth will lose.
can be turned into by Arjun, which is symmetric, so Beth will lose.
can be turned into by Arjun, which is symmetric, so Beth will lose.
can be turned into by Arjun, which is symmetric, so Beth will lose.
That leaves or .
Solution 3 (Nim-values)
Let the nim-value of the ending game state, where someone has just removed the final brick, be . Then, any game state with a nim-value of 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 bricks long (since the answer choices only go up to ).
First, the game with brick has a nim-value of .
Similarly, the game with bricks has a nim-value of .
Next, we consider a brick wall. After the next move, the possible resulting game states are brick, a brick wall, or separate bricks. The first two options have nim-values of and . The final option has a nim-value of , so the nim-value of this game state is .
Next, the brick wall. The possible states are a brick wall, a brick wall, a brick wall and a brick wall, or a brick wall and a brick wall. The nim-values of these states are , , , and , respectively, and hence the nim-value of this game state is . (Wait why is the nim-value of it ? - awesomediabrine)
The possible game states after the brick wall are the following: a brick wall, a brick wall, a brick wall and a brick wall, a two brick walls, and a brick wall plus a brick wall. The nim-values of these are , , , , and , respectively, meaning the nim-value of a brick wall is .
Finally, we find the nim-value of a brick wall. The possible states are a brick wall, a brick wall and a brick wall, a brick wall and a brick wall, a brick wall, a brick wall and a brick wall, and finally two brick walls. The nim-values of these game states are , , , , , and , respectively. This means the brick wall has a nim-value of .
The problem is asking which of the answer choices is losing, or has a nim-value of . We see that option has a nim-value of , option has a nim-value of , option has a nim-value of , option has a nim-value of , and option has a nim-value of , so the answer is .
This method can also be extended to solve the note after the first solution. The nim-values of the brick wall and the brick wall are and , using the same method as above. The nim-value of is therefore , which is winning.
Video Solution by OmegaLearn (Game Theory)
~ pi_is_3.14
See Also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.