16 coins

Probability Level 2

You play a game where two people take turns picking coins from a pile of coins and the person to take the last coin wins!

The rule is you can take up to $n$ coins where $n$ is the turn number.

So, for example, suppose Sue and Esmerelda are playing the game. The first person (Sue) can take 1 coin (not much of a choice there!). The second person to play (Esmerelda) can take 1 or 2 coins. The third person (Sue again) can take 1, 2 or 3 coins.

Suppose you are the first to move and there are 16 coins.

If both people play optimally, can you guarantee a win?

Image credit: https://thecliparts.com

No Yes

2 solutions

Geoff Pilling
Dec 2, 2016

If $t$ is the turn number, and $c$ is the number of coins in the pile, then the following recursive relation determines whether you will win or not ( $1=$ win, $0 =$ lose):

$W(t,c) = 1$ if $t \geq c$ , since you can just take the remaining coins and win
$W(t,c) = 1 - MIN(W(t+1,c-i))$ where $i$ ranges from $1$ to $t$ . Since you can pick any number of coins from $1$ to $t$ , so if you play optimally you will pick one where $W(t+1,c-i) = 0$ .

Solving, $W(1,16) = 1$ .

So, $\boxed{\text{yes}}$ you can win!

Anirudh Sreekumar
Dec 3, 2016

You can definitely win if you start first

1) pick 1 coin on your 1st turn

2) let your opponent pick 1 or 2 coins

3) make the total number of coins picked up to 4

4) your opponent can get the count up to 8

5) make the count of the coins picked up to 9

6) your opponent can only get the count upto 15

7) you win YAY!!!

Nice write up, @Anirudh Sreekumar !

Geoff Pilling - 4 years, 6 months ago

thank you :)

Anirudh Sreekumar - 4 years, 6 months ago

16 coins

Image credit: https://thecliparts.com

2 solutions

0 pending reports