Mock AIME I 2012 Problems/Problem 13
Eduardo and Silvie play the Factor Game. Eduardo initially picks a number ; Silvie then subtracts a factor of from to get . Eduardo then subtracts a factor of from to get and so on. Neither player is allowed to subtract 1 at any time. The loser is the person who must subtract a number from itself and get zero. Let be the set of all positive integers less than 1000 which Eduardo can choose as the initial number to ensure that he wins (assuming optimal play). Find the remainder when the sum of the elements of is divided by 1000.
We claim that under optimal play, the first player wins if she chooses any odd number or any number of the form for integer , while she loses if she chooses any even number not of the form . In the rest of this proof, "first player" means "first player to move in the given position" (which, at the start of the game, reverses the sense of the words in the question).
The proof is by induction. It's easy to check the result for as many base cases as you like. Suppose the result is true for all . We wish to show that it is true for as well.
If is odd, all factors of are odd. Moreover, for any factor of we have and so is even but not a power of . By induction, all such positions are wins for the starting player, in this case the second player.
If is even but not a power of , has an odd factor . Thus the first player may move to , an odd number, and win.
If for some integer , the available moves are to even numbers other than powers of and to . Since even numbers other than powers of are losing moves, the first player wins from if and only if the second player wins from .
These three cases complete the induction.
Thus the sum is .