This is a sub-part question Developing an optimal strategy for a variant of the

Question

This is a sub-part question

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 … }

Explanation / Answer

From the above strategy of winning or losing, its is clear that this game follows a pattern of numbers.

Pattern is as follow:

1 -> You Lose

2-5 -> You Won = 1 + (1..4)

6 -> You lose

7-10 -> You Won = 6 + (1..4)

So, following pattern lead you to lose, its bad for you

n = 5k +1 with k = 0,1,2,3,4....... etc. results in the set {1,6,11,16.....}

Number which will won you is: 2,3,4,5,7,8,9,10.....

Or simplify it as:

So, winning pattern is now easy to make:

n = 5k + 2 with k=0,1,2,3..... results in set {2,7,12.....}

n = 5k + 3 with k=0,1,2,3..... results in set {3,8,13,18.....}

n = 5k + 4 with k=0,1,2,3..... results in set {4,9,14,19.....}

n = 5k + 5 with k=0,1,2,3..... results in set {5,10,15,20.....}

Now check your question with the fail pattern only i.e. n = 5k+1.

if its follow, its bad for you, otherwise good for you,.

For every number n, we will find k with n = 5k+1 equation, if k is whole number its mean n is bad for you otherwise not.

Question 1 answer:

n = 5k+1

286 = 5k +1

5k = 285

k = 285/5 => 57 (which is whole number i.e. k=57, and successfully follows the n=5k+1 pattern)

therefore, 286 is bad for you as it follows the pattern with k=57, which is whole number.

Question 2 answer:

n = 5k+1

285 = 5k +1

=> 5k = 284

=> k = 56.8 (which is not whole number, therefore its not following the pattern. and its good for you.)

Now check 285 with winning pattern, so you get k and k is equals how many sticks we will remove.

Checking it with n=5k+2,

=>5k = 285-2

=> k = 283/5 (its again not following n=5k+2)

Here, 285-2 = 283, 285-3=282, 285-4 = 281 which are not divisible by 5, therefore 285 will not follow all these pattern except n = 5k+5.

Checking 285 with n = 5k+5,

285 = 5k+5

=>5k = 280

=> k = 56.

Therefore you will remove 56 sticks.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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