Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Mock AIME I 2012 Problems/Problem 13

Problem

Eduardo and Silvie play the Factor Game. Eduardo initially picks a number $N$; Silvie then subtracts a factor of $N$ from $N$ to get $N'$. Eduardo then subtracts a factor of $N'$ from $N'$ to get $N''$ 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 $S$ be the set of all positive integers less than 1000 which Eduardo can choose as the initial number $N$ to ensure that he wins (assuming optimal play). Find the remainder when the sum of the elements of $S$ is divided by 1000.

Solution

We claim that under optimal play, the first player wins if she chooses any odd number or any number of the form $2^{2k + 1}$ for integer $k$, while she loses if she chooses any even number not of the form $2^{2k + 1}$. 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 $m < n$. We wish to show that it is true for $n$ as well.

If $n$ is odd, all factors of $n$ are odd. Moreover, for any factor $p > 1$ of $n$ we have $p \mid n - p$ and so $n - p$ is even but not a power of $2$. By induction, all such positions are wins for the starting player, in this case the second player.

If $n$ is even but not a power of $2$, $n$ has an odd factor $p > 1$. Thus the first player may move to $n - p$, an odd number, and win.

If $n = 2^k$ for some integer $k$, the available moves are to even numbers other than powers of $2$ and to $2^{k - 1}$. Since even numbers other than powers of $2$ are losing moves, the first player wins from $2^k$ if and only if the second player wins from $2^{k - 1}$.

These three cases complete the induction.

Thus the sum is $\left(\sum_{k=1}^{499} 2k+1 \right) + \left(\sum_{k=0}^{4} 2^{2k+1} \right) \mod 1000 = \boxed{681}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_I_2012_Problems/Problem_13&oldid=46189"