Question

Dado um conjunto contínuo $\mathsf{X},$ e uma função $f: \mathsf{X} \longrightarrow \mathsf{X}~$, denotamos, para cada elemento $x \in \mathsf{X}$, $f^1(x) = f(x)$ e, para cada $j \geqslant 1$, $f^{j + 1}(x) = f(f^j(x))$. Dizemos que $a \in \mathsf{X}$ é um ponto fixo de $f$ se $f(a) = a$. Para cada número real $x$, definimos $\pi x$ como o número de primos positivos menores ou iguais a $x$.

Dado um número inteiro positivo $n$, dizemos que $f: \{1,2, \dots , n \} \longrightarrow \{1,2, \dots , n \}$ é catracha se $f^{f(k)}(k) = k$ para $\text{todo o}~k \in \{1,2, \dots , n \}$.

Prove que se $f$ é catracha, então $f$ tem pelo menos $\pi (n) - \pi \big(\sqrt{n} \big) + 1$ pontos fixos.​

Answer 1

Seja A = {1, ..., n}.  Notamos que se f é catracha então para cada k em A existe algum elemento cuja imagem é k. Assim, f é sobrejetora. Como a cardinalidade do domínio e contradomínio é a mesma, segue que f é bijeção. Assim, f é uma permutação.

Lembramos que toda permutação é uma composição de ciclos (de órbitas disjuntas). Para um número primo p, seja k₁ = f⁻¹(p). Assim temos

$f^{p}(k_1) = k_1$

Assim, o elemento k₁ está num ciclo cuja ordem é um divisor de p. Ou seja, a ordem é p ou 1. Caso a ordem seja p, devem existir $k_2, k_3, \dots, k_p$ distintos tais que  $f^p(k_i) = k_i$ para i = 2,..., p. Isso implica que $f(k_i)$ é múltiplo de p.

Observamos que os múltiplos de p até p² são:

p, 2p, 3p, ..., (p-1)p, p²

Ou seja, um total de p múltiplos. Assim, se p² > n a ordem de k₁ não pode ser p pois não existem p múltiplos de p no conjunto A. Logo, f(k₁) = k₁ e portanto k₁ é um ponto fixo.

Assim, concluímos que para cada número primo p de forma que p² > n existe um ponto fixo para f. Como temos π(n) - π(√n) desses números primos, temos ao menos  π(n) - π(√n)  pontos fixos. Além disso, se k = f⁻¹(1) temos f¹(k) = k. Logo, temos mais um ponto fixo. Portanto, f tem pelo menos  

π(n) - π(√n)  + 1

pontos fixos.