Coprime Game I

If $m = 1$ , then 1 is the only integer removed from the list. If $m > 1$ , then removing $m$ from the list is equivalent to removing the prime factors of $m$ and their multiples from the list. With this understanding, we can simplify the gameplay. We will start with a list containing 1 and the primes less than and coprime to $N$ . Players will take turns removing one or more integers from this much shorter list observing the following rules:

• each turn, a player can remove 1 or a prime, but not both; and
• a player can remove multiple primes in a single turn if their product is less than $N$ .

According to the second rule, when $N \leq 200$ , a player can only remove multiple primes in a single turn if at least one of them is 2, 3, 5, 7, or 11. We will call these five primes the small primes . When there are no small primes left on the list, players remove integers one at a time until there are no integers left.

We will illustrate positions in the game using the symbol $s$ to represent small primes and $z$ to represent other integers. When we write, for example, a player "removes $s\,z$ ," we mean that the player removes a small prime and another integer that is not a small prime. For convenience, we will list the symbols in two rows. In the following position, there is an odd number of integers and none of them is a small integer. $\begin{matrix} z & z & \cdots & z & z \\ z & z & \cdots & z & \end{matrix} \tag{1}$ From this position, players will alternately remove one integer at a time until one of them removes the last integer and loses. Clearly, this is a losing position for whichever player plays next. Now consider a position in which there is an even number of integers with exactly two small integers. $\begin{matrix} s & z & z & \cdots & z & z \\ & s & z & \cdots & z & \end{matrix} \tag{2}$ If Dan plays next, then Sam has a strategy to force Dan into position (1) by making sure exactly three integers are removed in the following two turns, including both small primes:

• if Dan removes $s$ , then Sam removes $s\,z$ ;
• if Dan removes $z$ , then Sam removes $s\,s$ ;
• if Dan removes $s\,s$ , then Sam removes $z$ ; and
• if Dan removes $s\,z$ , then Sam removes $s$ .

In all four cases, Dan is left in position (1) and therefore loses. This strategy works provided two conditions are met: (a) the remaining integers must be small enough so that Sam can remove $s\,s$ or $s\,z$ , if necessary; and (b) the remaining integers must be large enough so that Dan cannot remove $s\,s\,z$ in a single turn.

We will now demonstrate a strategy with which the second player is guaranteed to win when $N = 199$ . First, note that 199 is prime and that there are 45 primes less than 199, including all five small primes. In the simplified gameplay, this means there are 46 integers on the list, the 45 primes plus the integer 1. $\begin{matrix} s & s & s & z & z & \cdots & z & z \\ & s & s & z & z & \cdots & z & \end{matrix}$ Suppose Dan plays first. The strategy for Sam is to make sure that exactly four integers are removed in the first two turns, including exactly three small primes:

• if Dan removes $s$ , then Sam removes $s\,s\,z$ ;
• if Dan removes $z$ , then Sam removes $s\,s\,s$ ;
• if Dan removes $s\,s$ , then Sam removes $s\,z$ ;
• if Dan removes $s\,z$ , then Sam removes $s\,s$ ;
• if Dan removes $s\,s\,s$ , then Sam removes $z$ ; and
• if Dan removes $s\,s\,z$ , then Sam removes $s$ .

This puts Dan in position (2). We must show that Sam can apply this strategy in a way that ensures this is a losing position for Dan based on conditions (a) and (b).

• If Dan removes $s$ , then Sam can remove 13 and the least two of the remaining small primes. (The product of Sam's integers is at most $3 \cdot 5 \cdot 13 < 199$ , so this move is allowed.) The two remaining small primes will be from among 5, 7, and 11, and the least remaining non-small prime will be 17.
• If Dan removes $z$ , then Sam can remove 2, 3, and 5. The remaining small primes will be 7 and 11, and the least non-small prime will be 13 or 17.
• If Dan removes $s\,s$ , then Sam can remove the least remaining small prime and 13. (The product of Sam's integers is at most $5 \cdot 13 < 199$ , so this move is allowed.) The remaining small primes will be from among 3, 5, 7, and 11, and the least remaining non-small prime will be 17.
• If Dan removes $s\,z$ , then Sam can remove the least two of the remaining small primes. (The product of Sam's integers is at most $3 \cdot 5 < 199$ , so this move is allowed.) The remaining small primes will be from among 5, 7, and 11 and the least remaining non-small prime will be 13 or 17.
• If Dan removes $s\,s\,s$ , then Sam can remove 13. Since the product of the three small primes that Dan removes is less than 199, the product of the remaining small primes will be more than $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 / 199 \approx 11.6$ , which is to say that the product of the remaining small primes will be at least 12. The least remaining non-small prime will be 17.
• If Dan removes $s\,s\,z$ , then Sam can remove the least remaining small prime. Since the non-small prime that Dan removes is at least 13, the product of the two small primes Dan removes is at most $199 / 13 \approx 15.3$ , which is only possible if Dan removes two small primes from among 2, 3, and 5. After Sam plays, the remaining small primes will be 7 and 11, and the least remaining non-small prime will be 13 or 17.

In each of these cases, we can tell by examining the remaining small primes and least remaining non-small prime that conditions (a) and (b) are met. This means Dan (the first player) is in a losing position, so when $N = 199$ , Sam (the second player) has a winning strategy.

We are asked to find the largest value of $N$ less than or equal to 200 for which the second player has a winning strategy. We will show that the first player has a winning strategy when $N = 200$ . There are 44 primes less than and coprime to 200, so in the simplified gameplay, there are 45 integers on the list, the 44 primes and the integer 1. The three small primes on the list are 3, 7, and 11. $\begin{matrix} s & z & z & \cdots & z & z \\ s & s & z & \cdots & z \end{matrix}$ If the first player removes 3 (i.e., removes $s$ ) then the second player will be in position (2) with conditions (a) and (b) met and thus will be in a losing position. Therefore, when $N \leq 200$ , the largest value of $N$ for which the second player has a winning strategy is $\boxed{n = 199}$ .