Take-away game problem – find the winning strategy

contest-math

There are 200 coins in a pile. During a players turn they must take at least one coin and
cannot take more than half of the coins. The person who takes the last coin wins. Devise a
strategy so you always win.

What strategy/method should I use to solve this problem and related problems. Would proof by induction be sufficient or is there some kind of formula. I’ve played around with this question for a while but haven’t had much luck. Any suggestions/pointers would be helpful.

Best Answer

Commonly, with a game like this one (two-player, symmetric, zero-sum games of perfect information and no possibility of a tie), you can start at the end of the game and work your way backwards, marking each board position as either a winning position or a losing position, defined recursively by the two rules:

  • A board position is a winning position if you either immediately win or you can move so that the board position on your opponent's turn is a losing position.
  • A board position is a losing position if you either immediately lose or every option you have to move will put the board in a winning position on your opponent's turn.

For instance:

  • If on my turn there is one coin remaining, then I win. Therefore one coin is a winning position.
  • If there are two coins remaining, then I must take one coin, leaving one left, which is a winning position. Therefore two coins is a losing position.
  • With three coins, I can remove one to put the board in a losing position, so three coins is a winning position.

After you do this a few more times, you might notice that the losing positions become pretty rare, and we can further investigate what pattern they follow. In this case, we find that the losing positions are all the positions with $3(2^n)-1$ coins for $n \geq 0$ an integer.

Once you have that, the winning strategy is fairly apparent. Whatever position the board is in on your turn, you must take away the right number of coins to leave $3(2^n)-1$ coins on your opponent's turn. Proving that this is a winning strategy amounts to an inductive proof that having $3(2^n)-1$ coins at the start of your turn is a losing position as defined by the two rules I gave above, which effectively is just noting $$\frac{1}{2}\Big(3(2^n)-1-1\Big) \leq 3(2^{n-1})-1 < \frac{1}{2}\Big(3(2^n)-1\Big).$$

In a game starting with $200$ coins, if we go first, we should take $9$ coins, leaving $3(2^6)-1 = 191$ coins. Following this strategy each turn will result in our win.

Related Question