Difference between revisions of "2021 AMC 12B Problems/Problem 22"
Arcticturn (talk | contribs) (→Solution 5) |
|||
Line 98: | Line 98: | ||
{{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}} | {{AMC10 box|year=2021|ab=B|num-b=23|num-a=25}} | ||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 20:05, 20 August 2021
- The following problem is from both the 2021 AMC 10B #24 and 2021 AMC 12B #22, so both problems redirect to this page.
Contents
[hide]- 1 Problem
- 2 Solution 1
- 3 Solution 2 (Process of Elimination)
- 4 Solution 3 (Nim-values)
- 5 Solution 4
- 6 Solution 5
- 7 Video Solution by Mathematical Dexterity (Be A Copycat!)
- 8 Video Solution by OmegaLearn (Game Theory)
- 9 Video Solution by Interstigation (Goal of Winning - Pairs and Symmetricity & In-depth)
- 10 See Also
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
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 is an N-position, since we can win by moving to ; this rules out . We next look at . The possible next states are 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 and , we can win by moving to ; it remains to check that and are N-positions.
To save ourselves work, it would be nice if we could find a single P-position directly reachable from both and . We notice that is directly reachable from both states, so it would suffice to show that is a P-position. Indeed, the possible next states are which allow for the following refutations:
Hence, is a P-position, so and are both N-positions, along with all other possible next states from as noted before. Thus, is a P-position, so our answer is . (For completeness, we could also rule out , and as in Solution 2.)
-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 .
Solution 5
We can start by guessing and checking our solutions. Let's start with A, . Arjun goes first, and he has a winning strategy. His strategy is to cut the 6 block in half, so whatever Beth does, Arjun will copy. If we see this in practice, Arjun has made the block in to . If Beth takes 1, he will take one. If Beth takes 2, he will take 2 as well.
Then, we can guess solution B, . If Arjun starts by taking 1 of the blocks, he will either have , , (Where x+y = 5). If he has , Beth can take 2 out of the middle of to get which we know Arjun will lose because we know by symmetry from answer choice A. If he has , Beth will take out one from the edge, and we get . Beth can now copy whatever Arjun does, so she will win.
Next, if he takes one out to get , we can either have or . If it is the first case, Beth can take the edge 2 out of the 4, which gives us and whatever Arjun does, Beth can do, so she has established a win. If it is the 2nd case, Beth can take out 2 from the 3 to get , in which, Beth can copy whatever Arjun does, so Beth will win. So in all 4 cases, Beth wins. So our answer is
~Arcticturn
Video Solution by Mathematical Dexterity (Be A Copycat!)
https://www.youtube.com/watch?v=m6yWxyYZLqw
Video Solution by OmegaLearn (Game Theory)
~ pi_is_3.14
Video Solution by Interstigation (Goal of Winning - Pairs and Symmetricity & In-depth)
~ Interstigation
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.