Question

Developing an optimal strategy for a variant of the game Nim Nim is a subtraction game that is played with sticks. The subtraction game variant is simple. A pile of sticks is placed in front of a pair of participants. The players take turns removing either 1, 2, 3, or 4 sticks from the pile. The player who removes that last stick from the pile loses the game. It turns out that there is an optimal strategy for playing this subtraction game variant of Nim. We can actually use mathematical induction to construct this optimal strategy.

We begin by considering the rules of the game. A player loses the game if he/she is forced to pick up the last stick in the pile. Thus, a pile containing a single stick is bad pile. Other piles of sticks are not so bad. Consider a pile that contains 2 sticks. If it is your turn and you have a pile with 2 sticks then you can pick up a single stick which will leave your opponent with a bad pile containing a single stick. Likewise, if it is your turn and you have a pile with 3 sticks then you can pick up 2 sticks which will leave your opponent with a bad pile containing a single stick. And if it is your turn and you have a pile with 4 sticks then you can pick up 3 sticks which will leave your opponent with a bad pile containing a single stick. Finally, if it is your turn and you have a pile with 5 sticks then you can pick up 4 sticks which will leave your opponent with a bad pile containing a single stick.

Note that if it is your turn and you a have a pile with 6 sticks then there is nothing you can do to prevent your opponent from giving you a bad pile after his/her turn. If you take a single stick then he/she can take 4 sticks, leaving you with a bad pile. If, on the other hand, you take 2 sticks then he/she can take 3 sticks, leaving you with a bad pile. If your take 3 sticks then he/she can take 2 sticks, leaving you with a bad pile. Finally, if you take 4 sticks then he/she can take a single stick, leaving you with a bad pile. So, a pile with 6 sticks is just as bad as a pile with a single stick.

A pile with 7 sticks, on the other hand, is great because you can take a single stick and force your opponent to have to deal with a bad pile containing 6 sticks. Likewise, you can force your opponent to have to deal with a bad pile containing 6 sticks if you have a pile with 8, 9, or 10 sticks by removing 2, 3, or 4 sticks, respectively. A pattern is clearly arising.

1. Identify the pattern. For a pile containing n sticks, which ones are good? Which ones are bad? Express the pattern in the most general way possible.

2. Remember that you have no control over how many sticks your opponent is going to remove, so you must consider all possibilities. Make a claim that expresses the optimal strategy for the subtraction game variant of Nim. For each of the good piles covered by the pattern you identified in the previous problem, how many sticks should you remove so that you can ensure that you will win?