Beat your Friend at Subtraction!

You and your friend are playing a game. The game goes as follows:

  • At the start, you are given a positive integer NN.
  • You choose a positive factor nn of NN, where nNn \neq N.
  • You compute NnN - n and give the result to your friend.
  • Your friend repeats the above procedure with the integer she is given and gives the result to you, and so forth.

For example, if you are given N=12,N = 12, you can choose n=3n = 3 and give Nn=9N - n = 9 to your friend. Then, N=9N = 9.

Play continues in this fashion until one person is given N=1N = 1, at which point that person loses.

Given that you and your friend will both play optimally, how many positive integers N2015N \leq 2015 are there such that, when given at the start, you will always win?

Problem source: ASMT 2015 Team #3

Problem Loading...

Note Loading...

Set Loading...