Solve the Coin Problem with Expert Tips | Austin vs. Brooks Game Strategy

[golfchic2006]

Help please! Coin Problem

A coin game requires:
1. Ten coins in one pile
2. That each player takes one, two, or four coins from the pile at alternate turns.
3. That the player who takes the last coin loses.

I. When Austin and Brooks play, Austin goes first and Brooks goes second,
II. Each player always makes a move that aloows him to win when possible; if there is no way for him to win, then he always makes a move that allows a tie when possible.

Must one the two men win? If so, which one?

 

[ssjSolidSnake]

Two men can win?

Brooks takes 4

Austin takes 2

Brooks takes 1

Austin takes 1

Brooks takes 2

 

[golfchic2006]

There can be a tie. But look at number 3. The player who takes the last coin loses. Would that mean that Brooks looses according to your answer?

 

[CRGreathouse]

The first player always wins in this case. The correct starting move is to take 4 coins.

 

[robert Ihnot]

The first player has the option to win by taking an even number. If A takes 2, then B gets nowhere by taking an even number, as gone into below, so B will take only 1. This leaves now 7 and A then takes 1, leaving B with 6, and B must take 2, leaving 4. In this case, A again takes 1.

 

[CRGreathouse]

The first player has the option to win by taking an even number. If A takes 2, then B gets nowhere by taking an even number, as gone into below, so B will take only 1. This leaves now 7 and A then takes 1, leaving B with 6, and B must take 2, leaving 4. In this case, A again takes 1.

If the first player takes 2 the second player can also take 2, which forces a win for the second player. The only correct starting move is to take 4.

 

[robert Ihnot]

CRGreathouse: If the first player takes 2 the second player can also take 2, which forces a win for the second player. The only correct starting move is to take 4.

Well, if A takes 2, B takes 2, then A can take 2, leaving 4. So A wins!

 

[CRGreathouse]

Well, if A takes 2, B takes 2, then A can take 2, leaving 4. So A wins!

No, B responds by taking 3, forcing A to take the last and thus lose.

 

[robert Ihnot]

CRGreathouse: No, B responds by taking 3, forcing A to take the last and thus lose.

PLEASE! You are not allowed to take 3.

 

[uart]

No, B responds by taking 3, forcing A to take the last and thus lose.

Hi CRGreathouse. I think you misread the question, 3 is not an option.

"2. That each player takes one, two, or four coins from the pile at alternate turns."

Edit : Robert just beat me to it. :)

 

[CRGreathouse]

PLEASE! You are not allowed to take 3.

Ah, sorry, missed that. I did solve the problem where {1, 2, 3, 4} rather than {1, 2, 4} were legal.

The first player has the option to win by taking an even number. If A takes 2, then B gets nowhere by taking an even number, as gone into below, so B will take only 1. This leaves now 7 and A then takes 1, leaving B with 6, and B must take 2, leaving 4. In this case, A again takes 1.

I still don't follow. Can't B then force a loss for A by taking 2?

A: 10 -> 8
B: 8 -> 7
A: 7 -> 6
B: 6 -> 4
A: 4 -> 3
-----
B: 3 -> 1
A: 1 -> 0

It looks like leaving a player with a number of coins equal to 1 mod 3 at each turn forces a win.

 

[tiny-tim]

It looks like leaving a player with a number of coins equal to 1 mod 3 at each turn forces a win.

You can make this rigorous:

If player A leaves 1 (mod 3), what can player B then leave (mod 3)?

Can player A always get back to 1 (mod 3), next move?

If so, then he can always leave 1 (mod 3), until eventually he leaves exactly 1.

 

[dianli1990]

The first player always wins in this case. The correct starting move is to take 4 coins.

That depends, because if #1 takes 4, #2 has the choice to take 2, Then:
#1 takes 1, #2 takes 2, #1 takes 1 and loses.
or
#1 takes 2, #2 takes 1, #1 takes 1 and loses.
There is no correct starting move if player #2 is smart enough to win.