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$ – Rand al'Thor 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$ – Culver Kwan May 26 '20 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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