SRM 575 div 1

250, had some idea but could not finish. Submitted an obviously faulty version.

The problem is a game, given integer C, in each move you can subtract d from C such that d is a divisor of C and 1 < d < C. The player cannot make a move loses.

To start, make a table for C = 1 to 16, and this gives some idea.

if C is 2^k, then 2 is LOSE, 4 is WIN, 8 is LOSE, 16 is WIN. So a guess is that 2^k is LOSE if k is odd and is WIN if k is even.

and all odd numbers are LOSE, 1, 3, 5, 7, ...
and other numbers, 2^k * l for odd l > 1 are WIN.

If you have gone this far, an induction proof is all you need, and that's easy.

if C is 2^k, for even k you can make a move to 2^(k-1) which is an odd power of 2 and a LOSE, so you must be in WIN. For odd k we need to show every move leads to WIN. You possible moves are 2^l for some l >= 1, and C - 2^l = 2^k - 2^l = 2^l (2^(k-l) - 1), so it is  of the form 2^l * odd, and that is a WIN.

if C is odd, then we need to show every move leads to WIN.  An odd C can only have odd divisor d and d must be greater than 1, less than C. so C - d is even, and since d also divides C - d, the number C - d must be of the form 2^l * odd, and hence a WIN.

if C is 2^l * odd for l >= 1, then we need to find a move to LOSE. And that was easy. Let C = 2^l * d, for some odd d, then C - d = 2^l * d - d = d * (2^l - 1). The product of two odd numbers must be odd, and odd is LOSE.

We are now complete in the induction proof.