Communications of the ACM
Last byte
Puzzled: Paths and Matchings
Alice (red) beats Bob (blue) in a Path Game.
The Path Game. Alice and Bob alternately place a checker on an unoccupied square of an initially empty eight-by-eight checkerboard (see the figure here). The rule is that after Alice places her initial checker, every new checker must be (orthogonally) adjacent to the most recently placed checker. The players are in effect constructing a path of checkers. The last player to make a legal move wins the game. Your mission: find a winning strategy for Bob.
The Match Game. Suppose that Alice, when it is her turn, is no longer obliged to play next to Bob's last checker and may instead place her checker on any unoccupied square. Bob is still constrained to "match" Alice, that is, to play next to Alice's last move. As in the Path Game, the last player to make a legal move wins the game. So who wins now, with best play?
General graphs. Either the Path Game or the Match Game can be played on any finite graph. Alice begins by marking any vertex, and, subsequently, Bob and Alice alternate in marking vertices. In the Path Game, each marked vertex must be adjacent to the most recently marked vertex. In the Match Game, each vertex marked by Bob must be adjacent to the most recently marked vertex, but Alice can mark any unmarked vertex when it is her turn. As in the checkerboard versions, the last player to make a legal move wins the game. Now find a graph on which, with best play, Bob wins the Path Game and Alice wins the Match Game... if there is one.
Footnotes
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.
No entries found