Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Why is Alice's name in quotation marks but Bob's isn't? –  Qiaochu Yuan Jul 23 '12 at 2:11
    
Just emphasize he has only 1 chance compared to Bob (3). –  Chan Jul 23 '12 at 2:14

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
The Sprague-Grundy theorem tells us that $N=4n+k$ is a nim-heap of $k-1 \pmod 4$. You are right that all primes above $3$ don't matter in this game. –  Ross Millikan Jul 23 '12 at 2:37
    
@Denocourt: Thanks a lot. –  Chan Jul 23 '12 at 17:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.