Iberoamericana 2014 P6

[Matías V5]

Dado un conjunto $X$ y una función $f:X\to X$, denotamos, para cada $x\in X$, $f^1(x)=f(x)$ y, para cada $j\geq 1$, $f^{j+1}(x)=f\left (f^j(x)\right )$.
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,\ldots ,n\}\to \{1,2,\ldots ,n\}$ es catracha si $f^{f(k)}(k)=k$ para todo $k\in \{1,2,\ldots ,n\}$.
Pruebe que:

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

[Matías V5]

Solución de la parte a):

Spoiler: mostrar

Notemos que la condición que define a una función catracha implica que toda función catracha es sobreyectiva, pues todo [math]k \in \{1,2, \ldots, n\} está en la imagen de la función. Como además el dominio y el codominio de la función tienen [math]n elementos, el hecho de que la función sea sobreyectiva equivale a que sea biyectiva.
Ahora bien, es conocido que dada cualquier función biyectiva [math]f : \{1,2, \ldots, n\} \to \{1,2, \ldots, n\}, es posible particionar el conjunto [math]\{1,2, \ldots, n\} en subconjuntos disjuntos de modo que al aplicar [math]f los elementos de cada uno de estos subconjuntos disjuntos se permutan cíclicamente. Aquí permutar cíclicamente significa que aplicando [math]f repetidas veces se recorren todos los elementos del subconjunto. Por ejemplo, si [math]n=5 y la función [math]f está definida por [math]f(1) = 3, [math]f(2) = 5, [math]f(3) = 4, [math]f(4) = 1 y [math]f(5) = 2, la partición asociada a [math]f sería [math]\left \{ \{1,3,4\} ; \{2,5\} \right \}. A los elementos de esta partición los llamamos ciclos. Los ciclos de un solo elemento corresponden a los puntos fijos de [math]f.
Dado un ciclo de longitud [math]\ell y un elemento [math]x en ese ciclo, se tiene que [math]f^{\ell}(x) = x, y más aún, como [math]\ell es el mínimo entero positivo con esta propiedad, se puede probar que si [math]m es cualquier entero positivo tal que [math]f^m(x) = x, entonces [math]\ell \mid m.
Dicho todo esto, vemos que la condición que debe cumplir una función para ser catracha es equivalente a lo siguiente: para todo [math]k \in \{1,2, \ldots, n\}, si [math]\ell_k es la longitud del ciclo al que pertenece [math]k, entonces [math]\ell_k \mid f(k). Ahora bien, notemos que por definición [math]k y [math]f(k) pertenecen a un mismo ciclo, de modo que [math]\ell_k = \ell_{f(k)}; además, como [math]f es catracha tenemos que [math]\ell_{f(k)} \mid f(f(k)); entonces resulta que [math]\ell_k también divide a [math]f(f(k)). Iterando este argumento conseguimos probar que todos los números que están en el ciclo al que pertenece a [math]k son múltiplos de [math]\ell_k. En particular, [math]\ell_k \mid k.
Vamos a probar ahora que en una función catracha, necesariamente el [math]1 y todos los primos mayores que [math]\sqrt{n} deben ser puntos fijos, de donde se deduce lo que pide probar el problema.
El [math]1 debe ser un punto fijo porque [math]\ell_1 \mid 1 \Rightarrow \ell_1 = 1.
Si [math]p > \sqrt{n} es un primo, la condición [math]\ell_p \mid p implica que [math]\ell_p es [math]1 o [math]p. Supongamos que [math]\ell_p = p. Por lo que vimos antes, todos los números del ciclo al que pertenece [math]p van a tener que ser múltiplos de [math]p. Pero como [math]p > \sqrt{n}, no hay [math]p múltiplos distintos de [math]p en el conjunto [math]\{1,2, \ldots, n\}. Entonces no puede pasar que [math]\ell_p = p, y la única posibilidad que queda es [math]\ell_p = 1, es decir, [math]p es un punto fijo. [math]\blacksquare

[ésta]

Solución del b):

Spoiler: mostrar

Ya vimos que los primos mayores a [math]\sqrt{n} y el [math]1 tienen que ser puntos fijos.

Veamos como podemos definir una [math]f catracha en el resto de los puntos.
Dado un primo [math]p, si tomamos un conjunto de [math]p múltiplos de [math]p: [math]\{a_1, a_2, \ldots , a_p\} y definimos [math]f(a_i)=a_{i+1} para [math]i entre [math]1 y [math]p-1 y [math]f(a_p)=a_1, tenemos para cada [math]a_i que [math]f^p(a_i)=a_i y luego como [math]f(a_i) es múltiplo de [math]p, que [math]f^{f(a_i)}(a_i)=a_i.

Luego si particionamos los enteros entre [math]1 y [math]n, salvo el [math]1 y los primos grandes, en conjuntos disjuntos como estos, podemos definir una [math]f que sea catracha.

Veamos un algoritmo para poder armar estos conjuntos. Iremos recorriendo los primos de mayor a menor (comenzando del primero que no sea un punto fijo).
Dado un primo [math]q>3, podemos agrupar los múltiplos de [math]q que no agrupamos ya antes en conjuntos de [math]q elementos hasta que no podamos más. En este caso nos van a quedar a lo sumo [math]q-1 múltiplos de [math]q sin agrupar.
Además, sabemos que antes de este paso no agrupamos ninguno de los siguientes: [math]q, 2q, 3q, 4q, \ldots, (q+1)q pues ninguno puede tener un divisor primo más grande que [math]q y solo agrupamos hasta ahora multiplos de primos más grandes que [math]q.
Notar que como [math]q no es un punto fijo, [math]q^2\leq n pero podríamos tener [math](q+1)q>n.

Además, podemos elegir cuales son los a lo sumo [math]q-1 múltiplos sin agrupar. Podemos elegir que los que queden sean un subconjunto de [math]\{2q, 3q, 4q, \ldots (q-1)q\} \cup \{(q+1)q\} que son exactamente [math]q-1 elementos.
El único caso en donde no podríamos lograr esto es si justo [math](q+1)q>n. Pero en este caso los únicos múltiplos de [math]q son [math]q, 2q, \ldots, q^2, que los podemos agrupar todos en un sólo grupo y no sobra nada por lo que también lo que sobra es un subconjunto de los [math]q-1 elementos.

Ahora para el caso [math]q=3, hacemos algo lígeramente diferente. Vamos a agrupar los múltiplos de [math]3 que quedan sin agrupar en grupos de [math]3 salvo el [math]6, el [math]12 y el [math]18.
Nos van a sobrar a lo sumo [math]2 múltiplos de [math]3, que podemos lograr que sean un subconjunto de [math]\{24, 36\}.
Notar que todos los que eventualemente pueden sobrar de este paso no los pudimos haber elegido en un paso anterior pues sus únicos divisores primos son [math]3 y [math]2.

Bien, ahora vamos a agrupar todos los pares que faltan. Si la cantidad que faltan agrupar es par, podemos agruparlos de pares y listo. Si es impar, podemos armar un conjunto más de [math]3 que sea el [math]\{6, 12, 18\} y ahora nos queda cantidad par de pares y los podemos agrupar.
De esta manera conseguimos agrupar siempre todos los pares. Además no sobra ningún múltiplo de [math]3, pues los múltiplos de [math]3 que elegimos para que puedan sobrar también son pares.

Supongamos que hay un elemento [math]n\geq m>1 que no quedó en ningún grupo. Sea [math]p_0 su menor divisor primo. Por lo que vimos recién, [math]p_0>3.
Ahora si [math]m=p_0 luego no puede ser [math]p_0^2 \leq n, pues sino en el paso que agrupamos múltiplos de [math]p_0 logramos que no quede el [math]p_0 suelto.
Luego [math]m=p_0*k con [math]k>1, pero como [math]p_0 es el menor primo, [math]k \geq p_0, pues si no k tiene un divisor primo menor a [math]p_0 y también sería divisor de [math]m.
Esto nos dice que [math]n \geq m \geq p_0^2, por lo que en algún momento hicimos un paso con [math]p_0.
Pero el único [math]m que pudo haber sobrado en el paso de [math]p_0, que sea múltiplo de [math]p_0 y [math]m \geq p_0^2 es [math](p_0+1)p_0 y [math]p_0+1 es par, luego el menor primo que divide a [math]m es [math]2, absurdo pues vimos que [math]p_0>3.
Luego si [math]m no fue agrupado en un conjunto entonces [math]m=1 o un primo mayor a [math]\sqrt{n}.

Con esto probamos que los únicos que pueden quedar sueltos son el [math]1 y los primos mayores a [math]\sqrt{n} como queríamos.
Entonces construímos una función catracha con la cantidad de puntos fijos pedida.

[([{&}])]

b)

Spoiler: mostrar

$n=40$ es solución.

[drynshock]

b)

Spoiler: mostrar

$n=40$ es solución.

Lo que te pide el problema es demostrarlo para todos los $n\geq 36$, no solo para uno.