Let $Z^+$ be positive integers set. $f:\mathbb{Z^+}\to\mathbb{Z^+}$ is a function and we show $ f \circ f \circ ...\circ f $ with $f_l$ for all $l\in \mathbb{Z^+}$ where $f$ is repeated $l$ times. Find all $f:\mathbb{Z^+}\to\mathbb{Z^+}$ functions such that $$ (n-1)^{2020}< \prod _{l=1}^{2020} {f_l}(n)< n^{2020}+n^{2019} $$for all $n\in \mathbb{Z^+}$
Problem
Source: 2020 Turkey TST P4
Tags: function, Inequality, inequalities
14.03.2020 16:27
15.03.2020 09:06
$f(1)=1$ is obvious. Now let $n$ be the smallest positive integer such that $f(n)\neq n$. ($n\geq2$). We have $f(i)=i$ for $i=\{1,2,\cdots n-1\}$. $f(n)\neq n\Rightarrow$ $(i)$ $f(n)<n$. Then let $f(n)=c$. Since $c<n$, we have $f(c)=c$.So $$\prod _{l=1}^{2020} {f_l}(n)=c.\prod _{l=1}^{2019} {f_l}(c)=c^{2020}$$Then $ (n-1)^{2020}< c^{2020}< n^{2020}+n^{2019}<(n+1)^{2020}\Rightarrow c=n$, a contradiction. $(ii)$ $f(n)>n$. Then let $\boxed{f(n)=c\geq n+1}$. We have $$\prod _{l=1}^{2020} {f_l}(n)=c.\prod _{l=1}^{2019} {f_l}(c)< n^{2020}+n^{2019}=(n+1)n^{2019}\overbrace{\Rightarrow}^{c\geq n+1} \prod _{l=1}^{2019} {f_l}(c)< n^{2019}\cdots(i)$$ So for some $i=\{1,2,\cdots2019\}$, we must have $f_i(c)<n$. Let $q$ be the smallest among them. Since $f_q(c)<n$, we have $f_r(c)=f_q(c)$ for $r\geq q$. Let $f_q(c)=a<n$. So we can rewrite $(i)$ like this: $$\prod _{l=1}^{2019} {f_l}(c)=\left(\prod _{l=1}^{q-1}{f_l}(c)\right).(f_q(n))^{2020-q}=\left(\prod _{l=1}^{q-1}{f_l}(c)\right).a^{2020-q}< n^{2019}\cdots (ii)$$ Also the main inequality must hold for $n=c$ which yields $$(c-1)^{2020}< \prod _{l=1}^{2020} {f_l}(c)< c^{2020}+c^{2019}$$Again we can rewrite it as: $$(c-1)^{2020}< \left(\prod _{l=1}^{q-1} {f_l}(c)\right).(f_q(c))^{2021-q}=\left(\prod _{l=1}^{q-1} {f_l}(c)\right).a^{2021-q}< c^{2020}+c^{2019}\cdots(iii)$$ Merge $(ii)$ and $(iii)$ to get the final contradiction: $$\frac{(c-1)^{2020}}{a^{2021-q}}\overbrace{<}^{(iii)}\left(\prod _{l=1}^{q-1} {f_l}(c)\right)\overbrace{<}^{(ii)}\frac{n^{2019}}{a^{2020-q}}\Rightarrow (c-1)^{2020}<n^{2019}.a\overbrace{<}^{a<n}n^{2020}\Rightarrow c-1<n\rightarrow \boxed{c<n+1}$$Again, a contradiction. So such $n$ doesn't exist, which means we have $f(n)=n$ for all $n$.
05.01.2022 15:39
Strong induction
07.01.2022 00:25
Good problem and solution