Two players are playing a game in which each have to pick $3$, $4$ or $7$ coins in each turn. There are $2009$ coins in total. Find the player who can win the game and mention their strategy if the last one who can pick any number of coins, is the winner.
Solved!
On
By trial and error, I noticed that if the remaining number of coins is $n \leq 22$, and it is your turn to select a coin, then you can guarantee a win unless the number of coins is an element in $\{1,2,10,11,12,20,21,22\}.$
This was determined by working backwards. For example, if there are $6$ coins left, you can take $4$ coins, forcing your opponent to have the losing position of having only $2$ coins left.
This leads to the inductive hypothesis, that if it is your turn, and $n > 22$, then you are in a losing rather than winning position if and only if the least non-negative residue of $n \pmod{10}$ is an element in $\{0,1,2\}.$
Proof of hypothesis:
If the least non-negative residue is $0$, then your move will leave a least non-negative residue of either $7,6,$ or $3$. If you leave a $3$ or a $7$, your opponent can then convert it back to a $0$. If you leave a $6$, your opponent can convert it to a $2$.
If the least non-negative residue is $1$, then your move will leave a least non-negative residue of either $8,7,$ or $4$. If you leave a $8$ or a $4$, your opponent can then convert it back to a $1$. If you leave a $7$, your opponent can convert it to a $0$.
If the least non-negative residue is $2$, then your move will leave a least non-negative residue of either $9,8,$ or $5$. If you leave a $9$ or a $5$, your opponent can then convert it back to a $2$. If you leave an $8$, your opponent can convert it to a $1$.
Suppose instead that it is your move and the least non-negative residue is some element in $\{3,4,5,6,7,8,9\}$.
It is easy to verify that in all $7$ cases, above, you can force your opponent to be on move, where the least non-negative residue will be an element in $\{0,1,2\}.$
Thus, the person on move when there are $2009$ coins has exactly $1$ winning move: take $7$ coins. Any other move allows the opponent to win.
On
If there are 0,1,2 coins left, you lose as you cannot pick up any more coins.
If there are 3,4,5,6,7,8,9 coins left, you win, as you can pick up any number of coins required to leave 0,1,2 coins left for the opponent.
If there are 10,11,12 coins left, you lose, as however many coins you pick up, you will leave 3,4,5,6,7,8,9 coins left for the opponent.
If there are 13,14,15,16,17,18,19 coins left, you win, as you can pick up any number of coins required to leave 10,11,12 for the opponent
This pattern appears to repeat every 10 numbers, because for any number 3-9, there exists a number in the set {3,4,7} you can subtract to leave 0,1,2. (You can brute force this if it isn't obvious)
Likewise for any number ending in 0-2, subtracting any number from the set {3,4,7} will yield a number 3-9.
This shows that if you start on any number that ends with 3-9 i.e 2009, you can win by subtracting the amount required to leave a number 0-2. The only option in this case is to take away 7.
If it's a player's turn to pick coins, and there are $3,4,5,6,7,8,9$ coins, then the player is the winner (because either he can pick all the coins or just $1$ or $2$ coins are left for the other one, which is not allowable).
Hence, if it's a player's turn to pick coins, and there are $10, 11, 12$ coins, the player is the loser (simply because, regardless of the number of coins the player picks, the other player, in the next turn has $3, 4,5,6,7,8 $ or $9$ coins).
Now, if it's a player's turn to pick coins, and there are $13,14,15,16,17,18,19$ coins, then the player is the winner because he can easily make the other player have $10, 11, 12$ coins in the next turn.
In a similar way, if it's a player's turn to pick coins, and there are $10k+3,10k+4,10k+5,10k+6,10k+7,10k+8,10k+9$ coins where $k$ is a natural number, then the player is the winner.
At the beginning of the game, there are $2009$ coins, and it's the first player's turn to pick coins; therefore the first player is the winner.