Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2014 USAJMO Problems/Problem 4

Problem

Let $b\geq 2$ be an integer, and let $s_b(n)$ denote the sum of the digits of $n$ when it is written in base $b$. Show that there are infinitely many positive integers that cannot be represented in the form $n+s_b(n)$, where $n$ is a positive integer.

Solution 1

Define $S(n) = n + s_b(n)$, and call a number unrepresentable if it cannot equal $S(n)$ for a positive integer $n$. We claim that in the interval $(b^p, b^{p+1}]$ there exists an unrepresentable number, for every positive integer $p$.

If $b^{p+1}$ is unrepresentable, we're done. Otherwise, time for our lemma:

Lemma: Define the function $f(p)$ to equal the number of integers x less than $b^p$ such that $S(x) \ge b^p$. If $b^{p+1} = S(y)$ for some y, then $f(p+1) > f(p)$.

Proof: Let $F(p)$ be the set of integers x less than $b^p$ such that $S(x) \ge b^p$. Then for every integer in $F(p)$, append the digit $(b-1)$ to the front of it to create a valid integer in $F(p+1)$. Also, notice that $(b-1) \cdot b^p \le y < b^{p+1}$. Removing the digit $(b-1)$ from the front of y creates a number that is not in $F(p)$. Hence, $F(p) \rightarrow F(p+1)$, but there exists an element of $F(p+1)$ not corresponding with $F(p)$, so $f(p+1) > f(p)$.

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 $f(n) = n + s_b(n)$. It is easy to see that $f(b^2) = b^2 + 1$, and $f(b^2 - b + 1) = b^2 - b + 1 + b - 1 + 1 = b^2 + 1$, because the digits of $b^2 - b + 1$ are $b-1$ and $1$. Additionally, if we take any number, let's say $x$, and multiply it by $b^3$, and then add it to $b^2$ and $b^2 - b + 1$, we still obtain $f(b^3x + b^2) = f(b^3x + b^2 - b + 1)$, because we are simply adding $b^3x + s_b(x)$ to each value.

Thus, we conclude that there are infinitely many numbers that are counted twice in $f(n)$, and that these numbers come $b^3$ apart. Finally, it is clear that for a large $N$, the number of numbers that are counted at least twice is at least $\left\lfloor\frac{N}{b^3}\right\rfloor$. Because $f(n) > n$ for all $n$, this means that there are at least $\left\lfloor\frac{N}{b^3}\right\rfloor$ 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 $S(n)=n+s_b(n)$. We will use numbers from $b^k$ to $b^{k+1}-1$ for induction. Call this interval Class $k$.

Start with $b^0=1$ and go up to $b-1$. There are $b-1$ numbers covered. Easily $S(n)$ ranges from $1+1=2$ to $b-1+b-1=2b-2$, or a range of $2b-3$. Thus, there are at LEAST $b-2$ numbers lacking coverage. Now, in order to fill up these gaps, we consult Class $1$: $b^1=b$ to $b^2-1$. If we are to fill up all these gaps, then we need at least $b-2$ numbers in the next series with their $S$ values. Unfortunately, there are only at MOST $b-3$ numbers that can satisfy a value, from $b$ to $2b-3$, otherwise the $S$ 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 $k$ numbers from $b^k$ to $b^{k+1}-1$ there are clearly $b^{k+1}-b^k$ integers. Yet the $S(n)$ can range from $b^k+1=b^k+1$ to $(b^{k+1}-1)+(k+1)(b-1)=b^{k+1}+b(k+1)-(k+1)$. This gives a range of $b^{k+1}-b^k+b(k+1)-(k+1)$. This leaves an extra $b(k+1)-(k+1)$ numbers. Now, we invoke the next class: $k+1$. Again, to fill in the gap there are sadly only $b(k+1)-(k+2)$ numbers available: $b^{k+1}$ to $b^{k+1}+b(k+1)-(k+3)$, because $s_b(n)$ is at least 1.

By induction we are done. Because each Class $k$ for integral $k$ at least $0$ misses at least one $S$ value, we miss an infinite number of numbers. Game over!

Note: If you are unconvinced of the range of $S(n)$ values we go from the smallest value of both the number and the $s_b(n)$, or $b^k$ and $1$, to the greatest of both, i.e. $b^{k+1}-1$ and $k(b+1)$, because in that series the largest possible sum is a bunch of $b-1$s.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_USAJMO_Problems/Problem_4&oldid=220994"