0
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Please edit to include your efforts. Working it out for small $n$ would be a good start. $\endgroup$
    – lulu
    Oct 16, 2022 at 11:48
  • $\begingroup$ 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. $\endgroup$
    – user978902
    Oct 18, 2022 at 19:28
  • $\begingroup$ So an odd number of coins is remains? $\endgroup$
    – user978902
    Oct 18, 2022 at 19:54
  • 1
    $\begingroup$ As I said before, work it out for small $n$ to see what happens. $\endgroup$
    – lulu
    Oct 18, 2022 at 20:10
  • $\begingroup$ No, it doesn't. And you got several of the smaller cases wrong. $\endgroup$
    – lulu
    Oct 18, 2022 at 21:00

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. I understand the $4-k$ part. But the $4m+1$ is still not clear for me. $\endgroup$
    – user978902
    Oct 18, 2022 at 20:03
  • $\begingroup$ 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 $\endgroup$
    – maxjw91
    Oct 19, 2022 at 8:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .