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, 2020 at 4:03

1 Answer 1

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, 2020 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, 2020 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.