Opinion
Computing Applications Last byte

Puzzled: Solutions and Sources

Last month (August 2014), we presented three puzzles concerning the Path Game and the Match Game, each of which can be played on any finite graph. To start, Alice marks a vertex; Bob and Alice then alternate marking vertices until one (the loser) is unable to mark any more. In the Path Game, each vertex thus marked, following the first one, must be adjacent to the most recently marked vertex. In the Match Game, only Bob has this constraint, whereas Alice can mark any vertex.
Posted
  1. 1. The Path Game
  2. 2. The Match Game
  3. 3. General Graphs
  4. Author
  5. Footnotes
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 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.

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More