Found this game in a tiktok filter, tried to solve it and got stuck.
Consider a game of nim, with a single pile of N stones. On their turn, each player can remove either one or two stones. The winning player is the player to remove the last stone. My conjecture is that player 1 has a winning strategy for all positive integers n.
This screams induction to me, so I made my base cases:
n = 1 -> Player 1 wins (by taking the only stone)
n = 2 -> Player 1 wins (by taking both stones)
And my inductive hypothesis:
For any integer k s.t 1 ≤ k ≤ m (where m is an arbitrary positive integer), when n = k, there exists a winning strategy for player 1.
Now, I'm having a really hard time proving the conjecture holds for n = m + 1. For example, when player 1 chooses to take 1, player 2 is left with m remaining. By our ind. hyp, this implies player 2 should win, which obviously is the opposite of what I'm trying to prove. Similarly, when player 1 starts by taking 2 stones, player 2 is left facing m-1 stones, which, again, is a winning position by my inductive hypothesis.
I don't think I'm on the right track. I think I'm missing something crucial regarding the parity of n, but I'm honestly not sure. I also noticed that player 2 wins when n = 3, and player 1 wins when n = 4, so I think I might need to in some way modify the conjecture. I think (but I'm not sure how to prove) that player 2 wins if 3 | n. I didn't make trees, but I played a few games of n = 6 and n = 9 by hand, and both times I won as player 2. I made game trees for when n = 3 and n = 4 to help wrap my head around it.
Game tree for n = 3 Game tree for n = 4
Anyone know where I'm going wrong? Thanks!
If $n \equiv 0\pmod 3$ player 2 wins. The strategy is as follows:
-If player 1 takes $1$ stone, player 2 takes $2$ stones
-If player 1 takes $2$ stones, player 2 takes $1$ stone
Notice that after that, there are $n-3$ stones in the pile. If $n-3=0$ player 2 won, else, repeat the strategy. We can note that $0 \equiv 0 \pmod 3$, and after player 1 moves will never be a number of coins divisible by $3$ (if player 2 uses this strategy), so it's impossible for player 1 to win. In this game there are no draw and the game will eventually ends, so the winner will be player 2.
If $n \equiv 1, 2\pmod 3$ player 1 wins. The strategy is quite similar to the other case:
-If $n \equiv 1\pmod 3$ player 1 takes $1$ stone
-If $n \equiv 2\pmod 3$ player 1 takes $2$ stones
Now, we can imagine the game is just beggining, and the first player is player 2, player 1 takes the role of the second player and now the number of stones in the pile is divisible by $3$, so player 1 (who is playing second now) will use the strategy of the first case and he will eventually win.
Just in case, $n \equiv k\pmod m$ is a way to express that $n-k$ is divisible by $m$, or, equivalent, that $n$ and $m$ have the same rest in the division by $m$.