8
$\begingroup$

X and Y are playing a game. There are eleven coins on the table and each player must pick up at least one coin but not more than five in a turn. The person picking up the last coin loses. X starts. How many should X pick up to start to ensure a win no matter what strategy Y employs?

Is there a mathematical approach?

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ This is just Nim with 11 pieces. If you prefer video, here's one explaining The Amazing Dr. Nim, a "game" that beats you at Nim. $\endgroup$
    – Engineer Toast
    Commented Jun 23, 2017 at 18:51
  • 3
    $\begingroup$ This is not ordinary Nim, since there is an upper limit on the number of coins that can be taken. (And indeed, single-pile Nim is trivial.) $\endgroup$
    – Greg Martin
    Commented Jun 24, 2017 at 0:17
  • $\begingroup$ @EngineerToast The subtraction game where you can remove 1, 2, or 3 pieces on a turn is/was called Nim in many places, including that "Amazing Dr. Nim". But as Greg Martin points out, Nim more commonly refers to a game with multiple heaps where you can remove as much as you want from a single heap. $\endgroup$
    – Mark S.
    Commented Jun 24, 2017 at 3:40

6 Answers 6

Reset to default
14
$\begingroup$

X picks 4.
Y picks $N$ coins.
X removes $6-N$ coins.
There is now 1 coin on the table because we removed $4 + N + 6- N = 10$.

Generalization.

There are $K$ coins on the table and one player can pick as many as M coins at once.

Case 1:
M >= K. This is trivial. Player 1 picks $K-1$ coins, leaving 1 coin and wins.
Case 2.1:
$M < K$ and $K \not\equiv 1 (\textrm{mod}\ (M + 1))$
player 1 picks $P$ coins in such a way that $(K-P) = K_1 \equiv 1 (\textrm{mod}\ (M + 1))$
player 2 picks $N$ coins ($N < M$).
Player 1 picks $M + 1 - N$ coins leaving again the number of coins on the table $K_2 \equiv 1 (\textrm{mod}\ (M + 1))$
Repeat this process until $K_q = 1$ and player 1 wins.
Case 2.2
$M < K$ and $K \not\equiv 1 (\textrm{mod}\ (M + 1))$
Player 2 can follow the same strategy as player 1 followed in case 2.1 and win.

Improve this answer
$\endgroup$
13
$\begingroup$

Using winning/losing position analysis you can tell that the correct move is to take:

4

You can work this out iteratively.

If you have 1 coin and it is your turn you will obviously lose. Thus 1 is a losing condition.

We can then create a set of winning conditions:

2-6 coins are all winning positions. The reason being that you can take as many coins as are needed to leave one coin left which is then a losing position for your opponent and thus a winning position for you.

You can then use that to work out more losing conditions.

7 coins is a losing position because no matter how many coins you take away you are left with somewhere between 2 and 6 coins, inclusive. Thus leaving your opponent with a winning position and thus you lose.

You can then extend this logic to create an formula to allow you to work out what positions are winning and what are losing. Then for any position you know that you just take coins to leave your opponent with one of the losing positions.

The losing positions are when there are 1+6n coins remaining (where n is a non-negative integer). This can be shown by the same logic as already used. It can also be verified by considering that if you are at 1+6n coins then if you take m coins then your opponent can take 6-m coins and your new position is still of the form 1+6n meaning you are still in a losing position. And of course any other position is a winning position you will have 1+6n+k coins where k is between 1 and 5 (inclusive). You thus just take k coins, leaving your opponent with a losing position.

So for this particular problem:

You have 1+6(1)+4 coins to start with, thus you take 4.

Improve this answer
$\endgroup$
0
7
$\begingroup$

X should pick up

4 at the beginning

Because

however many Y picks next, X will make up the difference so that the three turns sum to 10 coins, then forcing Y to pick up the last one

Examples:

X = 4
Y = 1, 2, 3, 4, 5 (the 5, 6, 7, 8, or 9th coin)
X = 5, 4, 3, 2, 1 (the 10th coin)
Y = 1 (which is the 11th coin)

Improve this answer
$\endgroup$
5
$\begingroup$

4.

Because if player Y picks up
- 1 coin : X picks 5
- 2 coins : X picks 4
and so on, so the total amount of coins picked will be 10 and Y will have no other choice than pick up the last coin and lose.

Improve this answer
$\endgroup$
1
$\begingroup$

First insight:

You win if you can make a move that leaves only one coin for your opponent to pick up.

Second insight:

However many coins your opponent takes, you can take a number of coins that, together with his, sums to 6.

Third insight:

Thus, if you can make a move that leaves 7 coins, you win just as surely as if you make a move that leaves 1 coin, since you can force that condition one turn later.

Now it's obvious that:

You need to leave 1, 7, 13, .. coins at the end of your turn to win. There are now 11 coins, and it's your turn. So taking 4 leaves 7 at the end of your turn and thus you can force your opponent to take the turn after that with only one coin left.

So take 4.

Improve this answer
$\endgroup$
0
$\begingroup$

The Mathematical solution :

total coins = t
range is from 1 to n

first X draws x coins

Any Solution must satisfy the equation

t-x = n+2

hereby Y can draw coins from 1 to n and in every case the no. of coins left will be between n+1 to 2

now X pulls out (n to 1) coins respectively from (n+1 to 2)

hereby making sure Y has to pick up the last coin

Improve this answer
$\endgroup$

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