2014 USAJMO #4

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.



Since this is a strange problem, we will develop strange methods. 

Denote $\text{strange}(n) = n + s_b(n)$. Pick some arbitrary integer $M$. Notice that $$\text{strange}(x) > b^{2M} \forall x \ge b^{2M}$$ and $$\text{strange}(b^{2M}-k) \ge b^{2M} \forall 1 \le k \le M$$, because the base-$b$ expansion of $b^{2M}-k$ will start with at least $M$ digits equal to $b-1$. 

Hence, the function $\text{strange}$ excludes $M$ values in the range $[1, b^{2M})$ for any arbitrary $M$, so there are infinitely many positive integers that can't possibly by expressed like $n+s_b(n)$, as desired.  $\square$ 



Comments

Popular posts from this blog

1995 IMO #2

Inequality problem I made