Determine the number of positive integers for which there exist nonnegative integers such that .
, 2012
Solution
There are 16 such positive integers .
Let . We would like to represent as a sum of 2011 numbers of the form . To get such a representation, we can do in the following way. Starting from the number , each time we choose a number and break it into numbers , so that the sum of all numbers remains .
In view of the base representation of the numbers, if we can write
then we are able to obtain the numbers on the right by using the above operation repeatedly. Conversely, if we can obtain these numbers after some operations, then clearly their sum is by construction. Therefore, it remains to check for which we can apply finitely many operations so that we can generate exactly 2011 numbers.
Note that there are numbers more after applying each operation. Initially, there is only one number. Therefore, it is the same as finding those such that . As , there are solutions.