Functional equation involving 2020th powers

Find all functions $$f:\mathbb{N}\to\mathbb{N}$$ which satisfy $$(n-1)^{2020}<\prod_{k=1}^{2020}f^{(k)}(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.

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

1 Answer

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) 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.

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