Nacional 2023 N2 P6

Problemas que aparecen en el Archivo de Enunciados.
Felibauk

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 OFO - Medalla de Oro-OFO 2023
FOFO 13 años - Medalla-FOFO 13 años OFO - Oro perfecto-OFO 2024 FOFO Pascua 2024 - Jurado-FOFO Pascua 2024
Mensajes: 73
Registrado: Dom 19 Ene, 2020 12:43 am
Medallas: 13
Nivel: 1

Nacional 2023 N2 P6

Mensaje sin leer por 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$.)
"La matemática es para pensar. El fútbol es para sacar mi instinto animal y decirle al árbitro hdp te voy a m4t4r." Anónimo
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Nacional 2023 N2 P6

Mensaje sin leer por 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.
This homie really did 1 at P6 and dipped.
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Nacional 2023 N2 P6

Mensaje sin leer por 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).
Responder