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: , 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?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
We say that a game state is an -position if it is winning for the next player (the player to move), and a -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 -positions, as the second player can win by mirroring the first player's moves. It follows that is an -position, since we can win by moving to ; this rules out (A). We next look at . The possible next states are
None of these are symmetrical, so we might reasonably suspect that they are all -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 -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 -position. Indeed, the possible next states are
which allow for the following refutations:
Hence, is a P-position, so and are both -positions, along with all other possible next states from as noted before. Thus, is a -position, so our answer is . (For completeness, we could also rule out and as in Solution .)
-Note: In general, this game is very complicated. For example is winning for the first player but good luck showing that.
OR
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 .
The problems on this page are the property of the MAA's American Mathematics Competitions