Putnam 2006, Problem A-2

Alice and Bob play a game in which they take turns removing stones from a heap that initially has $n$ stones. The number of stones removed at each turn must be one less than a prime number. The winner is the player who takes the last stone. Alice plays first. Prove that there are infinitely many $n$ such that Bob has a winning strategy. (For example, if $n = 17$, then Alice might take 6 leaving 11; then Bob might take 1 leaving 10; then Alice can take the remaining stones to win.)

Solution:
Suppose on the contrary that the set $B$ of values of $n$ for which Bob has a winning strategy is finite; for convenience, we include $n = 0$ in $B$, and write $B = \{b_1, \ldots, b_m\}$. Then for every nonnegative integer $n$ not in $B$, Alice must have some move on a heap of $n$ stones leading to a position in which the second player wins. That is, every nonnegative integer not in $B$ can be written as $b + p - 1$ for some $b \in B$ and some prime $p$. However, there are numerous ways to show that this cannot happen.

**First solution:** Let $t$ be any integer bigger than all of the $b \in B$. Then it is easy to write down $t$ consecutive composite integers, e.g., $(t+1)! + 2, \ldots, (t+1)! + t + 1$. Take $n = (t+1)! + t$; then for each $b \in B$, $n - b + 1$ is one of the composite integers we just wrote down.

**Second solution:** Let $p_1, \ldots, p_{2m}$ be any prime numbers; then by the Chinese remainder theorem, there exists a positive integer $x$ such that
$$x - b_1 \equiv -1 \pmod{p_1p_{m+1}}$$
$$\vdots$$
$$x - b_n \equiv -1 \pmod{p_mp_{2m}}.$$
For each $b \in B$, the unique integer $p$ such that $x = b + p - 1$ is divisible by at least two primes, and so cannot itself be prime.

**Third solution:** (by Catalin Zara) Put $b_1 = 0$, and take $n = (b_2 - 1) \cdots (b_m - 1)$; then $n$ is composite because $3, 8 \in B$, and for any nonzero $b \in B$, $n - b_i + 1$ is divisible by but not equal to $b_i - 1$. (One could also take $n = b_2 \cdots b_m - 1$, so that $n - b_i + 1$ is divisible by $b_i$.)