Putnam 2025, Problem A-3

Alice and Bob play a game with a string of \( n \) digits, each of which is restricted to be 0, 1, or 2. Initially all the digits are 0. A legal move is to add or subtract 1 from one digit to create a new string that has not appeared before. A player with no legal move loses, and the other player wins. Alice goes first, and the players alternate moves. For each \( n \geq 1 \), determine which player has a strategy that guarantees winning.

Solution:
Bob has a winning strategy for all \( n \geq 1 \).

Consider the graph \( G \) with vertices \( \{0,1,2\}^n \setminus \{(0, \ldots, 0)\} \) with an edge between any two strings that differ by adding or subtracting 1 in a single position. A perfect matching of \( G \) consists of a collection \( P \) of edges of \( G \) which contain each vertex exactly once. Each perfect matching \( G \) leads to a winning strategy for Bob: if Alice’s last move was to vertex \( v \), Bob moves to the vertex \( w \) such that \( \{v, w\} \in P \). This maintains the condition that before every move by Alice, the unused vertices still admit a perfect matching contained in \( P \); consequently, Bob’s next move is always legal.

It thus suffices to exhibit a perfect matching on \( G \); there are many ways to do this. For example, for each vertex \( v \), find the first nonzero coordinate of \( v \), let \( w \) be the result of interchanging 1 with 2 in that position, and include \( \{(v, w)\} \) in \( P \); since running this process with \( w \) leads back to \( v \), we see that \( P \) is a perfect matching. (For this matching, Bob’s strategy is to always change the first nonzero digit from 1 to 2 or vice versa.)