0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ibp73 Oct 5 '14 at 9:56
  • $\begingroup$ 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. $\endgroup$ – ibp73 Oct 5 '14 at 10:02
  • $\begingroup$ @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. $\endgroup$ – a-- Oct 5 '14 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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