2014 USAJMO Problems/Problem 4
Contents
Problem
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.
Solution 1
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 disjoint 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.
~mathboy100
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.