Problem
Alice and Bob play the following game.They choose a number N to play
with.The runs are as follows :
1.Bob plays first and the two players alternate.
2.In his/her turn ,a player can subtract from $N$ any prime number less than $N$ or the number 1. The result thus obtained is the new $N$.
3.The person who cannot make a move in his/her turn loses the game.
Assuming both play optimally, who wins the game?
The answer is if $N \equiv 1 \pmod{4}$, then "Alice" will win, otherwise Bob. But I couldn't prove it mathematically correct. The way I obtain this answer is just bruteforce for some particular $N$. I noticed several rules but I just can't find a way to deduce from there. Here is what I have:
If $N = P + 1$, where $P$ is prime, then whoever take this turn will win.
If $N = 5$, then whoever takes this turn will lose.
The biggest problem I'm facing is primes because there is no general rule to generate one. I wonder could anyone shed me some light on this problem? Any suggestion would be greatly appreciated.
Best Answer
It sounds like the key point is that you can subtract $1$, $2$, or $3$, but nothing equivalent to $0$ mod 4. (In other words, the primes are a distraction.)
Thus, if $N \not\equiv 1$ (mod 4), Bob can subtract either $1$, $2$, or $3$ from $N$ so that $N' \equiv 1$ (mod 4), where $N'$ is the new $N$. However, if $N \equiv 1$ (mod 4), then Bob is forced to make $N' \not\equiv 1$, and Alice can reply by making the next number equivalent to 1 (mod 4).
(I'm assuming that the endgame is such that if you start with $N = 1$, you lose.)