The function $f : N \to N$ is defined by $f(n) = n + S(n)$, where $S(n)$ is the sum of digits in the decimal representation of positive integer $n$. a) Prove that there are infinitely many numbers $a \in N$ for which the equation $f(x) = a$ has no natural roots. b) Prove that there are infinitely many numbers $a \in N$ for which the equation $f(x) = a$ has at least two distinct natural roots. (I. Voronovich)
Problem
Source: Belarus 2010 TST 8.1
Tags: sum of digits, number theory, roots
kaede
02.04.2020 16:55
It is sufficient to prove that the following proposition $ P( n)$ is true for any $ n\in \mathbb{N}$
Proposition $ P( n)$
There does not exist $ x\in \mathbb{N}$ such that $ f( x) =f\left(\left( 10^{n} -1\right) /3\right) +1$.
Proof
For each $ n\in \mathbb{N}$, let $ g( n) =f\left(\left( 10^{n} -1\right) /3\right) +1$.
It is not difficult to verify that $ P( 1)$ is true.
Suppose that $ P( k)$ is true for some $ k\in \mathbb{N}$.
Assume, for the sake of contradiction, $ P( k+1)$ is false.
Then we can take $ x\in \mathbb{N}$ such that $ f( x) =g( k+1) \cdots ( \clubsuit )$.
Note that $ g( k+1) =\left( 10^{k+1} -1\right) /3+3k+5\ \cdots ( \diamondsuit )$.
If $ x\geq 10^{k+1}$, then $ 10^{k+1} < f( x)$, which is impossible.
If $ x< 3\cdot 10^{k}$, then $ f( x) \leq \left( 3\cdot 10^{k} -1\right) +( 9k+2)$, which is impossible.
So we must have $ 3\cdot 10^{k} \leq x< 10^{k+1}$.
So we can take $ r\in \mathbb{N}$ such that $ x=3\cdot 10^{k} +r$ and $ r< 7\cdot 10^{k}$.
Thus $ f( x) =x+S\left( 3\cdot 10^{k} +r\right) =x+S\left( 3\cdot 10^{k}\right) +S( r)$
$ =3\cdot 10^{k} +r+3+S( r) =f( r) +3\cdot 10^{k} +3$.
It follows that $ f( x) =f( r) +3\cdot 10^{k} +3\ \cdots ( \heartsuit )$.
From $ ( \diamondsuit )$, we have $ g( k+1) -g( k) =3\cdot 10^{k} +3\ \cdots ( \spadesuit )$.
From $ ( \heartsuit )$,$ ( \spadesuit )$, and $ ( \clubsuit )$, we have $ 0=f( x) -g( k+1) =f( r) -g( k)$.
This contradicts that $ P( k)$ is true.
Therefore, $ P( k+1)$ is true.
Hence $ P( n)$ is true for any $ n\in \mathbb{N}$ by mathematical induction.
$ \blacksquare $
Let $ k$ be a positive integer and $ m=\left( 10^{k} +9k-1\right) /9$.
Then we can verify that $ f\left( 10^{m} -2\right) =f\left( 10^{m} +10^{k} -3\right) =10^{m} +9m-3.$
Hence $ a=10^{m} +9m-3$ satisfies the condition where $ m=\left( 10^{k} +9k-1\right) /9$.
$ \blacksquare $