14. (+15) Developing an optimal strategy for a variant of the game Nim. The three problems, +5 for each problem, that require answers appear at the end 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. The purpose of this exercise is to find the strategy (solution.) Rules of the game 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. Number of sticks Your turn Outcome 1 no strategy you lose (bad pile) 2 remove 1 stick you win 3 remove 2 sticks you win 4 remove 3 sticks you win 5 remove 4 sticks you win 6 no strategy you lose (bad pile) 7 remove 1 you win 11 no strategy you lose Why it is a bad pile for you with 6 sticks 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. Why it is a good pile for you with 7, 8, 9, 10 sticks 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. Why it is a bad pile for you with 11 sticks Note that if it is your turn and you a have a pile with 11 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 (6 sticks). If, on the other hand, you take 2 sticks then he/she can take 3 sticks, leaving you with a bad pile(6 sticks). If your take 3 sticks then he/she can take 2 sticks, leaving you with a bad pile (6 sticks).. Finally, if you take 4 sticks then he/she can take a single stick, leaving you with a bad pile(6 sticks).. So, a pile with 11 sticks is just as bad as a pile with a 6 sticks.

Problems 1. Is a pile with 286 sticks a good pile for you? If it is a good pile how many sticks should you remove? If it is a bad pile, explain

2. Is a pile with 285 sticks a good pile for you? If it is a good pile how many sticks should you remove? If it is a bad pile, explain

3. Identify the pattern. For a pile containing n sticks, which ones are good for you? Which ones are bad? Express the pattern in the most general way possible using n = number of sticks in the pile

As an example n = 3k + 1 with k = 0, 1, 2, 3, 4, etc. results in the set { 1, 4, 7, 10, 13 } n = 5k + 3 with k = 0, 1, 2, 3, 4, etc. results in the set { 3, 8 13, 18 }

Answer three questions at bottom