Nacional 2023 N2 P6

[Felibauk]

Se tiene una fila de $n$ sillas, numeradas ordenadamente de izquierda a derecha de $1$ a $n$. Además, en los respaldos de las sillas se distribuyen los $n$ números de $1$ a $n$, uno en cada silla, de modo que en ningún caso coincida el número de la silla con el número de su respaldo. Hay un niño sentado en cada silla. Cada vez que la profesora aplaude, cada niño se fija cuál es el número del respaldo de la silla en la que está sentado y se sienta en la silla numerada con ese número. Demostrar que, para todo $m$ que no sea una potencia de un primo, con $1<m \leq n$, es posible distribuir los números de los respaldos de manera tal que después de que la profesora haya aplaudido $m$ veces, por primera vez estén todos los niños sentados en las sillas donde se encontraban sentados al inicio del juego.
(Durante el proceso, puede ocurrir que los niños regresen a sus sillas originales, pero no lo hacen todos al mismo tiempo hasta la señal número $m$.)

[Fedex]

Spoiler: mostrar

Supongamos que de una silla $i$-esima con respaldo $j \neq i$ sale una flecha hacia la silla $j$-esima. Si fijamos una silla y nos movemos a la silla a la que apunta su flecha y de allí a la que apunta la flecha de esta y así sucesivamente, es claro que en algún punto del recorrido volveremos a una silla que ya había sido visitada, mas aun esta deberá ser la silla desde la que partimos ya que de lo contrario tendríamos dos flechas incidentes en una misma silla intermedia del recorrido (pero esto no puede ser ya que todos los respaldos son distintos). Luego de las $n$ sillas podemos extraer un grupo de ellas que se apuntan entre si formando un ciclo. Repitiendo esto con las sillas restantes podemos extraer mas ciclos y descomponer al grupo de sillas en varios ciclos de tamaños $c_1$, $c_2$, $\cdots$, $c_k$ todos ellos disjuntos y con $c_i \geq 2$ para todo $1 \leq i \leq k$ (ya que ninguna silla se apunta a si misma). Notar que sobre un ciclo de tamaño $c_i$, la posición de los alumnos se restablece tras $m$ pasos sii $c_i | m$. De esto se sigue que el $m$ mínimo que restablece la posición de todos los alumnos es $m = mcm(c_1, c_2, \cdots, c_k)$.
Luego el problema equivale a mostrar que para todo $m$ no potencia de un primo con $1 \leq m \leq n$ existen números $c_1$, $c_2$, $\cdots$, $c_k$ todos mayores o iguales a $2$ con $m = mcm(c_1, c_2, \cdots, c_k)$ y $c_1 + c_2 + \cdots + c_k = n$.
Probaremos esto por inducción fuerte en $n$ donde el caso base es trivial. Para el paso inductivo separamos en dos casos:

• $m$ es producto de al menos $3$ primos distintos: Sea $m = ab$ donde $a$ es la potencia de un primo coprimo con $b$ y $b$ no es potencia de un primo (si $m = p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}$ entonces $a = p_1^{e_1}$ y $b = p_2^{e_2} \cdots p_k^{e_k}$ por ejemplo) sea $c_1 = a$ ahora como $1 \leq ab \leq n$ entonces $1 \leq b \leq \frac{n}{a} \leq n -a $ (esta ultima desigualdad se obtiene de que $2 \leq a$ y como $2a \leq ab \leq n$ juntandolas $2 \leq a \leq \frac{n}{2}$ y por lo tanto $a + \frac{n}{a} \leq \frac{n}{2} + \frac{n}{2} = n$). Luego como $b$ no es la potencia de un primo, por hipotesis inductiva existen $b_1$, $\cdots$, $b_k$ tales que su $mcm$ es $b$ y su suma es $n-a$. Luego $c_1$, $b_1$, $\cdots$, $b_k$ son tales que su $mcm$ es $ab$ (ya que $a$ y $b$ son coprimos) y su suma es $n$.

• $m$ tiene $2$ primos distintos en su factorizacion: Sea $m = ab$ donde $a$ y $b$ son potencias de primos coprimos entre si (si $m = p_1^{e_1}p_2^{e_2}$ entonces $a = p_1^{e_1}$ y $b = p_2^{e_2}$). Supongamos primero que $a$ es coprimo con $n$, vamos a tomar solo ciclos de tamaños $ab$, $a$ y $b$, sean $x$, $y$ y $z$ las cantidades de estos, luego queremos que se verifique $abx + ay + bz = n$, tomando modulo $a$ resulta $z \equiv \frac{n}{b} \equiv r \; (a)$ con $0 < r < a$ (mayor a $0$ estricto porque $a$ es coprimo con $n$) luego $br < ba \leq n$ por lo que tomando $z = r$ tenemos que $bx + y = \frac{n-br}{a} >0$ y entero. Que escribiéndolo con el algoritmo de la división con $b$ como divisor salen $x$ e $y$ alguno de los dos no nulo y como $z$ también lo es resulta que su $mcm$ es $ab$. Si $a = p^k$ no es coprimo con $n$ entonces $n - ab \geq 0$ es divisible por $p$, por lo que tomando suficientes ciclos de tamaño $p$ resulta $ab + p + p + \cdots + p = n$ como queremos y con $mcm$ igual a $ab$.

Se sigue entonces que esto se verifica para todo $n$ como queríamos probar.

[usuario250]

Pista

Spoiler: mostrar

Al no ser m potencia de primo y ser m > 1, m se puede escribir como m = c * d, con c y d coprimos y c y d mayores a 1.

Si m=n, se puede hacer con un solo ciclo de tamaño m.
Si m<n, (ejercicio para el lector), demostrar que se puede escribir n como x * c + y * d con x,y enteros positivos. Luego se arman x ciclos de tamaño c e y ciclos de tamaño d.
Pista para este ejercicio

Spoiler: mostrar

ver que los restos de c, ..., (d-1)*c, d*c en la división por d son 0, 1, ..., (d-1) en algún orden (c y d son coprimos).
entonces lo que se hace es tomar x entre 1 y d tal que x*c tenga el mismo resto que n en la división por d y queda que (n - x*c) es múltiplo de d y positivo (x*c <= d*c = m < n).