Difference between revisions of "2014 USAJMO Problems/Problem 4"

(Solution)
m (Solution)
Line 3: Line 3:
 
==Solution==
 
==Solution==
 
Define <math>S(n) = n + s_b(n)</math>, and call a number ''unrepresentable'' if it cannot equal <math>S(n)</math> for a positive integer <math>n</math>.
 
Define <math>S(n) = n + s_b(n)</math>, and call a number ''unrepresentable'' if it cannot equal <math>S(n)</math> for a positive integer <math>n</math>.
We claim that in the interval <math>[b^p, b^{p+1})</math> there exists an unrepresentable number, for every positive integer <math>p</math>.
+
We claim that in the interval <math>(b^p, b^{p+1}]</math> there exists an unrepresentable number, for every positive integer <math>p</math>.
  
 
If <math>b^p</math> is unrepresentable, we're done. Otherwise, time for our lemma:
 
If <math>b^p</math> is unrepresentable, we're done. Otherwise, time for our lemma:

Revision as of 18:07, 30 April 2014

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