9
$\begingroup$

Find all functions $f:\mathbb{N}\to\mathbb{N}$ which satisfy $$ (n-1)^{2020}<\prod_{k=1}^{2020}f^{(k)}(n)<n^{2020}+n^{2019}\quad\quad\text{for all }n\in\mathbb{N}, $$ where $\mathbb{N}$ is the set of natural numbers (not including zero) and $f^{(k)}$ is the composite function $f\circ f\circ\dots\circ f$ ($k$ times).

This puzzle was shared with me by someone who found it online but couldn't remember where. It's probably from an olympiad or something; I had no luck finding the original source, but I wanted to share it here because it has such a nice elegant solution.

$\endgroup$
1
  • 1
    $\begingroup$ I haven't seen this exact problem before, but it seems to be a general version of Canada MO 2015 P1 (link contains spoilers). $\endgroup$
    – Ankoganit
    May 26 '20 at 4:03
10
$\begingroup$

The set of functions which satisfy this condition is:

Only the identity function $f(n) = n$. Let $f$ be any function satisfying this condition. Since $(1-1)^{2020} = 0$ and $1^{2020}+1^{2019} = 2$, we must have $f(1)=1$. Let $m>1$ be the smallest integer such that $f(m) \neq m$. First note that $f(m) > m$, for if not we have $f(m)<m$ which implies $f^{(k)}(m)=f(m)\leq m-1$ for all $k \geq 1$ and thus $$(m-1)^{2020} < \displaystyle\prod_{k=1}^{2020}f^{(k)}(m) \leq (m-1)^{2020}$$ This is a contradiction, so we must have $f(m) > m$.

Next step:

Since $f(m) >m$ we must have $f(m) \geq m+1$. Thus we have $$\displaystyle (m+1)\prod_{k=2}^{2020}f^{(k)}(m) \leq \prod_{k=1}^{2020}f^{(k)}(m) < m^{2020}+m^{2019}$$ which implies $$\prod_{k=2}^{2020}f^{(k)}(m) < m^{2019}$$ Since $f(m) > m$, there must exist a smallest $\ell$ with $2 \leq \ell \leq 2020$ such that $f^{(\ell)}(m) < m$ from which it follows that $f^{(\ell-1)}(m) \geq m$ and $f^{(k)}(m) \leq m-1$ for all $k \geq \ell$.

Finally:

Let $L = f^{(\ell-1)}(m)$. Then we have $$(m-1)^{2020} \leq (L-1)^{2020} < \displaystyle\prod_{k=1}^{2020}f^{(k)}(L) = \prod_{k=\ell}^{\ell+2019}f^{(k)}(m) \leq (m-1)^{2020}$$ This is the final contradiction, showing that there can exist no smallest $m$ with $f(m) \neq m$. This proves $f$ must be the identity.

$\endgroup$
2
  • $\begingroup$ Great deduction! This looks like exactly the same logic I used to solve it. $\endgroup$ May 25 '20 at 22:04
  • 2
    $\begingroup$ Wow, I am learning functional equations for olympiads and I will definitely bookmark this page for my reference! $\endgroup$ May 26 '20 at 0:57

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .