1
$\begingroup$

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.

  • 0
    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).2011-04-24

4 Answers 4

4

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?

2

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.

1

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?

1

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.