Sarin C.

Petya and Vasya are playing the following game. Petya thinks of a natural number $x$ with the sum of its digits being 2012. In one move, Vasya chooses any natural number $a$ and finds out from Petya the sum of the digits of $|x-a|$. What is the minimum number of moves Vasya needs to make to guarantee determining $x$?
Let $S(n)$ denote the sum of the digits of the number $n$.

Algorithm. On the first move, Vasya names 1. If the number $x$ ends with $k$ zeros, then $S(x-1) = 2011 + 9k$. Thus, Vasya learns the position of the rightmost non-zero digit in $x$. Let $x_1 = x - 10^k$. Vasya knows that $S(x_1) = 2011$. By choosing a number $a$ on the second move such that $x - a = x_1 - 1$, Vasya learns how many zeros are at the end of $x_1$. Let there be $m$ zeros. Let $x_2 = x_1 - 10^m$. Then $S(x_2) = 2010$. By choosing a number $a$ on the third move such that $x - a = x_2 - 1$, Vasya learns how many zeros are at the end of $x_2$, and so on. After 2012 moves, he will get $S(x_{2012}) = 0$, thereby finding $x$.

Estimate. Suppose Petya admits that the number $x$ consists only of zeros and ones, that is, $x = 10^{k_{2012}} + 10^{k_{2011}} + \ldots + 10^{k_1}$, where $k_{2012} > k_{2011} > \ldots > k_1$. In this case, Vasya's task is to determine the values of the exponents $k_i$. Suppose Vasya is unlucky, and on the $i$-th move it turns out that $10^{k_i}$ is greater than the number $a$ presented by Vasya. Then, regardless of the values of $k_{2012}, \ldots, k_{i+1}$, $S(x - a) = S(10^{k_i} - a) + (2012 - i)$. Thus, nothing is known about the values of $k_{2012}, \ldots, k_{i+1}$ (except that they are all greater than $k_i$). In particular, after 2011 moves, the exact value of $k_{2012}$ may remain unknown.

## Answer

2012 moves.

Natural numbers from 1 to $n$ are arranged in a row in any order. An arrangement is called bad if in it one can mark 10 numbers (not necessarily consecutive) that are in decreasing order. All other arrangements are called good. Prove that the number of good arrangements does not exceed $81^n$.

## Hint

If an arrangement is good, then the numbers in the row can be colored in nine colors such that the numbers of each color are in increasing order.

## Solution

1) We will prove that if an arrangement is good, then the numbers in the row can be colored in nine colors such that the numbers of each color are in increasing order. Indeed, we will color the numbers from left to right, each time using the color with the smallest number such that the last number painted in this color is less than the current number. Suppose nine colors are not enough. We cannot paint the next number in the ninth color because a larger number has already been painted in the ninth color. This number was not painted in the eighth color because a larger number was encountered before it and painted in the eighth color. And so on. We end up with 10 numbers that are in decreasing order. 2) An arrangement of numbers from 1 to $n$ together with such a coloring in nine colors, where the sequence of numbers of each color is increasing, is completely determined by the color of each number from 1 to $n$ and the color of each position in the row. The numbers from 1 to $n$ can be colored in 9 colors in $9^n$ ways. And there are just as many ways to color $n$ positions in 9 colors. Thus, the number of good arrangements does not exceed $81^n$.