Putnam 2020, Problem B-2

Let \( k \) and \( n \) be integers with \( 1 \leq k < n \). Alice and Bob play a game with \( k \) pegs in a line of \( n \) holes. At the beginning of the game, the pegs occupy the \( k \) leftmost holes. A legal move consists of moving a single peg to any vacant hole that is further to the right. The players alternate moves, with Alice playing first. The game ends when the pegs are in the \( k \) rightmost holes, so whoever is next to play cannot move and therefore loses. For what values of \( n \) and \( k \) does Alice have a winning strategy?

Solution:
We refer to this two-player game, with $n$ holes and $k$ pegs, as the $(n,k)$-game. We will show that Alice has a winning strategy for the $(n,k)$-game if and only if at least one of $n$ and $k$ is odd; otherwise Bob has a winning strategy.

We reduce the first claim to the second as follows. If $n$ and $k$ are both odd, then Alice can move the $k$-th peg to the last hole; this renders the last hole, and the peg in it, totally out of play, thus reducing the $(n,k)$-game to the $(n-1,k-1)$-game, for which Alice now has a winning strategy by the second claim. Similarly, if $n$ is odd but $k$ is even, then Alice may move the first peg to the $(k+1)$-st hole, removing the first hole from play and reducing the $(n,k)$-game to the $(n-1,k)$ game. Finally, if $n$ is even but $k$ is odd, then Alice can move the first peg to the last hole, taking the first and last holes, and the peg in the last hole, out of play, and reducing the $(n,k)$-game to the $(n-2,k-1)$-game.

We now assume $n$ and $k$ are both even and describe a winning strategy for the $(n,k)$-game for Bob. Subdivide the $n$ holes into $n/2$ disjoint pairs of adjacent holes. Call a configuration of $k$ pegs good if for each pair of holes, both or neither is occupied by pegs, and note that the starting position is good. Bob can ensure that after each of his moves, he leaves Alice with a good configuration: presented with a good configuration, Alice must move a peg from a pair of occupied holes to a hole in an unoccupied pair; then Bob can move the other peg from the first pair to the remaining hole in the second pair, resulting in another good configuration. In particular, this ensures that Bob always has a move to make. Since the game must terminate, this is a winning strategy for Bob.