Divisor Take-Away Game

[BMAD]

Here's the game: the first player picks an integer n > 1 , then the second player subtracts a proper divisor d < n of that number, telling the first player the difference n - d , then the first player subtracts a proper divisor of that new number, etc. The player who announces a difference of 1 is the winner. Does either player have a winning strategy? If not explain why not; if so, which player is it, does it depend on n, and what's the strategy?

note: A positive proper divisor is a positive divisor of a number n, excluding n itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.

[Rainman]

First player wins easily. He picks the number n=3, forcing the second player to subtract d=1 and announce n-d=2. Then the first player subtracts 1 from 2, announcing a difference of 1. It does heavily depend on n though, if the first player were to pick n=2 he would be cooked.

[BMAD]

What if player 2 picks their own number and chooses d?

[gavinksong]

Rainman is a sniper!

Edited July 30, 2013 by gavinksong

[plasmid]

If you start with the number 2, then whoever subtracts a number first will clearly win. Rainman showed that if you start with the number 3, then whoever subtracts a number first will lose. For cases where N>3:

If N is odd, then all divisors of N must also be odd. So if you face an odd N, you must subtract an odd number and leave your opponent with an even N. Because the goal is to get to 1 which is odd, you cannot win directly from N if N is odd.

If N is even, you can subtract 1 to make it an odd number. That means your opponent can't win on the following move and must leave you with an even number on your next turn, at which point you can subtract 1 again (or any other odd divisor if there is one) to keep leaving your opponent with an odd number from which they can't win. N will keep decreasing until you get a 2 and win.

So if N is odd then the player currently taking a turn will lose, and if N is even then the player currently taking a turn will win.

Edited July 31, 2013 by plasmid