Nim Game: Use mod to prove winning strategy when we start first and we have 1, 2 or 3 stones to choose from You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
Approach: if the number of stones is a multiple of $4$ we lose otherwise we win.
I found this useful analysis too:
Analysis:
Let's first simulate the game with a small number of stones, say 4. We will take the first turn to remove the stones.
If there are 4 stones, we have three options, take 1, 2 or 3 stones:
We take 1, 3 left
We take 2, 2 left
We take 3, 1 left
Then it's opponent's turn, assume they are doing their best to win the game:

*

*We take 1, 3 left, opponent take 3, opponent win, we lose

*We take 2, 2 left, opponent take 2, opponent win, we lose

*We take 3, 1 left, opponent take 1, opponent win, we lose

Note that, if it is our turn and there are n stones, say it is a must-win, then for the opponent facing n stones, it is a must-win for the opponent, and for us it becomes a must-lose case.
What about 5 stones:

*

*We take 3, 2 left, opponent take 2, opponent win, we lose

*We take 2, 3 left, opponent take 3, opponent win, we lose

We take 1, 4 left, now opponent has 3 options:

*

*opponent take 1, 3 left, then we take 3, we win, opponent lose

*opponent take 2, 2 left, then we take 2, we win, opponent lose

*opponent take 3, 1 left, then we take 1, we win, opponent lose

From this observation, we could see that:
We have to make the number of stones to 4 after our pick, so that opponent must lose and we must win.
There are 3 possibilities: when there are 4+1=5, 4+2=6 or 4+3=7 stones, we could make it 4 after we pick 1, 2 and 3 stones, respectively.
If the number of stones is times of 4, we will never win the game. Say there are 16 stones, we choose n stones, no matter how we choose, the opponent could always pick 4-n stones to make the number of stones still times of 4, until we met 4 stones, and we will lose.
Question: how we should proceed with modular arithmetic to prove this please? How do we know that all other options will lose if multiple of 4? Can we say that $1 \equiv n \bmod{7}, 2 \equiv n \bmod{7}, 3 \equiv n \bmod{7}$ then we win?
 A: If there are $4$ stones, then after our turn the number of stones is between $1$ and $3$, and so the opponent can win.
If there are $8$ stones, then after our turn the number of stones is between $5$ and $7$, and so our opponent can pick the right number of stones so that it is our turn with $4$ stones to play, which by above, means we lose again.
If there are $12$ stones, then after our turn there are between $9$ and $11$ stones, so our opponent can make it such that it's our turn with $8$ stones, so by above, we lose again.
In general, if there are $4n$ stones, after our turn there are between $4n-3$ and $4n-1$ stones, so by choosing to remove between $1$ and $3$ stones our opponent can make it our turn with $4n-4$ stones. The formal proof that we always lose is by induction, though it should be clear enough without explicitly writing it out.
If the number of stones is anything other than a multiple of $4$, then by removing between $1$ and $3$ stones we put our opponent at the situation where it's their turn with $4n$ stones to play, hence we win.
