A Simple Coin Game

Probability Level 2

Louise and James are playing a game with a pile of 15 coins. Each player alternates the turns by removing 1, 2 or 3 coins from the pile. Loses the game who remove the last coin. James start the game. If both play optimally, who have the winning strategy?

James Both have same chance Louise

2 solutions

Brian Moehring
Aug 9, 2018

James takes $2$ coins on his first move, leaving $13$ for Louise.

When Louise takes $k \in \{1,2,3\}$ coins, James can respond by taking $4-k \in \{1,2,3\}$ coins, leaving $13-k-(4-k) = 13 - 4 = 9$ coins for Louise. Then repeating this, Louise will have $5$ coins on her next turn, and $1$ coin on the turn after that, forcing Louise to take the last coin and making her lose.

Therefore $\boxed{\text{James}}$ has the winning strategy.

Hi Brian. If we change the rule and the winner is the player who removes the last coin, James aging has a winning strategy. He takes 3 coins on his first move, and then follows your strategy.

A Former Brilliant Member - 2 years, 7 months ago

Benjamin Chen
Aug 25, 2018

The intuition behind the solution is to start from the end. W stands for winner and L for loser

$\boxed{L=1}$ $\rightarrow$ W= 2,3,4 $\rightarrow$ L= 5 $\rightarrow$ W= 6,7,8 $\rightarrow$ L= 9 $\rightarrow$ W= 10,11,12 $\rightarrow$ L= 13 $\rightarrow$ W= 14,15

In general, given a pile of N coins, if a player is allowed to remove 1 to x coins from the pile, the one who starts will lose if N $\equiv$ 1 $\pmod{x+1}$ and will win otherwise.

A Simple Coin Game

2 solutions

0 pending reports