Let $\mathbb{N}$ be the set of positive integers. Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function such that for every positive integer $n \in \mathbb{N}$ $$ f(n) -n<2021 \quad \text{and} \quad f^{f(n)}(n) =n$$Prove that $f(n)=n$ for infinitely many $n \in \mathbb{N}$
Problem
Source: Switzerland Final Round 2021 P6
Tags: function, algebra, nice problem
24.02.2021 11:13
Kimchiks926 wrote: Let $\mathbb{N}$ be a set of positive integers. Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function such that for every positive integer $n \in \mathbb{N}$ $$ f(n) -n<2021 \quad \text{and} \quad f^{f(n)}(n) =n$$Prove that $f(n)=n$ for infinitely many $n \in \mathbb{N}$ $f^{[f(n)]}(n)=n$ immediately implies $f(x)$ bijective Note that if $f(n)=1$, we have $f^{(1]}(n)=n$, which is $f(n)=n$ and so $n=1$ Let $m>1$ and $n$ such that $f(n)=m$. We have $f^{[m]}(n)=n$$\implies$ $f^{[m-1]}(f(n))=n$ $\implies$ $f^{[m-1]}(m)=n$ And so (taking $f(.)$ of both sides) : $f^{[m]}(m)=f(n)=m$ And so $f^{[n]}(n)=n$ $\forall n\in\mathbb Z_{>0}$ Let $g(n)$ be the smallest positive integer $k$ such that $f^{[k]}(n)=n$ $f^{[f(n)]}(n)=n$ implies that $g(n)|f(n)$ $f^{[n]}(n)=n$ implies that $g(n)|n$ Let then any prime $p>2021$ : $g(p)|p$ and so : Either $g(p)=1$ and so $f(p)=p$ Either $g(p)=p$ and so $f(p)\ne p$ (else $g(p)=1$) and $p|f(p)$ and so $p+2021>f(p)\ge 2p$ which implies $p<2021$, wrong And so $\boxed{f(p)=p\quad\forall\text{ prime }p>2021}$ Q.E.D.
08.04.2021 03:05
Kimchiks926 wrote: Let $\mathbb{N}$ be a set of positive integers. Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function such that for every positive integer $n \in \mathbb{N}$ $$ f(n) -n<2021 \quad \text{and} \quad f^{f(n)}(n) =n$$Prove that $f(n)=n$ for infinitely many $n \in \mathbb{N}$ It should say that $\mathbb{N}$ is the set of positive integers. Otherwise, it could be interpreted as if it were any set. We could then take, for example, $\mathbb{N}=\{1\}$ and $f(1)=1$, which clearly satisfies the given conditions but contradicts what the problem asks.
24.12.2021 22:31
pco:very nice solution