Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
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.

Back to Top

2. The Match Game

The same strategy works for Bob in the Match Game.

Back to Top

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 covera "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}, ..., {bn1,an} are then all in the matching, but bn is unmatched.

However, this situation is not possible.

Why? Because then we could replace the n1 pairs {b1,a2}, {b2,a3}, ..., {bn1,an} with the n pairs {b1,a1}, {b2,a2}, ..., {bn,an} to get a bigger matchingcontradicting 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.

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

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


Copyright held by author.

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


 

No entries found