Player 1 attempting for a common factor

In the case where Player 1 is trying to force the last two numbers to have a common factor, there are two main classes of games to consider - whether $N$, the starting number of values, is even or odd.¹ In the case where it is even, Player 2 can always force a win by using the following strategy:

• Break the set of numbers into consecutive pairs
• Every time Player 1 removes a number, remove it's pair from the previous step

By following this strategy, the last 2 numbers will be $(x, x+1)$ for some value of $x$ such that $A \leq x < B$. It is very simple to show (for example, using the Euclidean Algorithm) that the GCD of these two numbers is 1, therefore, they are coprime. As an example consider the sequence 24, 25, 26, 27, 28, 29. This would be broken up into ( 24, 25 ), ( 26, 27 ) and ( 28, 29 ). If Player 1 removes 25, Player 2 removes 24, etc...

If the $N$ is odd, things are not quite so clear cut. For small $N$, Player 2 can generally still force a win, but we will now proceed to show that if $N$ is large enough, and odd, Player 1 can force a win.

Observation 1: If there are an odd number of values to start with, then on Player 1's turn, there will always be an odd number to choose from, and on Player 2's turn there will always be an even number.

Observation 2: If on Player 1's turn, there are exactly three numbers left, and there is either a pair congruent to 0 mod 2 (even) or congruent to 3 mod 6, then he can win by taking the number that's not part of the pair. This is because any two numbers that are even, or are odd but divisible by 3 have a common factor.

This leads to the following:

Theorem: Assume that Player 1 is trying to force the last two numbers to have a common factor. If Player 1 has enough turns to remove all values congruent to 1 and 5 mod 6, and leave at least 4 values remaining (i.e. have at least one additional turn), he can force a win.

Proof: All numbers that aren't congruent to 1 or 5 mod 6 are either even, or are congruent to 3 mod 6. Since there are at least 4 values remaining, Player 1 will at some point have a turn where there are exactly 3 numbers left (since he gets all of the odd turns). Since there are 3 numbers left, but only two categories, there must be a pair that are either congruent mod 2 or congruent mod 3, so Player 1 can simply remove the value that isn't part of the pair to win.

So the question is, for what values of $N$ does Player 1 have enough turns to satisfy the above requirements? A rough answer can be given as follows, and will provide a clue as to how to find the exact answer:

In any set of $N$ consecutive numbers, the maximum number of values that can be congruent to 1 or 5 mod 6 are $2\times \lfloor\frac{N}{6}\rfloor + 2$. If $N \equiv 0 \bmod 6$, then there are exactly N/3 values that are congruent to 1 or 5 mod 6. However, if N is not divisible by 6, then at most 2 additional values will also be congruent to 1 or 5. An equivalent way of writing $\lfloor\frac{N}{6}\rfloor$ is $\frac{N - N \bmod 6}{6}$. Since we're only considering cases where $N$ is odd, Player 1 has exactly $\frac{N-1}{2}$ turns. To meet the criteria of the theorem, Player 1 has to remove all of the numbers congruent to 1 or 5 mod 6 and still have 1 turn left over, thefore we want:

$$2 \times \frac{N - N \bmod 6}{6} + 2 + 1 \leq \frac{N-1}{2}.$$

$$\frac{N- N \bmod 6}{3} + 3 \leq \frac{N-1}{2}$$

$$2N - 2N \bmod 6 + 18 \leq 3N -3$$

$$21 - 2N \bmod 6 \leq N$$

Since we're trying to find a lower bound for $N$, we want to maximize the left side of the equation, which occurs when $2N \bmod 6 = 0$. Therefore, $21 \leq N$.As we will see in the specific cases, this particular situation will never occur, but that can't be demonstrated without more information about the specific numbers involved and this at least shows that a bound for $N$ does exist. Thus, if $N \geq 21$ and $N \equiv 1 \bmod 2$, Player 1 can force a win by removing all of the numbers congruent to 1 and 5 mod 6.

Next we will see how to get a better bound for $N$, and then look at the cases where $N$ is too small to be covered by the above theorem. When counting the number of values congruent to 1 or 5 mod 6, there are two factors that influence this number - $N_{0} \bmod 6$ and $N \bmod 6$. Since there are 6 possible values for $N_{0} \bmod 6$ and 3 possible values for $N \bmod 6$, there are 18 cases we need to consider. However, we can cut that number in half by the following theorem:

Theorem: Suppose that Player 1 is trying to force the last two numbers to have a common factor. If $N$ is odd and and $N_{0}$ is even, then Player 1 can force a win by removing only odd numbers.

Proof: Since $N_{0}$ is even, there are $\frac{N+1}{2}$ even numbers in play, and $\frac{N-1}{2}$ odd numbers. Since Player 1 has $\frac{N-1}{2}$ turns, he can simply remove an odd number each turn. However, Player 2 only has $\frac{N-3}{2}$ turns. Therefore, if on every turn Player 2 removes an even number, there will still be 2 even numbers remaining, which by definition have 2 as a common factor. If instead, Player 2 removes at least one odd number, Player 1 can continue to remove odd numbers until none are remaining, at which point all remaining numbers will have 2 as a common factor and Player 1 will still win.

This leaves only 3 classes to consider - when $N_{0} \equiv 1,3, \mathrm{or} 5 \bmod 6$. We will look at the first of these in depth to get an understanding of how to determine a bound for $N$, and then simply present the rest of the equations and solutions without tedious explanations.

Recall from above that we want to have the number of values congruent to 1 and 5 mod 6, plus 1 for the extra turn, be less than or equal to the number of Player 1's turns. If $N_{0} \equiv 1 \bmod 6$, then the first 6 numbers are:

$$\stackrel{1}{N_{0}} \stackrel{2}{N_{1}} \stackrel{3}{N_{2}} \stackrel{4}{N_{3}} \stackrel{5}{N_{4}} \stackrel{0}{N_{5}}.$$

We now consider each case where $N \equiv 1, 3, \mathrm{and} 5 \bmod 6$ separately. If $N \equiv 1 \bmod 6$, then there are $\frac{N-1}{6}$ complete ''sets'' of 6's. Since each set contains one value congruent to 1 mod 6 and one value congruent to 5 mod 6, there are $2 \times \frac{N-1}{6}$, or $\frac{N-1}{3}$ 1's and 5's from the complete sets. However, since we know that $N \equiv 1 \bmod 6$, there is one number left that's not part of a complete set. Furthermore, since $N_{0} \equiv 1 \bmod 6$, we know that number is congruent to 1 mod 6. Therefore, the exact number of values congruent to 1 or 5 mod 6 in this case is: $\frac{N-1}{3} + 1$. Now that we have this, we can plug it back into our original formula- Number of 1's and 5's mod 6 + 1 extra turn $\leq$ Number of Player 1 turns:

$$\frac{N-1}{3} + 1 + 1 \leq \frac{N-1}{2}$$

$$2N - 2 + 12 \leq 3N - 3$$

$$2N - 2 + 15 \leq 3N$$

$$13 \leq N$$

Thus, in the particular case where $N_{0} \equiv 1 \bmod 6$ and $N \equiv 1 \bmod 6$, if $N \geq 13$, then Player 1 can force a win by using the strategy from the theorem.

Next, we look at the case where $N \equiv 3 \bmod 6$. This time, there are $\frac{N-3}{6}$ complete sets, and $\frac{N-3}{3}$ 1's and 5's from them. However, even though there are now 3 numbers outside of the complete sets, they're congruent to 1,2 and 3 mod 6, so there's still only 1 additional 1 or 5 outside of the set. Thus:

$$\frac{N-3}{3} + 1 + 1 \leq \frac{N-1}{2}$$

$$2N - 6 + 12 \leq 3N -3$$

$$9 \leq N$$

Finally, we can look at the case where $N \equiv 5 \bmod 6$. In this case, there are $\frac{N-5}{6}$ complete sets, but there are now 2 numbers congruent to 1 or 5 outside the complete set, since the last value is now congruent to 5 mod 6. Therefore:

$$\frac{N-5}{3} + 2 + 1 \leq \frac{N-1}{2}$$

$$2N - 10 + 18 \leq 3N - 3$$

$$11 \leq N$$

Hence, we can now say that in the case where $N_{0} \equiv 1 \bmod 6$, any odd value of $N \geq 9$ will allow Player 1 to force a win by removing all 1s and 5s.

Using the same methods as described above, we can calculate values of $N$ for the cases where $N_{0} \equiv 3 \bmod 6$ and where $N_{0} \equiv 5 \bmod 6$. These solutions are presented in Table 1.

Table 1: Minimum values for $N$ where Player 1 wants a common factor

$N_{0} \equiv 3 \bmod 6$	$N \equiv 1 \bmod 6$	$2 \times \frac{N-1}{6} + 1 \leq \frac{N-1}{2}$
		$2N -2 + 6 \leq 3N -3$
		$7 \leq N$
	$N \equiv 3 \bmod 6$	$2 \times \frac{N-3}{6} + 2 \leq \frac{N-1}{2}$
		$2N - 6 + 12 \leq 3N -3$
		$9 \leq N$
	$N \equiv 5 \bmod 6$	$2 \times \frac{N-5}{6} + 3 \leq \frac{N-1}{2}$
		$2N - 10 + 18 \leq 3N - 3$
		$11 \leq N$
$N_{0} \equiv 5 \bmod 6$	$N \equiv 1 \bmod 6$	$2 \times \frac{N-1}{6} + 2 \leq \frac{N-1}{2}$
		$2N - 2 + 12 \leq 3N - 3$
		$13 \leq N$
	$N \equiv 3 \bmod 6$	$2 \times \frac{N-3}{6} + 3 \leq \frac{N-1}{2}$
		$2N - 6 + 18 \leq 3N -3$
		$15 \leq N$
	$N \equiv 5 \bmod 6$	$2 \times \frac{N-5}{2} + 3 \leq \frac{N-1}{2}$
		$2N - 10 + 18 \leq 3N - 3$
		$11 \leq N$

Combining our previous results with the table above, we see that for any odd $N \geq 11$, Player 1 has enough turns to force a win by removing all of the 1's and 5's. However, what happens if $N < 11$? These cases have to be worked out by hand, but fortunately, most of them are very simple. Recall that our second theorem above held for all $N$, therefore, we only need to consider the cases where the first value is odd. Also recall that in all cases where $N$ is even, Player 2 wins. The remaining special senarios are presented in Table 2, with Player 2 forcing a win in all cases.

Table 2: Special cases for $N < 11$ where Player 1 wants a common factor

$N = 3$	$N_{0} \equiv 1 \bmod 6$
	$\stackrel{1}{N_{0}} \stackrel{2}{N_{1}} \stackrel{3}{N_{2}}$	Player 1 loses
	$N_{0} \equiv 3 \bmod 6$
	$\stackrel{3}{N_{0}} \stackrel{4}{N_{1}} \stackrel{5}{N_{2}}$	Player 1 loses
	$N_{0} \equiv 5 \bmod 6$
	$\stackrel{5}{N_{0}} \stackrel{0}{N_{1}} \stackrel{1}{N_{2}}$	Player 1 loses
$N = 5$	$N_{0} \equiv 1 \bmod 6$
	$\stackrel{1}{N_{0}} \stackrel{2}{N_{1}} \stackrel{3}{N_{2}} \stackrel{4}{N_{3}} \stackrel{5}{N_{4}}$	Player 2 removes $N_{1}$ or $N_{3}$
	$N_{0} \equiv 3 \bmod 6$
	$\stackrel{3}{N_{0}} \stackrel{4}{N_{1}} \stackrel{5}{N_{2}} \stackrel{0}{N_{3}} \stackrel{1}{N_{4}}$	Player 2 removes $N_{3}$
	$N_{0} \equiv 5 \bmod 6$
	$\stackrel{5}{N_{0}} \stackrel{0}{N_{1}} \stackrel{1}{N_{2}} \stackrel{2}{N_{3}} \stackrel{3}{N_{4}}$	Player 2 removes $N_{1}$
$N = 7$	$N_{0} \equiv 1 \bmod 6$
	$\stackrel{1}{N_{0}} \stackrel{2}{N_{1}} \stackrel{3}{N_{2}} \stackrel{4}{N_{3}} \stackrel{5}{N_{4}} \stackrel{0}{N_{5}} \stackrel{1}{N_{6}}$	Player 2 removes $N_{5}$, $N_{1}$
		( not $N_{3}$, because $N_{1} \equiv N_{6} \bmod 5$,
		so if $N_{6} \equiv 0 \bmod 5$,
		then $N_{1}$ and $N_{6}$ will have
		5 as a common factor. This is not
		explicitly stated in the remaining
		cases where it occurs)
	$N_{0} \equiv 5 \bmod 6$
	$\stackrel{5}{N_{0}} \stackrel{0}{N_{1}} \stackrel{1}{N_{2}} \stackrel{2}{N_{3}} \stackrel{3}{N_{4}} \stackrel{4}{N_{5}} \stackrel{5}{N_{6}}$	Player 2 removes $N_{1}, N_{5}$
$N = 9$	$N_{0} \equiv 5 \bmod 6$
	$\stackrel{5}{N_{0}} \stackrel{0}{N_{1}} \stackrel{1}{N_{2}} \stackrel{2}{N_{3}}... ...\stackrel{4}{N_{5}} \stackrel{5}{N_{6}} \stackrel{0}{N_{7}} \stackrel{1}{N_{8}}$	Player 2 removes $N_{1}$, $N_{7}$.
		If $N_{0} \equiv 0 \bmod 5$,
		remove $N_{5}$, else remove $N_{3}$.