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 integers 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.
Solution 2 (Simple)
Let . It is easy to see that , and , because the digits of are and . Additionally, if we take any number, let's say , and multiply it by , and then add it to and , we still obtain , because we are simply adding to each value.
Thus, we conclude that there are infinitely many numbers that are counted twice in , and that these numbers come apart. Finally, it is clear that for a large , the number of numbers that are counted at least twice is at least . Because for all , this means that there are at least numbers uncounted, and because this is unbounded, the proof is complete.
Operation Intuitive Number Theory (INT)- Solution 2
I hope this solution is quite intuitive, because it is without complicated notation. It didn't take me very long to discover. As with Solution 1, define . We will use numbers from to for induction. Call this interval Class .
Start with and go up to . There are numbers covered. Easily ranges from to , or a range of . Thus, there are at LEAST numbers lacking coverage. Now, in order to fill up these gaps, we consult Class : to . If we are to fill up all these gaps, then we need at least numbers in the next series with their values. Unfortunately, there are only at MOST numbers that can satisfy a value, from to , otherwise the value is too big (note that none of them are zero)! Thus, between Class 0 and 1, there is at least one value lacking.
After setting up the base case, consider the Class numbers from to there are clearly integers. Yet the can range from to . This gives a range of . This leaves an extra numbers. Now, we invoke the next class: . Again, to fill in the gap there are sadly only numbers available: to , because is at least 1.
By induction we are done. Because each Class for integral at least misses at least one value, we miss an infinite number of numbers. Game over!
Note: If you are unconvinced of the range of values we go from the smallest value of both the number and the , or and , to the greatest of both, i.e. and , because in that series the largest possible sum is a bunch of s.