OIM

Dado un conjunto $X$ y una función $f : X \rightarrow X$, denotamos, para cada $x \in X$, $f^1(x) = f(x)$ y, para cada $j \geq 1$, $f^{j+1} = f(f^j(x))$. Decimos que $a \in X$ es un punto fijo de $f$ si $f(a) = a$. Para cada número real $x$, definimos $\pi (x)$ como la cantidad de primos positivos menores o iguales que $x$. Dado un número entero positivo $n$, decimos que $f : \{ 1,2, \cdots , n \} \rightarrow \{ 1,2, \cdots , n \}$ es catracha si $f^{f(k)}(k) = k$ para todo $k \in \{ 1,2, \cdots ,n\}$. Pruebe que:

1. Si $f$ es catracha, entonces $f$ tiene al menos $\pi (n)- \pi (\sqrt{n})+1$ puntos fijos.
2. Si $n \geq 36$, existe una función catracha con exactamente $\pi (n) - \pi (\sqrt{n})+1$ puntos fijos.