Question
Circle or highlight or write your answers Developing an optimal strategy for a variant of the game Nim . The three problems, +5 for each
Circle or highlight or write your answers
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 asubtraction 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
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
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
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 = 1, 2, 3, 4, etc. results in the set { 4, 7, 10, 13 } for k = 1, 2, 3, 4
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started