# two elementary games in number theory

I solved these two problems from a programming challenge website: numgame and numgame2.

These two problems are very similar. In the first one, the position is a number $n$ and each player can subtract from $n$ a divisor $d$ of $n$ with $1 \leq d < n$. Players Alice and Bob alternate with Alice going first and the first person unable to move loses. The second problem is similar except each player can subtract a prime number $p$, or 1, from the current position $n$, with $p < n$ ($p$ is not necessarily a divisor of $n$). We assume that the players play optimally and, as usual, ask who the winner is given the initial value of $n$.

The claim is that in the first game Alice wins if $n \equiv 0 \pmod{2}$ and Bob wins if $n \equiv 1 \pmod{2}$, while in the second game Alice wins if $n \equiv 1 \pmod{4}$ and Bob wins otherwise.

I'm looking for someone to give me a proof of these answers, or some hints to start.

-
If possible, please add into the question the rules of the games, and not just a link and a jumbled explanation. –  Asaf Karagila Apr 23 '11 at 10:50
In particular the rules include that two players Alice and Bob alternate. While the first game (numgame) has Alice play first, the second game (numgame2) requires Bob to play first. In both games a player loses if no valid move is available at their turn, i.e. if the remaining number is 1. –  hardmath Apr 23 '11 at 11:14
In the first problem the player who starts with a prime number loses, not necessarily 1. –  Vicfred Apr 23 '11 at 11:23
Because the rules of the first game allow for a proper divisor, if the player Alice starts with n = 2 (a prime), she has a valid move in taking away 1, leaving Bob with a losing position. Apart from that, of course, primes are odd and thus illustrate the claimed classification of outcomes for the first game (n odd gives Bob a win). –  hardmath Apr 24 '11 at 10:39

## 4 Answers

Hint for the first problem: If the current position $n$ is even and it's Alice's turn, can she always make a move into an odd position? If the current position $n>1$ is odd and it's Bob's turn, what can you prove about the parity of the position he must move into?

-

Second Problem:

Bob can never change a number of the form $4k+1$ into a number of the same form (primes and 1 tend to be not divisible by 4).

Alice can always change a number not of this form into a number of this form by substracting 1,2 or 3 as needed.

-

Hint for the first problem: Who wins if $n=2$, who wins if $n=1$? If $n$ is even, can Alice assure that after 2 turns (one turn by Alice and one by Bob) the number is still even?

-

1st Game

1) let n = value of current position.

2) n = 1 x n, so n is always divisible by 1

3) if n is even, Alice can always subtract 1 leaving Bob with odd value n

4) an odd number has no even divisors since if n/2a = b, then n = 2ab and is even.

5) if n is odd, Bob must always leave Alice with an even value n since all divisors are odd and he must subtract an odd number from n, while the difference between 2 odd numbers must always be even ((2x+1)-(2y+1) = 2(x-y)).

6) thus, by 3) & 5) with each subsequent pair of turns, Alice can always leave Bob with a smaller odd number position n.

7) This strategy leads to a descent that eventually must leave Bob with the odd position n = 1, and he loses. The descent could be hastened by Alice if she chose the largest odd divisor to subtract instead of 1 (which is the smallest) when it was her turn.

-