Coprime Game I

Let \( N \ge 2 \) be a positive integer. Dan and Sam play the following coprime game: starting with the set \( C_N \) of coprime positive integers of \( N\) that are less than \( N\), the players take turns removing some elements from the set. At a player's turn, he chooses a number \( m\) that remains, and removes \(m \) and any integer that is not coprime of \(m \) that remains. The player who moves last loses.

For example: \( N =7, C_N = \{ 1,2,3,4,5,6\} \). Dan chooses \( m=6 \), so he removes \( 2 \), \(4\), \(3\) and \( 6 \). The remaining set is \( \{1,5\} \). Sam chooses \( m=5 \). The remaining set is \( \{1\} \). Dan is forced to take \( 1\), so he loses.

Let \( n \ge 2 \) be the largest positive integer \( \le 200 \) such that if Dan and Sam play the divisor game for \( n \) and both of them play optimally, the second player wins. Find \( n \). If no such \( n \) exists, enter \(1\).


Inspiration.

This is the eighteenth problem of the set Winning Strategies.
×

Problem Loading...

Note Loading...

Set Loading...