4
$\begingroup$

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.

  • 0
    Just emphasize he has only 1 chance compared to Bob (3).2012-07-23

1 Answers 1

8

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.)

  • 0
    Nice. Looks like a useful technique for some subtraction games.2018-04-12