Bump.........

Solve it for $n$ instead of $2012$. I claim the answer is $n$. If the number is of form $1 \ 0^{a_1}1 \ 0^{a_2}...1\ 0^{a_n}$ then whatever my first guess is, it is possible that $a_n$ is bigger. It can be seen that if my guess is $1$ then I get to know $a_n$ and there is no possibility to get more info than that. Simple induction shows the answer is $n$. EDIT: I might have been not general enough with the strategy . If the number has other digits than 0 or 1 I can think of a_i as $-1$ . I.e. if last digits of my number are 20 then my first query is 1 and I learn the second to last digit is >=1. Then I ask 20 and learn that second to last digit is >=2. Then I ask 30 and learn the position of the next nonzero digit, etc.

The answer is $2012$, and in general, if $2012$ is replaced by $n$ the answer is $n$. Let $N$ denote Peter's number. For Paul's algorithm, Paul can start by picking $1$. Then Peter's reply will be exactly $n-1+9k$, where $k$ is the number of trailing zeros at the end of $N$. So, Paul learns the position of the rightmost nonzero digit of $N$. Now, observe that if Paul increases all his future guesses by $10^k$, he is essentially playing the same game with $N-10^k$. This is a number with sum of digits $n-1$, so induction gets the desired result. Now we show $n$ moves are needed. Suppose Peter pre-commits to choosing a number of the form \[ N = 1 \underbrace{0\dots0}_{a_1} 1 \underbrace{0\dots0}_{a_2} 1 \underbrace{0\dots0}_{a_3} \dots 1 \underbrace{0\dots0}_{a_n} \]and even announces this to Paul. On Paul's turn, he must start by picking some number, and if his number turns is less than $10^{a_n}$, he will only learn the value of $a_n$. The same argument applies with $10^{a_{n-1}+1+a_n}$ on the next turn, in which Paul's second turn only tells him the value of $a_{n-1}$ if his number is not large enough. And so on. This shows that at least $n$ moves are necessary.