# Winning strategy with game of coins

Alice and Bob are playing a game. They choose a natural number $$n$$ and build a stack of $$n$$ coins. Taking turns, they can remove 1, 2 or 3 coins from this stack. The player that takes the last coin loses the game. Alice gets to play first. Suppose $$n$$ ≡ 1 mod 4. Prove that Bob always can win, independent of the moves Alice makes.

My first thought was writing $$n$$$$1$$ mod $$4$$ as $$4 \mid n -1$$. In other words, if $$n$$ is even and divisible by $$4$$, then Bob wins by taking 1 or 3 coins everytime. So, I think prove by induction should be used but I'm not sure how to start.

• Please edit to include your efforts. Working it out for small $n$ would be a good start.
– lulu
Oct 16, 2022 at 11:48
• Thank you. I tried for the basis $n = 1$, which gives $4 \mid 0$. For $x \in \mathbb{Z}$, we have $n-1 = 4x$. Then, the I.S gives $4 \mid n+1-1 = (n-1)+1 = 4x+1$. But $4x+1$ is not divisible by 4. I guess this is totally wrong. Oct 18, 2022 at 19:28
• So an odd number of coins is remains? Oct 18, 2022 at 19:54
• As I said before, work it out for small $n$ to see what happens.
– lulu
Oct 18, 2022 at 20:10
• No, it doesn't. And you got several of the smaller cases wrong.
– lulu
Oct 18, 2022 at 21:00

## 1 Answer

If Alice choses to remove $$k$$ coins for $$k=1,2,3$$, then Bob must remove $$4-k$$ coins. Therefore, when it is Alices turn to remove coins, the number of coins remaining will always be of the form $$4m+1$$. Therefore, after repeating this operation a certain amount of times, there will be only $$1$$ coin left on Alices turn, and so she will lose.

• Thank you for your answer. I understand the $4-k$ part. But the $4m+1$ is still not clear for me. Oct 18, 2022 at 20:03
• Well the number of coins you start with is of the form $4n+1$. Using this strategy, Alice and Bob remove $4$ coins between the $2$ of them and so when it is Alices $l$-th turn, there will be $4n+1-4(l-1)=4(n-l+1)+1$ coins remaining Oct 19, 2022 at 8:15