7. (40 points) To enter Ali Baba's cave, it is necessary to zero out 28 counters, each set to a natural number in the range from 1 to 2017. Treasure hunters are allowed, in one move, to decrease the values of some of the counters by the same number, which they can change from move to move. Indicate the minimum number of moves in which the treasure hunters can, with certainty, zero out the counters (regardless of the initial values) and enter the cave.
Answer: In 11 moves.

## Solution:

Estimation. Suppose the counters are set to all powers of two from 1 to 1024 and some 17 other numbers. Since the order of moves does not matter, we can arrange them in descending order of the numbers being subtracted. We will show by induction that after the $k$-th move, there is a number on the board that is not less than $2^{10-k}$. The base case - 0 moves - is obvious. Suppose after $k$ moves, there is a number on the board that is not less than $2^{10-k}$. If we subtract a number greater than $2^{10-k-1}$ on the $k$-th move, then this and the previous moves have not affected the number $2^{10-k-1}$, and the proof is complete. Otherwise, after the subtraction, there will be a number not less than $2^{10-k-1}$, which is not less than $2^{10-k}$. From the proven statement, it follows that after 10 moves, there will still be a number on the board that is not less than $2^{0}=1$, meaning that at least 11 moves are required.

Example. By subtracting $2^{10}$ from all numbers not less than $2^{10}$, we will make all numbers less than $2^{10}$. The next step will similarly make all numbers less than $2^{9}$, and so on. After the tenth step, all numbers will be less than $2^{0}=1$, that is, they will all be zeros.