# Nim Sum Game Variant

Suppose there are black and white balls in a box. The initial number of white balls is m and the initial number of black balls is n. This is a two player game. Each player can do the following taking turns:

1) Remove as many balls (>0) of the same color.
2) Remove an equal number of white and black balls.

The player who takes the last ball wins.

Devise a winning strategy for the first play if one exists.

• Is the winner the person to take the last ball? – Milo Brandt Oct 4 '14 at 18:23
• @Meelo Yes. I have updated the question with this information. – ibp73 Oct 4 '14 at 18:28

I will define sequences $a_n$, and $b_n$ as following.

$$a_1=1, b_1=2$$ $$b_n - a_n = n$$ $$a_n = min(\mathbb{N} - \left \{a_1, \cdots, a_{n-1}, b_1, \cdots, b_{n-1} \right \})$$

The winning strategy for player A is to remove balls satisfying the next conditions at every A's turn;

(the number of black balls after removing, the number of white balls after removing) = $(a_n, b_n)$ or $(b_n,a_n)$ for some $n \in \mathbb{N}$

Then at the player B's turn, B got the given number of balls. By repeating this finite times, at B's turn, (the number of black balls, the number of white balls) should be $(a_1, b_1) = (1,2)$ or $(b_1, a_1) =(2,1)$.

$(1,2)$ case, the player B should remove 1 black ball / 1 white ball / 2 white ball / 1 black and 1 white ball, then A can win by removing 2 white balls / 1 black and 1 white ball / 1 black ball / 1 white ball.

$(2,1)$ case is similar.

The rest thing is to check that it is a possible strategy. In other words, one should show that the player A could remove balls following the strategy. The first player A makes the situation unless the initial numbers of black and white balls satisfies the conditions, i.e.(the initial number of black balls, the initial number of white balls) = $(a_n, b_n)$ or $(b_n, a_n)$. In this case, if the player B follows the given strategy, the player A couldn't win because of the following arguments. But if not, A can follow the strategy at the first time.

Now let assume that this is B's turn, and the number of balls after removing A is $(a_n, b_n)$. After the other player B remove the balls, the number of balls should be one of the followings;

$(a_n - k, b_n)$, $(a_n, b_n - k)$, $(a_n - k , b_n -k)$

Case 1: the number of balls $= (a_n - k, b_n)$

By definition of $a_n$, there is a natural number $m$ such that $m < n$, and $a_n-k=a_m$ or $a_n - k =b_m$.

If $a_n-k=a_m$, remove $n+k-m$ white balls.($n>m$) Then the number of white balls is $b_n - n - k +m = a_n -k +m = a_m +m = b_m$. $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (a_m, b_m)$$

If $a_n - k =b_m$, remove $n+k+m$ white balls. Then the number of white balls is $b_n - n - k - m = a_n - k -m = b_m-m = a_m$, $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (b_m, a_m)$$

Case 2 : the number of balls $= (a_n , b_n - k)$

If $k<n$, remove $a_n - a_{n-k}$ black and white balls. $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (a_n - (a_n - a_{n-k}) , b_n - k - (a_n - a_{n-k})) = (a_{n-k} , a_{n-k} + n-k) = (a_{n-k} , b_{n-k})$$

If $k = n$, by removing $a_n$ black and white balls, A can win.

If $k > n$, $b_n - k < b_n - n = a_n$. So there is a nature number $m$, s.t. $m<n$, and $b_n - k = b_m$ or $b_n - k = a_m$. For the case of $b_n - k = b_m$, remove $k-n+m$ black balls. Then the number of black balls after removing is $a_n - k + n - m = b_n - k - m = b_m - m = a_m$ $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (a_m , b_m)$$ For the case of $b_n - k = a_m$, we should consider two possibilities, $b_m > a_n$, $b_m < a_n$

At the first, $0 < t = a_n - a_m < b_m -a_m = m$. By subtracting $a_m - a_t$ black and white balls, we get $a_n - a_m + a_t = t + a_t = b_t$ black balls, and $b_n - k - a_m +a_t = a_m - a_m + a_t = a_t$ white balls. $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (b_t , a_t)$$ At the second, remove $a_n - b_m$ black balls, then the number of black balls should be $a_n - a_n + b_m = b_m$. $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (b_m , a_m)$$

Case 3 : the number of balls = $(a_n - k , b_n -k)$

By definition of $a_n$, there is a natural number $m$ such that $m < n$, and $a_n-k=a_m$ or $a_n - k =b_m$.

If $a_n-k=a_m$, $b_n - k - b_m = a_n + n - k - a_m -m = a_m + n - a_m - m = n - m >0$. Subtract $b_n - k - b_m$ white balls, then the number of white balls is $b_n - k - (b_n - k - b_m) = b_m$ $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (a_m , b_m)$$

If $a_n-k=b_m$, $b_n - k - a_m = a_n + n - k - a_m = b_m + n - a_m = n + m >0$. Subtract $b_n - k - a_m$ white balls then the number of white balls is $b_n - k -(b_n - k - a_m )= a_m$ $$(\textrm{number of black balls after removing by A, number of white balls after removing by A}) = (b_m , a_m)$$

• Thank you so much. The solution works for the game. I was however wondering how you came up with the series so quickly and how much time it took you to solve it. A little insight into how you arrived at the strategy would be awesome. Thanks again for all the help. – ibp73 Oct 5 '14 at 9:56
• I get the logic behind starting out at (1,2) but I fail to understand what caused you to try $b_n$ - $a_n$ = n. – ibp73 Oct 5 '14 at 10:02
• @ibp73, my approach is to consider this game on the (x,y)-plane. The x-coordinate means the number of black ball, and the y-coordinate meant the number of white ball. At the player A's turn, he can win if he is on x=0, y=0, or x=y. And if the player B is on (1,2) or (2,1), he should go to the given position. After that, repeat the same logic. If A is on x=1, y=2, y=x+1, then A can go to (1,2), and for (2,1) we can find the similar conditions. – a-- Oct 5 '14 at 18:27