51st Ukrainian National Mathematical Olympiad, 3rd Round

Answer: $17$.

Note, that on each step the number of candies that Petro takes from the table is a power of $2$. Moreover, if at some step Petro takes away $2^n$ candies, then there were the moves where he was taking away $2,4,\dots ,2^{n-1}$. Thus, the maximum number that Petro could take can not exceed $512$, since $1+2+4+\dots +1024=2047>2011$.

We assume that Petro keeps optimal strategy. Note, that the number of steps when Petro takes away exactly $2^n$ candies can not exceed $2$, otherwise, he could reduce the number of moves by taking $2^{n+1}$ candies instead. This implies that he could not take less than $512$ candies each time because $2\cdot (1+2+4+\dots +256)=1022<2011$.

Therefore Petro was taking $1,2,\dots ,512$ candies. We write this in the following form: $a_0+2a_1+4a_2+\dots +512a_9=2011$, where $a_i\in \{1,2\}$ is the number of times he was taking $2^i$ candies. This is equivalent to: $a_0^{\prime }+2a_1^{\prime }+4a_2^{\prime }+\dots +512a_9^{\prime }=2011-(1+2+4+\dots +512)=988$, where $a_i^{\prime }=a_i-1,a_i^{\prime }\in \{0,1\}$.

Since binary representation is unique we have $a_i^{\prime },i=0,\dots ,9:0,0,1,1,1,0,1,1,1,1$, since $$988=512+256+128+64+16+8+4.$$ Hence, $a_i,i=0,\dots ,9$ have values $1,1,2,2,2,1,2,2,2,2$ and optimal number of steps is $3\cdot 1+7\cdot 2=17$.