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.
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.