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
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.
18.11.2022 20:01
Solved with BarisKoyuncu and sevket12.