2014 USAJMO Problems/Problem 4
Let be an integer, and let denote the sum of the digits of when it is written in base . Show that there are infinitely many positive integers that cannot be represented in the form , where is a positive integer.
Define , and call a number unrepresentable if it cannot equal for a positive integer . We claim that in the interval there exists an unrepresentable number, for every positive integer .
If is unrepresentable, we're done. Otherwise, time for our lemma:
Lemma: Define the function to equal the number of integer x less than such that . If for some y, then .
Proof: Let be the set of integers x less than such that . Then for every integer in , append the digit to the front of it to create a valid integer in . Also, notice that . Removing the digit from the front of y creates a number that is not in . Hence, , but there exists an element of not corresponding with , so .
Note that our lemma combined with the Pigeonhole Principle essentially proves the claim. Therefore, because there are infinitely many intervals containing an unrepresentable number, there are infinitely many unrepresentable numbers.