3
$\begingroup$

Two players A and B play a game where they take turns removing 1,4, or 5 coins from a pile of n coins, A moving first. The player who takes the last coin wins. Who wins when: n=18, n=41, n=56?

This problem is easy to solve for small values of n, but for large values I'm having difficulty calculating the tree. Please do not mark this question as a duplicate because the answers to these particular values of n are of interest to me.

$\endgroup$
  • $\begingroup$ If n=3, do players only have one move (take one coin) or can they take all the remaining coins? $\endgroup$ – Ian MacDonald Sep 27 '16 at 17:14
  • $\begingroup$ @Ian Only one coin. $\endgroup$ – RobertJan Sep 27 '16 at 17:20
  • 1
    $\begingroup$ Possible duplicate of Halve or diminish, and race to unity! $\endgroup$ – Oray Sep 27 '16 at 17:44
  • $\begingroup$ @Oray These aren't duplicates. They're similar, but that's generally ok on PSE. $\endgroup$ – Mike Earnest Sep 27 '16 at 18:18
7
$\begingroup$

The only thing that matters is

$n$ $mod$ $8$. If it is $0$ or $2$, $B$ wins, otherwise $A$ wins.
This also tells you what is the winning move: you should take as many coins, as it is needed to have $8k$ or $8k+2$ coins left on the table.
For $n=18$ and $n=56$, $B$ wins if playing correctly, no matter what $A$ does. For $n=41$, $A$ wins (taking $1$ coin first).

This is because

from all the numbers giving 1, 3, 4, 5, 6 or 7 modulo 8 you can get to one giving 0 or 2 modulo 8:
1-1=0
3-1=2
4-4=0
5-5=0
6-4=2
7-5=2
But whatever you do starting from 0 or 2 modulo 8, you end up with one of the others:
0-1=7
0-4=4
0-5=3
2-1=1
2-4=6
2-5=5

$\endgroup$
1
$\begingroup$

The answer is

For $n=18$, B wins.
For $n=41$, A wins.
For $n=56$, B wins.

Actually this question is kinda same question as Halve or diminish, and race to unity!. The only difference is the methodology. You need to think of this question from the very beginning 2.

For $n=2$, A loses automatically since A can only remove 1 coin and and B will win by default.

Likely, For $n=3$, A win since A can only remove 1 coin and and B will end up with 2 coins, what happens before will happen to B.

For $n=4,5$, A wins.

Important: For $n=6$, A has 3 options, to remove 1,4 or 5 coins, if any of these options is lost for B somehow, A wins, otherwise B wins. This is the rule of this game. As a result;

1-) A

2-) B

3-) A

4-) A

5-) A

6-) A

7-) A

8-) B

9-) A

10-) B

11-) A

12-) A

13-) A

14-) A

15-) A

16-) B

17-) A

18-) B

19-) A

...

41-) A

....

56-) B

The bold part repeats itself forever. You may find the general formulation on mod 8 accordingly:

If $(n\ mod\ 8) = 0 \ or\ 2$ B wins otherwise A wins.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.