Sarin S.

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$ of them. 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 admitted 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 all of them are greater than $k_i$). In particular, after 2011 moves, the exact value of $k_{2012}$ may remain unknown.

## Answer

2012 moves.