Editorialist: SUSHANT AGARWAL
Basic Number Theory.You can also browse through the chapter “Games” from the book “Mathematical Circles” by Fomin,Genkin,Itenberg for an idea on how to solve simlar problems.
Let us look at small examples first and then try and figure out how to solve the problem.This following table represents Whether you will win or lose if you are on the given number and it is your chance to play.
It seems that if N is an Even number then Alice wins otherwise Bob wins.This is indeed True.
Strategy to be followed :- If you are on an Even number,subtract 1 from the number.The opponent will then have an Odd number.All factors of odd numbers are Odd.Hence he can only subtract an Odd number.Hence you will have an even number on your turn.Keep following the same strategy.What will remain “Invariant” is that you will always have an even number and the opponent will have an odd number.This process will keep continuing until you reach one the numbers between 1 and 8,for which the results are listed above.
Editorialist’s solution can be found here.