2014 USAJMO Problems/Problem 4

Revision as of 18:51, 18 August 2015 by Swagger21 (talk | contribs) (Solution)

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