Question 92
Given a set $X$ and a function $f:X\to X$, write $f^{-1}(x)=f(x)$ for each $x\in X$, and $f^{j+1}(x)=f(f^j(x))$ for each $j\ge1$. A point $a\in X$ is fixed if $f(a)=a$. For real $x$, let $\pi(x)$ be the number of positive primes at most $x$. For a positive integer $n$, call $f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$ catracha if $f^{f^k}(k)=k$ for every $k\in\{1,2,\ldots,n\}$. Prove:
a) If $f$ is catracha, it has at least $\pi(n)-\pi(\sqrt n)+1$ fixed points.
b) If $n\ge36$, there is a catracha function with exactly $\pi(n)-\pi(\sqrt n)+1$ fixed points.
a) If $f$ is catracha, it has at least $\pi(n)-\pi(\sqrt n)+1$ fixed points.
b) If $n\ge36$, there is a catracha function with exactly $\pi(n)-\pi(\sqrt n)+1$ fixed points.