# 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 intervals containing an unrepresentable number, there are infinitely many unrepresentable numbers.

## 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.