Find all $a\in\mathbb{N}$ such that exists a bijective function $g :\mathbb{N} \to \mathbb{N}$ and a function $f:\mathbb{N}\to\mathbb{N}$, such that for all $x\in\mathbb{N}$, $$f(f(f(...f(x)))...)=g(x)+a$$where $f$ appears $2009$ times. (tatari/nightmare)
Problem
Source: Mathcenter Contest / Oly - Thai Forum 2010 R1 p6 https://artofproblemsolving.com/community/c3196914_mathcenter_contest
Tags: algebra, functional equation
starchan
16.11.2022 07:34
I'm confused, doesn't setting $f(x) = x+a$ and $g(x) = x+2008a$ ensure all the required conditions?
parmenides51
16.11.2022 08:48
I updated the wording, I think it makes more sense now, it is supposed to be a generalisation of IMO 1987 p4 Quote: Prove that there is no function $f$ from the set of non-negative integers into itself such that $f(f(n))=n+1987$ for all $n$.
starchan
17.11.2022 19:27
parmenides51 wrote: Find all $a\in\mathbb{N}$ such that exists a bijective function $g :\mathbb{N} \to \mathbb{N}$ and a function $f:\mathbb{N}\to\mathbb{N}$, such that for all $x\in\mathbb{N}$, $$f(f(f(...f(x)))...)=g(x)+a$$where $f$ appears $2009$ times. (tatari/nightmare)
The first observation is that we want $f$ such that $f^{2009}$ is injective and it's range is precisely the naturals larger than $a$. The injectivity of $f^{2009}$ is equivalent to the injectivity of $f$. The digraph of $f$ over $\mathbb{N}$, because of injectivity is a union of some finite cycles and some infinite chains. Let's say there are $k$ chains $C_i$ and let $C_{ij}$ be the $j$th element of the $i$th chain. The numbers that are not in the image of $f^{2009}$ are precisely the numbers $C_{ij}$ for $1 \leqslant i \leqslant k$ and $1 \leqslant j \leqslant 2009$ (all elements of cycles are images of $f^{2009}$ anyway). Thus $2009k = a$ which forces $2009 \mid a$. The converse direction is to show that for each $a$ that is a multiple of $2009$ such functions exist. For this we set $f(n) = n + \frac{a}{2009}$ and $g(n) = n$ for all $n \in \mathbb{N}$ which is easily seen to work.