Q6 Matemática  (IberoAmerican 2014)

Dado um conjunto $X$ e uma função $f:X\to X$, para cada $x\in X$ definimos $f^1(x)=f(x)$ e, para cada $j\ge 1$, $f^{j+1}(x)=f(f^j(x))$. Dizemos que $a\in X$ é um ponto fixo de $f$ se $f(a)=a$. Para cada $x\in \mathbb{R}$, seja $\pi (x)$ a quantidade de primos positivos menor ou igual a $x$. Dado um inteiro positivo $n$, dizemos que $f:\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$ é catracha se $f^{f(k)}(k)=k$, para cada $k=1,2,\dots n$. Prove que: (a) Se $f$ é catracha, $f$ tem pelo menos $\pi (n)-\pi (\sqrt{n})+1$ pontos fixos. (b) Se $n\ge 36$, existe uma função catracha $f$ com exatamente $\pi (n)-\pi (\sqrt{n})+1$ pontos fixos.