Problem 4. Polycarp has 2 boxes, the first of which contains $n$ coins, and the second is empty. In one move, he can either transfer one coin from the first box to the second, or remove exactly $k$ coins from the first box, where $k$ is the number of coins in the second box. For which $n$ can Polycarp make the first box empty in no more than 10 moves?

Answer: for $n$ from 0 to 30 inclusive.
Solution. Let's call a move where one coin is moved from the first box to the second box a move of the first type, and a move where coins are removed from the first box a move of the second type. Suppose a total of $x$ moves of the first type and $y$ moves of the second type were made. Then, the second box contains no more than $x$ coins. Therefore, when performing moves of the second type, we will remove no more than $x y$ coins from the first box, meaning we will remove no more than $x + x y$ coins in total. Since $x + y \leqslant 10$, then

$$
x + x y \leqslant x + x(10 - x) = -x^2 + 11x
$$

For integer values of $x$, the maximum of this expression is achieved at points $x = 5$ and $x = 6$ and is equal to $5 \cdot 6 = 30$. Thus, $n \leqslant 30$. We will prove that any $n \leqslant 30$ works.

If we make 5 moves of the first type and then 5 moves of the second type, we will remove exactly 30 coins from the first box. Write down the sequence of 1s and 2s, where 1 represents a move of the first type and 2 represents a move of the second type. Notice that if in this sequence we swap a neighboring pair 12 to a pair 21, the total number of coins removed from the first box will decrease by 1. We can do this until all 2s are on the left and all 1s are on the right. Then we will replace 1 with 2, and on each step, the number of coins removed using such a sequence of operations will also decrease by 1. Thus, for any $n$ from 0 to 30, we can provide the required sequence of operations.

## Criteria

The following single most appropriate criterion is used:

7 6. Any complete solution to the problem.

If in the solution $n$ is considered a natural number, and the number 0 is not mentioned in the answer, the score is not reduced.

4 b. It is proven that $n$ does not exceed 30, but it is not explained why all smaller $n$ also work.

3 6. All examples for $n$ from 1 to 30 are described.

For the following error in a solution that otherwise fits one of the criteria above, the score is reduced:

-1 6. The maximum value of the expression $-x^2 + 11x$ for integer $x$ is found incorrectly due to an arithmetic error.