Stack of Coins 3

Once more, you and your friend stumble on another pirate’s treasure: an old chest filled with coins: 575 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 576 coins in a tall stack with the gold coin at the bottom. You and him will take turns taking coins from the top of the stack, all the way until the final coin is taken.

If you are the first to move, you can only take up to 575 coins. After that, players can only take anywhere between 1 to $X$ coins (inclusive), where $X$ is the number of coins taken on the last turn. 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

The solution is fairly complex, so let’s work our way up. Do take a look at Adversarial Games if you haven’t already done so, as most concepts there will be useful for this solution.

Let’s play around with smaller stacks of coins in order to get a feel of the rules. If we start with a stack of 5 coins, should you go first?

Yes! All you have to do is to take 1 coin. This forces you both to take turns taking 1 coin each. Since there are an odd number of coins, you’ll take the last coin and win.

We can show this by laying out the coins in a row, with the coin at the top of the stack on the left, and the gold coin on the right. We colour the gold coin blue, then the next coin red, then blue, and so on.

By taking the blue coin on your turn, you always force the other player to only take the red coin. To get this configuration, we’ll need the first coin to be blue, meaning this strategy only works if we start with an odd number of coins. What happens if we start with an even number of coins?

Let’s consider 6 coins. If you take 3, 4, or 5 coins, the other player can immediately take the remaining coins and win. But if you take 1 coin, then you’ve forced both players to take 1 coin until the other player takes the last coin and you lose. The only option you have is to take 2 coins to not result in an immediate loss.

You take 2 coins. The other player now has 2 options:

Take 2 coins. You can take the remaining 2 coins and win.
Take 1 coin. You both take turns taking 1 coin until you win.

No matter what the other player picks, you can always win.

Let’s try to represent this by extending our earlier diagram. This time, we’ll group the coins into pairs. We colour the pair with the gold coin blue, then the next pair red, then the next pair blue.

This leaves us with 2 interesting observations:

If the other player sticks to taking pairs, then you’ll take turns taking alternating blue and red pairs, leaving you the win.
If the other player breaks the pairs by taking an odd number of coins, then you’ll take turns taking alternating blue and red coins, leaving you the win.

Since the last coin is always a blue coin in a blue pair, we’ll always ensure that the other player cannot take it. To get a feel for this strategy, let’s try this with a bigger game with 10 coins.

This strategy applies to any odd multiple of 2 (2, 6, 10, 14, …), because the first pair of coins will always be blue.

What happens for the even multiples of 4? Well, we can’t say for sure, so let’s play around with more examples. Let’s try a stack of 12 next.

This time, there’s an even number of pairs, meaning we can’t use our strategy of taking pairs again. But what if we took pairs of pairs? This time, let’s group pairs into pairs, which we will call quadruples (or quads for short). Let’s colour them with alternating colours again.

This time, we can start first and take a blue quad. If the other player takes a red quad, we can take the last blue quad and win.

But what happens if the other player decides to take 1, 2, or 3 coins instead?

If he takes 2 coins, we can start ignoring the quads and look at the pairs. He would have left you with a blue pair at the top, in which case we can use the earlier strategy and start taking pairs each turn.

If he takes 1 or 3 coins, we can start ignoring the quads and pairs and look at the individual coins. He would have left you with a blue coin at the top, in which case we can use our earlier strategy and start taking 1 coin each turn.

Are you starting to see a pattern? For any stack of coins, we can start making pairs, pairs of pairs, then pairs of pairs of pairs, all the way up until we get an odd number of groups. Because of how we constructed these groups, each group will have a number of coins equal to a power of 2. Let the size of the group be $x$ coins. Then on your first turn, you should take $x$ coins to win.

Case 1: If the other player “breaks” the pairs, he would have to leave you a blue coin at the top of the stack. Take 1 coin and you’ll win.

Case 2: If the other player “breaks” the quads but not the pairs, he would have to leave you a blue pair at the top of the stack. Take 2 coins, since the other player can either (a) keep taking 2 coins and you win, or (b) he can break the pairs and you win by case 1.

Case 3: If the other player “breaks” the octets (groups of 8) but not the pairs or quads, then he would have to leave you with a blue quad. Take 4 coins, since the other player can either (a) keep taking 4 coins and you win, or (b) he can break the quads and you win by case 1 or 2.

…

Case $n$ : If the other player breaks the groups of $2^{n}$ but not the groups of $2^{n - 1}$ , $2^{n - 2}$ , …, then he would have to leave you with a blue group of $2^{n - 1}$ . Take $2^{n - 1}$ coins.

Have we solved it? Not quite. So far, I’ve carefully chosen the stack size to avoid a special exception. Let’s take a look at a stack of 4.

If you take 2 or 3 coins on your turn, he takes the remaining and you lose.
If you take 1 coin on your turn, you take turns taking coins and you lose.

How about a stack of 8?

If you take 4 or more coins on your turn, he takes the remaining coins and you lose.
If you take 1 or 3 coins on your turn, you leave him with a stack of an odd number. He starts taking 1 coin on each turn, forcing you to lose.
If you take 2 coins on your turn, he starts taking 2 coins on each turn. You’re once again seeing our strategy in motion, except now you’re on the losing end of it.

Why is this happening? This is because when we formed the pairs of pairs of pairs… into groups, we assumed that there would be an odd number of groups, with this number being more than 1. This lets us take 1 group’s worth of coins on our first turn.

If the stack has a size that is a power of 2 (2, 4, 8, 16, …), then there is exactly 1 group. We can’t take that many coins on our first turn, so we’re forced to make a move that lets the other player subject us to the losing end of the winning strategy.

Let’s put it all together.

If the stack of coins is a power of 2, then choose to go second.
Otherwise, the stack of coins will be in the form $2^{n} \times m$ , where $n$ is an odd number more than 1. On your first turn, take $2^{n}$ coins.
After the other player moves, count the number of the coins in the stack. If there are $x$ coins left in the stack, take $y$ coins such that $y$ is the biggest power of 2 that is still a factor of $x$ .

Extra Credit

I’ve left out one tiny detail in my explanation. In the strategy, I state:

“After the other player moves, count the number of the coins in the stack. If there are $x$ coins left in the stack, take $y$ coins such that $y$ is the biggest power of 2 that is still a factor of $x$ .”

To be certain our strategy works, we should also show that taking $y$ coins is a valid move. If the other player took 3 coins on their previous turn, and our strategy tells us to take 8 coins on our next turn, then this strategy falls apart. Let’s show that such a situation will never happen.

Let’s consider two cases:

Case 1: you went first
- Case 1A: consider the first move
- Case 1B: consider the subsequent moves
Case 2: you went second

In case 1A, we notice that our strategy gives rise to a valid first move since we attempt to take a power of two coins that is less than the number of coins in the stack.

Now we consider case 1B. Let’s say the strategy tells us to take $2^{s}$ coins for some $s$ . This means that the stack of coins is $2^{s} \times m$ for some odd number $m$ .

To reach this point, you must have already made your first move (taking $2^{n}$ coins from the original stack of $2^{n} \times k$ coins, where $k$ is odd and $k > 1$ ). After your move, the stack had $2^{n} \times (k - 1)$ coins. Your opponent then took some number of coins, leaving the current stack of $2^{s} \times m$ coins.

Let’s call the number of coins your opponent took $t$ . Then:

$2^{n} \times (k - 1) - t = 2^{s} \times m$

Rearranging: $t = 2^{n} \times (k - 1) - 2^{s} \times m$

Here’s the key insight. After your first move, the stack size was divisible by $2^{n}$ but not by $2^{n + 1}$ (since $k - 1$ is even but $k$ is odd). The largest power of 2 dividing the stack was exactly $2^{n}$ .

When your opponent takes $t$ coins, they leave a stack divisible by $2^{s}$ . The largest power of 2 dividing the remaining stack equals the largest power of 2 dividing $t$ itself. Why? Because $2^{n} \times (k - 1)$ is divisible by exactly $2^{n}$ , so if we subtract $t$ and get something divisible by $2^{s}$ , then $t$ must be divisible by whichever of $2^{n}$ or $2^{s}$ is smaller.

Since the strategy worked correctly (the stack is now $2^{s} \times m$ where $m$ is odd), we know $2^{s}$ is the largest power of 2 dividing the remaining stack. This means $2^{s}$ is also the largest power of 2 dividing $t$ .

Therefore: $t = 2^{s} \times q$ for some odd number $q \geq 1$

This gives us $t \geq 2^{s}$ , which means taking $2^{s}$ coins is a valid move!

Finally, we consider case 2: you went second. This means the original stack was a power of 2, say $2^{n}$ coins.

Your opponent moves first. Whatever they take (say, $t$ coins where $1 \leq t < 2^{n}$ ), they leave you with $2^{n} - t$ coins.

Now, $2^{n}$ is divisible by $2^{n}$ but not by $2^{n + 1}$ . When we subtract $t$ , the largest power of 2 dividing $(2^{n} - t)$ equals the largest power of 2 dividing $t$ . Let’s say $t = 2^{s} \times q$ where $q$ is odd. Then the stack has $2^{s} \times (something odd)$ coins.

The strategy tells you to take $2^{s}$ coins. Since $t = 2^{s} \times q$ where $q \geq 1$ , we have $t \geq 2^{s}$ , making this a valid move.

For all subsequent moves after your first, the situation is identical to Case 1B—you’ve taken a power of 2, leaving the opponent with a stack divisible by one higher power of 2, and the proof follows the same logic.

Therefore, the strategy always gives valid moves!

Previous puzzle in this series

Stack of Coins 2

Try These Next

Coin Weighing 3

Pirates and Coins

The Infinite Chocolate Bar