14. (+15) Developing an optimal strategy for a variant of the game Nim. The thre

Question

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

Explanation / Answer

From the description provided, it is clear that a plie with 1 stick, 6 sicks, 11 sticks, etc are bad piles for you.

1) A pile with 286 sticks is a bad pile for you.

Explanation: A pile with 1 stick, 6 sticks or 11 sticks is a bad pile for you. Similarly, a pile with 16 sticks is bad because if you choose 1 stick, you opponent will choose 4 sticks. Then you are left with 11 sticks, which is a bad pile for you. If you choose 2 sticks, then player 2 can choose 3 sticks and you remain with 11 sticks(bad for you). And, if you choose 3 sticks, he can choose 2 sticks and again you are left with 11 sticks. One last case, if you choose 4 sticks, then he can choose 1 stick so that you are left with 11 sticks (bad pile for you).

Similarly, a pile with 21 sticks is bad for you. If you choose 1 stick, you opponent will choose 4 sticks. Then you are left with 16 sticks, which is a bad pile for you. If you choose 2 sticks, then he can choose 3 sticks and you remain with 16 sticks(bad for you). And, if you choose 3 sticks, he can choose 2 sticks and again you are left with 16 sticks. If you choose 4 sticks, then he can choose 1 stick so that you are left with 16 sticks (bad pile for you).

It can be inferred that any number that ends with 1 or 6 is a bad pile for you. Since, 286 ends with digit 6, it is a bad pile for you.

2) A pile with 285 sticks is a good pile for you.

Explanation: As discussed in problem 1, any pile with number of sticks that ends with 1 or 6 is a bad pile for you. Since, 285 ends with 5, it is a good pile for you.

Initially you should remove 4 sticks such that your opponent is left with 281 sticks. Since, 281 ends with 1, it will certainly be a bad pile for your opponent.

3) Pattern for bad pile with n sticks is n = 5k + 1 for k = 0, 1, 2, 3, 4, etc.

Clearly, this pattern will result in a set {1, 6, 11, 16, 21, 26, .....} which can represent bad pile.

Pattern for a good pile with n sticks is n = 5k + m for k = 0, 1, 2, 3, 4, etc and m = 2, 3, 4 or 5

Let k = 0, then n can be 2, 3, 4 or 5 (all good piles for you). If k = 1, then n = {7, 8, 9, 10}, again all good sets for you. Hence, this pattern will result in a set {2, 3, 4, 5, 7, 8, 9, 10, 12, 13, 14, 15, .....}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.