2021 AMC 12B Problems/Problem 22
- The following problem is from both the 2021 AMC 10B #24 and 2021 AMC 12B #22, so both problems redirect to this page.
Contents
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 1
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 .
[Why is the nim-value of it ? - awesomediabrine
https://en.wikipedia.org/wiki/Mex_(mathematics)]
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.
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 bricks. It is easy to see that for 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 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 . Thus, answer choice 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 , 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 .
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.