Find all functions $f$ from positive integers to themselves, such that the followings hold. $1)$.for each positive integer $n$ we have $f(n)<f(n+1)<f(n)+2020$. $2)$.for each positive integer $n$ we have $S(f(n))=f(S(n))$ where $S(n)$ is the sum of digits of $n$ in base $10$ representation.
Problem
Source: Iranian Third Round 2020 Number Theory exam Problem3
Tags: number theory, function, sum of digits
Euler365
24.11.2020 07:04
We claim that $f(x)=x$ is the only function which satisfies the given FE. Firstly, we see that $f(x)=x$ indeed satisfies the FE. Now we proceed to show that no other solutions exist. Claim 1: $f(1)=1$ Proof: $S(f(9))=f(S(9))\implies f(9)=S(f(9))$ which implies $f(9)$ is single digit number. Also note that $f:\mathbb{N}\rightarrow\mathbb{N}$ is strictly increasing implies $f(n)\geq n$. So $f(9)\geq 9$. Hence we obtain $f(9)=9$. This gives us $f(1)=1,f(2)=2,...f(8)=8$ as $f$ is strictly increasing. This proves our claim $1$. Claim 2: $f(10^n)$ is a power of $10$ $\forall$ $n\in\mathbb{N}$ Proof: $S(f(10^n))=f(S(10^n))=f(1)=1$. This implies that $f(10^n)$ must be a power of $10$. Claim 3: $\forall$ sufficiently large $n$, $f(10^n)=10^n$. Proof: Let $f(10^n)=10^k$ for some sufficiently large $n$. Note that $k\geq n$ as $f$ is strictly increasing implies $f(t)\geq t$ $\forall$ $t\in\mathbb{N}$. Now let $m=2.10^{\frac{10^n-1}{9}}-1$. Then $S(m)=10^n$. So $S(f(m))=f(S(m))=f(10^n)=10^k$. Now note that mimimum no. with sum of digits $10^k$ is $199...9$ where $9$ occurs $\frac{10^k-1}{9}$ times ie $2.10^{\frac{10^k-1}{9}}-1$. So $f(m)\geq 2.10^{\frac{10^k-1}{9}}-1$. Now if $k>n$ then we have $k\geq n+1$. But now note that $f(t+1)<f(t)+2020$ and $f(1)=1$ implies that $f(t)<2020t$. So we have $2020m>f(m)\geq 2.10^{\frac{10^{n+1}-1}{9}}-1\geq 10^{\frac{10^{n+1}-10^n}{9}}m$. This is clearly false for $n$ sufficiently large. So our assumption that $k>n$ was wrong. Also $k\geq n$. So we have $k=n$. This proves our claim. So now we have $f(n)=n$ for infinitely many $n\in\mathbb{N}$. Now $f$ is strictly increasing and $f(n)=n$ for infinitely many $n$ implies $f(n)=n$ $\forall$ $n\in\mathbb{N}$. Q.E.D.
hakN
18.11.2022 20:01
Solved with BarisKoyuncu and sevket12.
Notice that when $n$ is digit, $S(f(n))=f(n)$ thus $f(n)$ is also a digit, since $f$ is increasing, $f(i)=i$ for all $1 \leq i \leq 9$.
Now plugging $n=1$ we get for all $\alpha$, there exists $\beta \geq \alpha$ such that $f(10^{\alpha})=10^{\beta}$.
Also, if $f(10^{\alpha})=10^{\beta}$, then $10^{\beta+1} \leq f(10^{\alpha+1}) \leq 10^{\beta} + (10^{\alpha+1}-10^{\alpha})\cdot 2019$ which implies that $10^{\beta - \alpha} \leq 2019$, so $\beta - \alpha \leq 3$.
Plug $n = 10^{\alpha}-1$, since $f(10^{\alpha}-1) \leq f(10^{\alpha})-1 \leq 10^{\alpha+3}-1$, we get $f(9\alpha) = S(f(10^{\alpha}-1)) \leq 9(\alpha+3)$.
This implies that $f(9\alpha) = 9\alpha + c$ for all $\alpha \geq N$ where $0 \leq c \leq 27$ is a constant and $N\in \mathbb{N}$. This implies $f(n)=n+c$ for all $n \geq M$ for some $M$.
So $S(n+c)=S(n)+c$ for all large $n$, now let $n=10^k+\ell$ for $k$ large and $1 \leq \ell \leq 9$, we get $S(c+\ell)=\ell+c$, so for all $1 \leq \ell \leq 9$, $c+\ell$ is a digit which implies that $c=0$, hence $f(n)=n$ for all large $n$, together with $f$ increasing this implies $f(n)=n$ for all $n \in \mathbb{N}$, which clearly works.