Communications of the ACM
Last byte
Puzzled: Solutions and Sources
Bob can win the Path Game on an 8×8 checkerboard by imagining the board is covered by 32 dominoes, each occupying two adjacent squares. (There are many ways to do this; can you count them?) When Alice marks a square covered by a domino, Bob simply marks the square at the other end of that domino.
2. The Match Game
The same strategy works for Bob in the Match Game.
3. General Graphs
Amazingly, whenever Bob has a winning strategy for the Path Game, he can win the apparently more difficult Match Game as well. To win the Match Game, he needs the graphical equivalent of a domino cover—a "perfect matching." A matching in a graph is a collection of pairs of adjacent vertices, such that no vertex shows up in two pairs. A matching is deemed "perfect" if it uses up all the vertices; note this requires the graph to have an even number of vertices to begin with.
If the graph has a perfect matching, Bob easily wins either game by fixing some perfect matching and always marking the vertex paired with the one Alice just marked. The tricky part is to show that if there is no perfect matching, Alice can win the Path Game, and therefore the Match Game as well. To do this she chooses a maximum-size matching, and starts the game by picking a vertex not included in the matching. After that, she always picks the mate to Bob's last move, until poor Bob runs out of moves.
How do we know Alice always has such a move available? Suppose she is OK until she gets stuck after Bob's nth move, she and Bob having constructed the path a1, b1, a2, b2, ..., an, bn. The pairs {b1,a2}, {b2,a3}, ..., {bn–1,an} are then all in the matching, but bn is unmatched.
However, this situation is not possible.
Why? Because then we could replace the n–1 pairs {b1,a2}, {b2,a3}, ..., {bn–1,an} with the n pairs {b1,a1}, {b2,a2}, ..., {bn,an} to get a bigger matching—contradicting the assumption that the matching Alice chose was of maximum size. So Alice always has a legal move, and thus it is Bob who eventually gets stuck and loses.
We conclude that Bob wins both games if the graph has a perfect matching; otherwise Alice wins both.
Want to know more about matchings? Any book on graph theory or computer algorithms will get you started, but if you prefer to tackle a whole book on the subject, see Matching Theory by László Lovász and Michael Plummer, North-Holland, Amsterdam, 1986.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.
No entries found