Game theory: Given a number N, decide the winner.

Question

Given a number $N$:

• Two people A and B subtracts a number k $\left(~0 < k < N,\ k\mid N~\right)$ alternatively from $N$.
• The one who cannot make a move loses the game.Provided that A always starts first, decide the winner.

Initially, I tried solving this problem using dynamic programming considering the fact that a state can be a winning one if it leads to at least one losing state. Also, a state is a losing one if all the states it goes to are winning. Checking for all the states didn't prove to be time efficient. After looking at the solutions I found that this problem boils down to checking whether N is odd or even. What I think is, one can say that if a state X is losing then $\mathbf{X + 1}$ $\left(\,\mbox{as}\ \mathbf{1\mid\left(\,X + 1\,\right)}\,\right)$ will always be a winning state but what if $\mathbf{X}$ is a winning state ?.

How can one prove that even states will always be winning and vice versa ?.

Answer 1

Note a few things:

1) If you are passed an even number, you can not be made to lose in that turn.

This is because $N = 2m > 1$ and $1|N$ so you can pass $N -1$.

2) If you are passed an odd number, then either a) you are forced to lose if $N =1$ or b) you are forced to pass an even number. And your opponent cannot be made to lose in the next turn.

a) if $N =1$ you can't do anything.

b) if $N > 1$ but $N$ is odd so if $k|N$ then $k$ is odd and you must pass $N -k$ which is an odd minus an odd must be even.

3) if you are passed an even you can make it so that you are passed an even the next turn (if there is a next turn).

Just pass the $N-1$. That will be odd and your opponent must pass you an even by 2). (or the opponent must lose if you passed a $1$). [If you have a larger odd $k$ that divides $N$ you can pass $N -k$ which will also be odd. That will speed the game up.]

4) The game is finite and must end.

You are passed a finite $N$ and you pass an $1 \le N - k < N$ that is smaller. There are only a finite number (maximum $N$) turns that can be taken.

...... so ......

So if you are passed an even you need not lose that turn or, by induction, any other turn. If you are passed an odd you might lose but you can not make your opponent lose. All games must end.

Therefore (if both players play the best strategy) player $A$ will lose if the first $N$ is odd. Player $A$ will win if the first $N$ is even.

Answer 2

Let $n=2^a\cdot d$ where $d$ is an odd number. We have two cases.

1) If $a>0$ then $n$ is even and if the player subtracts $0< d<n$ (or any divisor of $d$) then we obtain $n-d=(2^a-1)\cdot d$ which is odd.

2) If $a=0$ then $n$ is odd and any divisor $k$ is odd too. So for any move $0<k<n$ the new number $n-k$ is even.

Therefore we may conclude that the initial number $N$ is winning for the first player if and only if $N$ is even.

Answer 3

From an even state, you can always get to an odd state (by subtracting $1$), but from an odd state you can only get to an even state, because the only divisors of an odd number are odd, and odd minus odd is even. (The game ends at the odd number $1$, since there is no integer $k$ between $0$ and $1$.)

Remark: For a nontrivial variant, you might take a look at a game I came up with some years ago which, for lack of a better name, I call Factor Subtractor. The sequence of starting numbers for which there is a winning opening move has no apparent regularity.

Answer 4

If $N=2$, then the second player, B wins the game.

---

---

Lets set some notations. Given $N$ as described above. Let $a_1=N$.

First state:

Assume that A chooses in the first state $\alpha_1$. Then let $b_1:=a_1-\alpha_1$. Assume that B chooses in the first state $\beta_1$. Then let $a_2:=b_1-\beta_1$.

Second state:

Assume that A chooses in the second state $\alpha_2$. Then let $b_2:=a_2-\alpha_2$. Assume that B chooses in the second state $\beta_2$. Then let $a_3:=b_2-\beta_2$.

....... .......

$i$-th state:

Assume that A chooses in the $i$-th state $\alpha_i$. Then let $b_i:=a_i-\alpha_i$. Assume that B chooses in the $i$-th state $\beta_i$. Then let $a_{i+1}:=b_i-\beta_i$.

---

---

In all other cases, i.e., $2 \leq N$, the first player, A wins the game.

Let $k$ be the least natural number, which does'nt divides $N$, i.e.

$k:=min\{n \in \mathbb{N} : N-1 \geq n \nmid N \}$.

The strategy for the first player in the $i$-th state, is to choose the unique element $\alpha_i \in \{1, 2, 3, ..., k-2, k-1\}$ such that $b_i:=a_i-\alpha_i$ is divisible by $k$.

---

---

Let $k$ be the least natural number, which does'nt divides $N$, i.e.

$k:=min\{n \in \mathbb{N} : N-1 \geq n \nmid N \}$.

[Notice that the set $\{n \in \mathbb{N} : n \nmid N \}$ is not empty.

Notice that $N-1 \nmid N$, since N is greater than $1$.]

Also notice that for every $t \in \{1, 2, 3, ..., k-2, k-1\}$ we have that:

$t\mid N$, by definition.

---

---

In $i$-th state the first player, A subtracts

the unique element $\alpha_i \in \{1, 2, 3, ..., k-2, k-1\}$;

such that $b_i:=a_i-\alpha_i$ is divisible by $k$.

[By the euclid's algorithm, A can be able to do such a move.]

---

---

Now it's the second player turn.

We claim that B could not win.

Suppose on contrary that B could win, so he/she must choose the whole remaining number; i.e. $b-i$

which means that the remaining number $b_i$ divides $N$.

On the other hand, $k \mid b_i$; since A makes the remaining number divisible by $k$.

So we have: $k \mid b_i \mid N$,

so by the property of transitivity of division we have

that $k \mid N$, which contradicts the definition of $k$.

---

---

Example

$N=60$.

In this case $k:=7$ is the least number which does not divides $60$.

The remainder of $a_1=60$ by $7$; is equal to $4$, so A subtracts $4$, and $56=b_1=a_1-\alpha_1=60-4$ is divisible by $7$.

Now it is the second player's turn for example he chooses $15$, $41=a_2=b_1-\beta_1=56-15$ has the remainder equal to $6$ module $7$, so A subtracts $6$, and $35=b_2=a_2-\alpha_2=41-6$ is divisible by $7$.

Now again, it is the second player's turn for example he chooses $5$, $30=a_3=b_2-\beta_2=35-5$ has the remainder equal to $2$ module $7$, so A subtracts $2$, and $28=b_3=a_3-\alpha_3=30-2$ is divisible by $7$.

Now again, it is the second player's turn for example he chooses $20$, $8=a_4=b_3-\beta_3=28-20$ has the remainder equal to $1$ module $7$, so A subtracts 1, and $7=b_4=a_4-\alpha_4=8-1$ is divisible by $7$.

Now again, it is the second player's turn for example he chooses $2$, $5=a_5=b_4-\beta_4=7-2$ has the remainder equal to $5$ module $7$, so A subtracts $5$; $0=b_5=a_5-\alpha_5=5-5$, and he wins the game.

Notice that every integer like $a$ which is divisible by $7$ could not divide $60$, since $7$ does not divides $60$.