Solution
The Wandering Token
Show the problem again
A token sits on one square of a 3×3 grid, and that square counts as visited. Players alternate moving the token to an orthogonally adjacent square that has not been visited yet. A player who cannot move loses. The token may be started on any of the 9 squares, and the player to move first is the one who must make the first move from it. For how many of the 9 starting squares does the first mover win with optimal play? Answer with an integer.
Worked solution
Colour the grid like a chessboard. Corners and centre form the five squares of one colour, and the four edge squares form the other. A maximum matching of the grid graph has 4 dominoes and leaves one of the five majority squares uncovered, so each of the five majority squares can be left out of some maximum matching. If the token starts on a square missed by some maximum matching, the second player answers each move by moving to the partner in that matching, and the first player eventually runs out of moves. Therefore the five majority squares lose for the first mover. The four edge squares are covered by every maximum matching (each such matching covers all four minority squares), so the first player moves along the matching edge and keeps playing the partner of whatever the opponent does, which wins. The answer is 4, confirmed by exhaustive search of the walk tree.
Source: Undirected vertex geography; the matching criterion appears in work of Fraenkel, Scheinerman and Ullman on undirected geography games. Statement written for AxiomIQ.