4. There is a pile of 2016 stones. Two players are playing a game. The first player can take either 1, 3, or 4 stones on each of their turns. The second player can take either 1, 2, or 3 stones on each of their turns. The player who cannot make a move loses. Who can win, no matter how the opponent plays?
Answer: The second.

## Solution:

The second player's strategy: each time leave a number of stones in the pile that gives a remainder of 2 when divided by 3. Note that he can do this after any move by the opponent, as his set of moves allows him to change the remainder of the remaining stones to any value. The first player cannot end the game with such a number of remaining stones, so the last move will remain with the second player.

The problem allows for a solution that does not require the second player to follow the non-obvious strategy of "making the remainder from division by 3 equal to 2" from the beginning of the game:

Consider the following strategy (for the second player).

The main idea of the solution: it is easy to see that if exactly 2 stones are left for the first player, then he (the first player) will lose, and the second player will win. Indeed, from a pile of 2 stones, the first can only take one, but then the remaining stone is taken by the opponent (the second), and he wins.

Let's analyze the actions of the second player depending on the number of stones in the pile before his move.

- If there are 1, 2, or 3 stones in the pile, the second player wins (he simply takes all the stones on his turn).
- If there are 4 or 5 stones in the pile, the second player takes 2 or 3 stones respectively, leaving the first player with a pile of 2 stones (in which case the first player loses).
- If there are 6, 7, or 8 stones in the pile, the second player takes 1, 2, or 3 stones respectively, leaving the first player with a pile of 5 stones. After this, no matter how many stones the first player takes, there will be stones left (it will be the second player's turn), and there will be fewer than five stones. But if the second player is left with fewer than 5 stones, the second player wins (the strategy has been considered above).
- If there are more than 8 stones in the pile, the second player simply takes any number of stones.

In other words, the second player makes moves as he pleases at the beginning of the game—until the number of stones (before his turn) is 8 or fewer. This moment will come, as after a couple of moves (by the first and second players), the number of stones decreases by at least 2 and at most 7 (that is, the second player will not miss the moment when he will play according to a meaningful strategy).

Instructions for checking:

Carefully follow the justification of the winning strategy for the second player and the justification of the possibility for the second player to make the next move.