There are 2 piles of coins, each containing 2010 pieces. Two players A and B play a game taking turns (A plays first). In each turn the player on play has to take 1 or more coins from 1 pile or exactly 1 coin from both piles. Whoever takes the last coin is the winner. Which player will win if both play in the best possible way? We represent the present state of a game as config.(a+b) which means there are "a" coins in one pile an "b" coins in the other pile. Now it can be easily seen that a (2+1) config is a losing one for the person to play. Similarly a (3+3) config is a losing one for the person to play. Hence a (4+4) is a winning config because the player will then draw 1 coin each from both pile and force the other to a losing config. (5+5) is also a winning config because then the player to play(say A) will draw 1 coin from one of the piles. Hence depending on the other player's move it will turn into a (4+4) for A or a (3+3) for B after the next chance. So how do I proceed?
[Math] Who’s winning this coin drawing game
game theory
Related Solutions
For $\ N=2\ $ it's fairly easy to tabulate the losing positions for the first player (i.e. $\ \mathcal{P}$-positions, or "safe" positions, according to the standard terminology), although I haven't found any simple expression for them. The first few are $\ \left\{1,2\right\}$, $\left\{3,5\right\}$, $\left\{4,7\right\}$, $\left\{6,10\right\},\ $ and so on.
It follows from this that simply removing one coin from both piles is not usually a good strategy. The position $\ \left\{5,7\right\}\ $, for instance is an $\ \mathcal{N}$-position in which the only winning moves are to take either $2$ coins from both piles, or $4$ coins from the pile of $7$, in both cases leaving one's opponent with the $\ \mathcal{P}$-position, $\left\{3,5\right\}\ $. Taking one coin from both piles, on the other hand, leaves one's opponent with the $\ \mathcal{N}$-position,$\ \left\{2,6\right\}\ $, from which he or she can win by taking $5$ coins from the pile of $6$.
The list, $\ \left\{a_1,b_1\right\}, \left\{a_2,b_2\right\},\dots, \left\{a_i,b_i\right\}, \dots, \ $ of $\ \mathcal{P}$-positions is constructed recursively as follows:
- $\ a_1=1\ $, $b_1=2\ $.
- Given $A_n=\left\{a_1, a_2, \dots, a_n\right\}\ $ and $B_n=\left\{b_1, b_2, \dots, b_n\right\}\ $, define \begin{eqnarray} a_{n+1} &=& \min\mathbb{N}^+\setminus\left(A_n\cup B_n\right)\ , \mbox{and}\ .\\ b_{n+1}&=&a_{n+1}+n+1\end{eqnarray}
If we put $\ P_n=\left\{\left\{a_i,b_i\right\}\left|i=1,2,\dots,n\right.\right\}\ $ then it's easy to demonstrate that:
- $\bigcup_\limits{i=1}^\infty A_i \cap\ \bigcup_\limits{i=1}^\infty B_i=\emptyset\ $,
- $\bigcup_\limits{i=1}^\infty A_i \cup\ \bigcup_\limits{i=1}^\infty B_i=\mathbb{N}^+\ $, and
- $\left\vert b-a\right\vert \le n\ \ \mbox{ for all }\ \ \left\{a,b\right\}\in P_n\ $
We can now show by induction that the set of $\ \mathcal{P}$-positions is $\ P=\bigcup_{i=1}^\infty P_i\ $.
First, let $\ \left\{a,b\right\}\not\in\ P\ $, with $\ a\le b\ $. If $\ a=b\ $, then the first player can win immediately by taking all the coins from both piles. Otherwise, if $\ r= b-a\ $, then either $\ a=a_k\ $ or $\ a=b_k\ $ for some $\ k\ $. In the first case, since $\ \left\{a,b\right\}\not\in\ P_r\ $, we must have $\ a> a_r\ $, and the first player can leave the second with the position $\ \left\{a_r,b_r\right\}\in P_r\ $ by removing $\ a-a_r\ $ coins from both piles. In the second case, the first player can leave the second with the position $\ \left\{a_k,b_k\right\}\in P_k\ $, again with $\ a_k < a\ $, by removing $\ b-a+k=b-a_k\ $ from the pile of $\ b\ $. In position $\ \left\{1,2\right\}\ $ there are only four moves possible for the first player:
- Take one coin from each pile. The second player can then win by taking the one remaining coin;
- Take the coin from the pile of one. The second player can then win by taking both coins from the remaining pile;
- Take one coin from the pile of $2$. The second player can then win by taking both of the remaining coins;
- Take both coins from the pile of $2$. The second player can then win by taking the single remaining coin.
Thus, the position $\ \left\{1,2\right\}\ $ is a $\ \mathcal{P}$-position. Suppose now that all positions in $\ P_{n-1}\ $ are $\ \mathcal{P}$-positions, and consider the position $\ \left\{a_n,b_n\right\}\ $. If the first player takes all the coins from either pile, then the second player wins immediately by taking all the coins from the other. If he or she takes $\ c < a_n\ $ coins from the $\ a_n\ $ pile, then the new position, $\ \left\{a_n-c,b_n\right\}\ $, cannot be in $\ P\ $, because $\ b_n-\left(a_n-c\right)=n+c\ $ but $\ a_n-c< a_{n+c}\ $. If he or she takes $\ c \le n\ $ coins from the pile of $\ b_n\ $, the new position, $\ \left\{a_n,b_n-c\right\}\ $ again cannot be in $\ P\ $, because $\ b_n-c-a_n = n-c\ $, and either $\ n-c=0\ $, or $a_n \ne a_{n-c}\ $. If he or she takes $\ c\ $ coins from the $\ b_n\ $ pile, with $ n<c< b_n\ $, then the new position, $\ \left\{b_n-c, a_n\right\}\ $ cannot be in $\ P\ $, because $\ a_n\notin B\ $. Finally, if the first payer takes $\ c\ $ coins from both piles, the new position, $\ \left\{a_n-c,b_n-c\right\}\ $ cannot be in $\ P\ $ because $\ b_n-c-\left(a_n-c\right)=n\ $, and $\ a_n-c < a_n\ $. Thus, from the argument above, whatever the first player does, the second player can either win immediately, or move the position to $\ \left\{a_k, b_k\right\}\in P_k\ $ with $\ k < n\ $, which is a $\ \mathcal{P}$-position by the induction hypothesis. Thus $\ \left\{a_n, b_n\right\}\ $ is a $\ \mathcal{P}$-position, and it follows by induction that all positions in $\ P\ $ are $\ \mathcal{P}$-positions.
On the other hand, the argument above shows that a player faced with a position not in $\ P\ $ can always either win immediately, or move the game to a $\ \mathcal{P}$-position in $\ P\ $, so a position is a $\ \mathcal{P}$-position, if and only if it is in $\ P\ $.
Addendum: I have just become aware that the $2$-pile version of this game is known as Whytoff's game, its solution having already been given by the Dutch mathematician Willem Whytoff in 1907.
Best Answer
As Ross pointed out, you can solve this using nimbers. Working out the nimbers for some low coin counts leads to the winning strategy: Always make sure the coin counts are roughly equal, $\pm1$, and that their sum is divisible by $3$. That is, if the coin counts are equal and both have remainder $1$ mod $3$, take one coin from each pile; if the coin counts are equal and both have remainder $2$ mod $3$, take a coin from either pile: if the coin counts are different, take as many from the larger pile that you end up with the same count $\pm1$ and the sum is divisible by $3$. Such a move is always possible if the position isn't one of the losing positions $(3k,3k)$ or $(3k+1,3k+2)$ or $(3k+2,3k+1)$.
In particular, since $2010$ is divisible by $3$, the initial position is a losing position for player $A$.