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:
Answer (B): Observe that a player who can leave two (or any even number of) copies of each wall size can win by mirroring the opponent's moves in the other copy. For any configuration except (B), Arjun has a move that leaves two or four copies of each wall size. Specifically these moves include generating walls of sizes , and (3, 2, 3, 2 ) from choices (A), (C), (D), and (E), respectively. Only choice (B) gives Beth a chance.
It remains to show that Beth can win from configuration (B). With two exceptions, any starting move Arjun can make allows Beth to create a position from which she wins by the mirroring strategy. The exceptions are when Arjun takes away the wall of size 1 or the wall of size 2 . In either case, Beth must take from the wall of size 6, leaving ( ) or ( ), respectively. Then any move by Arjun leaves Beth able to create a mirroring position and win.
Note: This combinatorial game is called Kayles.
The problems on this page are the property of the MAA's American Mathematics Competitions