Beat your Friend at Subtraction!

Number Theory Level 5

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

  • At the start, you are given a positive integer \(N\).
  • You choose a positive factor \(n\) of \(N\), where \(n \neq N\).
  • You compute \(N - 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,\) you can choose \(n = 3\) and give \(N - n = 9\) to your friend. Then, \(N = 9\).

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

Given that you and your friend will both play optimally, how many positive integers \(N \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...