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

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 integer x less than $b^p$ such that $S(x) > b^p$ . If $b^{p+1} = S(x)$ for some x, then $f(p+1) \ge f(p)$ .

Proof: Let $F(p)$ be the set of integers x less than $b^p$ such that $S(x) > 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 $x > b * b^p$ . Removing the digit $(b-1)$ from the front of x creates a number that is not in $F(p)$ . Hence, $F(p) -> 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.

Page

Toolbox

Search

2014 USAJMO Problems/Problem 4

Problem

Solution