Stack of Coins 2

You and your friend have decided to make treasure hunting your weekend project. After a few weeks of treasure hunting, you guys stumble on another pirate’s treasure: an old chest filled with coins: 99 copper coins and 1 gold coin. As before, these old coins are no longer legal tender, so the copper ones are worthless. Only the gold coin is worth something due to its material.

Not wanting to lose again, your friend comes up with another game of wits. He stacks the 100 coins in a tall stack with the gold coin at the bottom. You and him will take turns taking either 1, 4, or 5 coins from the top of the stack, all the way until the final coin is taken. If there’s only 2 or 3 coins left, the only option for the player is to take 1 coin, since there aren’t enough coins for the player to take 4 or 5. He lets you decide if you want to go first or second.

Should you go first or second? And what strategy do you use to ensure you’ll win the gold coin?

Solution

Choose to go first and take 4 coins. After that, follow the strategy below.

Let’s start from 0 coins and work backwards. If a player is presented with a stack of 0 coins, it means their opponent took the gold coin, resulting in a loss for the current player. If there are 1, 4, or 5 coins left, the player that moves next can take all the coins and win. A stack of 2 coins left is a losing position as the only option is for the player to take 1 coin, allowing their opponent to take the last coin and win.

Coins in stack	Position for the player that moves next
0	Lose
1	Win
2	Lose
3	?
4	Win
5	Win

We notice that when there are 3 coins left, the next player can take away 1 coin, forcing their opponent into a losing position with 2 coins.

Coins in stack	Position for the player that moves next
0	Lose
1	Win
2	Lose
3	Win
4	Win
5	Win

Let’s extend the table a bit more.

Coins in stack	Position for the player that moves next
0	Lose
1	Win
2	Lose
3	Win
4	Win
5	Win
6	Win
7	Win
8	Lose
9	Win
10	Lose

As we learnt in Adversarial Games, a position is a winning position if there exists a move for the current player to put the other player in a losing position. A position is a losing position if ALL moves put the other player in a winning position.

A stack of 6 coins is a winning position since you can take 4 coins to leave the other player with a stack of 2 coins: a losing position.

A stack of 7 coins is a winning position since you can take 5 coins to leave the other player with a stack of 2 coins: a losing position.

A stack of 8 coins is a losing position, since taking 1, 4, or 5 coins leaves you with a stack of 7, 4, or 3 coins, all of which are winning positions for their opponent.

Notice that the table is starting to repeat itself. This is because we can determine if a position is winning or losing by looking up to 5 positions up the table. Once it starts repeating, it will repeat all the way down.

Coins in stack	Position for the player that moves next
0	Lose
1	Win
2	Lose
3	Win
4	Win
5	Win
6	Win
7	Win
8	Lose
9	Win
10	Lose
11	Win
12	Win
13	Win
14	Win
15	Win
16	Lose
17	Win
18	Lose
…

In general, we see that the losing positions are positions where the stack of coins are (a) a multiple of 8, or (b) 2 more than a multiple of 8.

Since 100 is 4 more than a multiple of 8, it is a winning position, so you should choose to go first. On your turn, you want to take a number of coins to leave your opponent in a losing position. To do so, you can follow the strategy below: divide the number of coins by 8 to get the remainder $k$ , then follow the table below to see what action to take.

$k$	What to do
0	Losing position: all moves lead to a loss in optimal play.
1	Take 1 coin
2	Losing position: all moves lead to a loss in optimal play.
3	Take 1 coin
4	Take 4 coins
5	Take 5 coins
6	Take 4 coins
7	Take 5 coins

Previous puzzle in this series

Stack of Coins 1C

Next puzzle in this series

Stack of Coins 3

Try These Next

Two-Bullet Russian Roulette

Pirates and Coins

Ant on a Rubber Band