ONEM 2018 - Fase 3 - Nivel 3 - P10

[luisq]

Una permutación $a_1,a_2,\ldots ,a_{1000}$ de $1,2,\ldots ,1000$ es llamada buena si cumple la siguiente condición: Si $n$ y $m$ son enteros positivos tales que $n$ es múltiplo de $m$, con $1\leqslant n\leqslant 1000$ y $1\leqslant m\leqslant 1000$, entonces $a_n$ es múltiplo de $a_m$. Determine el menor entero positivo $k$ para el cual existe una permutación buena $b_1,b_2,\ldots ,b_{1000}$ tal que $b_k\neq k$.

Aclaración: Una permutación es una forma de ordenar los elementos de un conjunto. Por ejemplo, $4,2,1,3,5$ es una permutación de $1,2,3,4,5$.

[Fedex]

Spoiler: mostrar

Como $m|n \to a_m | a_n$ tenemos que la cantidad de múltiplos de $a_m$ es suficiente como para cubrir los $a_i$ tal que $i$ es múltiplo de $m$. Luego:
$\lfloor \frac{1000}{m} \rfloor \leq \lfloor \frac{1000}{a_m} \rfloor$
Ahora sea $k$ el mínimo valor entero tal que existe una permutación buena con $a_k≠k$ luego $a_k > k$ pero en ese caso la inecuación anterior se verifica solo si $\lfloor \frac{1000}{k} \rfloor = \lfloor \frac{1000}{a_k} \rfloor$.
$i \leq \frac{1000}{a_k} < \frac{1000}{k} < i+1$
Para algún entero $i$.
$\frac{1000}{i} \geq a_k > k > \frac{1000}{i+1}$
$\frac{1000}{i+1} + 2 \leq \frac{1000}{i}$
$1000i + 2i(i+1) \leq 1000(i+1)$
$i(i+1) \leq 500$
$i \leq 21$
$k > \frac{1000}{i+1} \geq \frac{1000}{22} = 45,...$
$k \geq 46$

Ahora si $k$ no es la potencia de ningún primo podemos factorizar a $n = b.c$ con $b,c$ coprimos $>1$ como:
$a_b = b$ y $a_c=c$
$a_b = b | a_k$ y $a_c=c | a_k$
$bc = k | a_k$ por lo que $a_k \geq 2k$.
Luego remitiéndonos a:
$\frac{1000}{i} \geq a_k > k > \frac{1000}{i+1}$
Tenemos que $k, k+1, ..., a_k$ son al menos $47$ valores enteros.
$\frac{1000}{i+1} + 47 \leq \frac{1000}{i}$
$i(i+1) \leq \frac{1000}{47} = 21,...$
$i \leq 4$
$k > \frac{1000}{i+1} \geq \frac{1000}{5} = 200$

Ahora si queremos encontrar $k<200$ necesariamente es una potencia prima.

Si $k=47$ como $\lfloor \frac{1000}{47} \rfloor > \lfloor \frac{1000}{48} \rfloor$ no funciona.

Si $k = 49$ como $\lfloor \frac{1000}{49} \rfloor > \lfloor \frac{1000}{51} \rfloor$ el único valor posible es $a_{49} = 50$ pero $a_7 = 7| a_{49} = 50$ que no es posible.

Si $k=53$ como $\lfloor \frac{1000}{53} \rfloor > \lfloor \frac{1000}{56} \rfloor$, $a_{53} = 54, 55$ pero como $a_{2m} \equiv 0 \; (2)$ hay al menos $\frac{1000}{2} = 500$ números pares, pero como hay exactamente $500$ pares estos caen todos en los subíndices de esta forma. Además haciendo lo mismo pero $mod \; 5$ vemos que $2$ y $5$ no dividen a $a_{53}$.

Si $k=59$ hacemos esto:
Tomamos la lista $1,2,...,1000$ original y reemplazamos a todos los números de la forma $59x$ por $61x$ que se puede hacer porque $\lfloor \frac{1000}{59} \rfloor = \lfloor \frac{1000}{61} \rfloor = 16$
Como $59.61 > 1000$ hay $3$ casos a considerar.
La condición en índices $n,m$ coprimos con $59$ y $61$ se cumple porque no los tocamos.
Si $m$ es coprimo con $59$ y $61$ pero $n$ no, sea $p$ el primo entre $61$ y $59$ que divide a $n$ y $q$ el otro:
$a_m = m | a_{n=n’p} = n’q \to m |n’$
Que es cierto porque en la lista inicial $m |n=n’p \to m|n’$.
Finalmente si ambos en $m,n$ son divisibles por $59$ o $61$:
$m = pm’ | n=pn’ \to m’|n’ \to m’q | n’q \to a_m | a_n$.

Concluimos que el mínimo $k$ tal que existe una permutación buena con $a_k ≠ k$ es $k=59$.