acm-header
Sign In

Communications of the ACM

Last byte

Puzzled: Paths and Matchings


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.

Back to Top

Author

Peter Winkler (puzzled@cacm.acm.org) is William Morrill Professor of Mathematics and Computer Science at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

Back to Top

Figures

UF1Figure. Alice (red) beats Bob (blue) in a Path Game.

Back to top


Copyright held by author.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents: