A large number of rocks are placed on a table. On each turn, one may remove some rocks from the table following these rules: on the first turn, only one rock may be removed, and on every subsequent turn, one may remove either twice as many rocks or the same number of rocks as they have discarded on the previous turn. Determine the minimum number of turns required to remove exactly $2012$ rocks from the table.
Problem
Source:
Tags: combinatorics
mihirb
27.04.2015 02:01
Looks like recursion?
BobaFett101
27.04.2015 06:46
Do we just express 2012 in base 2 and add the digits?
flyingpurplepeopleeater
03.06.2015 08:15
We cannot use bobas method since for 101 we would have to multiply by 4 to get the next number. So if the largest number we use is $2^n$, we have to use at least one of every $2^x$ for all 0<=x<=n. Once we have subtracted that, however, we can add the digits of the binary representation of the remainder. Since 1023<2012<2047, the largest number we will use is 512. After using every power of 2 from 1 to 512, we have used up 1023. So after 10 moves, our total is 989. The binary representation is 1111011101, so after 8 more moves, or $\boxed{18}$ total, we're done.