Selectivo IMO 2022 P5

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 1898
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Selectivo IMO 2022 P5

Mensaje sin leer por Gianni De Rico »

Sea $n>10$ un número entero impar. Determinar de cuántas formas se pueden distribuir los números enteros de $1$ a $n$ inclusive alrededor de una circunferencia de manera que cada número sea divisor de la suma de su dos números vecinos, el de su derecha y el de su izquierda. (Dos formas simétricas respecto de un diámetro, se consideran iguales; dos formas que se obtienen una de rotar la otra, se consideran iguales.)
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Avatar de Usuario
ésta

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2017 OFO - Jurado-OFO 2018
Mensajes: 298
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Re: Selectivo IMO 2022 P5

Mensaje sin leer por ésta »

Spoiler: mostrar
Paso 1: En un ordenamiento válido no hay dos números pares consecutivos.
Demo: Si tenemos $a,b,c$ consecutivos con $b$ par, $b\mid a+c\Rightarrow 2\mid a+c$ por lo que $a$ y $c$ tienen la misma paridad. Por lo que si $b$ es adyacente a un par, sus dos vecinos son pares. Esto implica que si hay dos pares adyacentes, todos los números son pares, pues si no tendríamos que el conjunto maximal de números pares consecutivos que contiene a estos dos tiene un extremo, y este extremo es adyacente a exactamente un número par. Como no todos los números que hay que ordenar son pares, se sigue que esta situación es imposible.
Esto implica que en la paridad de los números de la circunferencia tiene la forma $IIPIPIPIP...IP$, es decir, hay dos impares consecutivos y luego se alternan pares e impares.

Paso 2: En un ordenamiento válido el número $n$ es adyacente a un impar.
Demo: Sean $a$ y $b$ los adyacentes a $n$. Tenemos que $n\mid a+b<n+n=2n$ por lo que $n=a+b$ y como $n$ es impar, debemos tener o bien $a$ impar o $b$ impar.

Paso 3: En un ordenamiento válido el número $n-2$ es adyacente a $n-1$ y $n-3$.
Demo: Por la distribución de pares e impares y el paso anterior tenemos que o bien $n-2$ es adyacente a $n$ o bien $n-2$ es adyacente a dos pares.
Si $n-2$ es adyacente a $n$ y $a$ es el otro adyacente (que debe ser par), $n-2\mid n+a$ con $n-2<n+a<2n<3(n-2)$ (la última desigualdad vale porque $n>6$). Por lo que debemos tener $2(n-2)=n+a$, pero $n+a$ es impar, absurdo.
Si $n-2$ es adyacente a dos pares $a$ y $b$, tenemos $n-2\mid a+b$ con $a+b$ par y $a+b<3(n-2)$ (por lo mismo que antes). Luego debemos tener $2(n-2)=a+b$ y luego alguno de los dos es mayor a $n-2$. Pero el único número par mayor a $n-2$ es $n-1$ por lo que $a$ y $b$ deben ser $n-1$ y $n-3$ en algún orden.

Paso 4: En un ordenamiento válido, si $m$ es adyacente a $m+1$ y a $a$, con $a<m$, entonces $a=m-1$.
Demo: Tenemos $m\mid a+m+1$ con $m<a+m+1\leq 2m$. Por lo que debemos tener $2m=a+m+1$ y despejando sale $a=m-1$.

De ahora en más sea $n=2k+1$
Paso 5: En un ordenamiento válido los números de $k+1$ a $n-1$ aparecen de forma consecutiva en orden.
Demo: Probemos por inducción de $m$ a $m-1$ que los números de $m$ a $n-1$ aparecen de forma consecutiva en orden si $m\geq k+1$. En el paso anterior lo vimos para $m=n-3$. Supongamos que vale para $m>k+1$, el número $m$ es adyacente a $m+1$, Como $m$ no puede ser adyacente a ningún número entre $m+2$ o $n-1$, o bien el otro adyacente es $n$ o bien es menor a $m$.
Si los adyacentes son $n$ y $m+1$, tenemos $m\mid n+m+1 $ con $2m<n+m+1=2k+1+m+1<3m$, absurdo.
Si el otro adyacente es $a$ con $a<m$ por el paso anterior, tenemos que $a=m-1$. Por lo que probamos que la hipótesis vale para $m-1$, luego vale para $k+1$.

Por el mismo argumento que antes, tenemos que $k+1$ es adyacente o bien a $n$, o bien a $k$ (además de $k+2$).

Paso 6: En un ordenamiento válido, si $k+1$ es adyacente a $k$, los números de $1$ a $n$ aparecen de forma consecutiva en orden.
Demo: Probaremos de nuevo por inducción de $m$ a $m-1$ que los números de $m$ a $n-1$ aparecen de forma consecutiva en orden si $m\geq 1$. Por hipótesis y el paso anterior, lo tenemos para $k$. Supongamos que vale para $2\leq m\leq k$ y probemos que vale para $m-1$:
Por el mismo argumento que el paso anterior, o bien $m$ es adyacente a $n$ o a $m-1$. Si pasa lo segundo estamos, así que solo tenemos que probar que no es adyacente a $n$. Pero si $m$ es adyacente a $n$ y $a$ es el otro adyacente a $n$. Tenemos que $n\mid m+a<2n$. Por lo que $n=m+a\Rightarrow a=n-m$. Pero $n-2\leq n-m\leq k+1$ (pues $2\leq m\leq k$), y por lo tanto $a$ está en la cadena de consecutivos de $k$ a $n-1$ (y no es ninguna de los extremos). Esto implica que $a$ tiene que ser adyacente a $a-1$ y $a+1$, donde ninguno es $n$, absurdo.

Paso 7: En un ordenamiento válido, si $k+1$ es adyacente a $n$, los números de $1$ a $k$ aparecen de forma consecutiva en orden y $k$ es adyacente a $n$.
Demo: Sea $a$ el otro adyacente a $n$ distinto de $k+1$, como números mayores a $k+1$ aparecen en la cadena de consecutivos de $k+1$ a $n-1$, tenemos que $a\leq k$. Y como $n\mid a+k+1\leq 2k+1=n$, debemos tener $a=k$. Sea $b$ el otro consecutivo a $k$ distinto de $n$. Tenemos por el mismo argumento que antes que $b\leq k-1$. Por lo que $k\mid n+b$, en donde $2k<n+b=2k+1+b\leq 3k$. Por lo que debemos tener $n+b=3k$, y despejando sale $b=k-1$.
Ahora podemos hacer la misma inducción de siempre, probaremos que los números de $m$ a $k$ aparecen de forma consecutiva, luego $n$ y luego los números de $k+1$ a $n-1$ si $1\leq m\leq k-1$. Sabemos que vale para $m=k-1$, probaremos que si vale para $m>2$, vale para $m-1$. Pero el otro número adyacente a $m$ tiene que ser menor a $m$ pues ya usamos todos los mayores, y por el paso 4 como $m$ es adyacente a $m+1$ debemos tener que el otro es $m-1$, lo que completa el paso inductivo.

Combinando los pasos 6 y 7 sigue que solo hay dos distribuciones posibles:
$1,2,3,\ldots ,n$ y $1,2,3,\ldots ,k,n,k+1,k+2,k+3,\ldots ,n-1$.
Es fácil verificar que ambas funcionan.
1  
Imagen

tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 2017
FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 622
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

Re: Selectivo IMO 2022 P5

Mensaje sin leer por tuvie »

Primero un comentario.
Spoiler: mostrar
Algo que me parece interesante de la solución, y que uno en principio no intentaría hacer, es resolver el problema no solo para los impares si no que también para los pares. Parecería que uno resuelve un problema más díficil, pero en realidad, es una ayuda para poder resolver lo que nos están pidiendo. Esto suele ser una idea común en problemas con inducción, en donde es necesario hacer mas fuerte la hipótesis para que cierre.
Ahora sí pasemos a la solución.
Spoiler: mostrar
Vamos a demostrar que para todo $n \geq 5$, si $n$ es par hay una sola solución dada por $1, 2, 3, \ldots, n-1, n$ y si $n$ es impar hay dos, dadas por $1, 2, 3, \ldots, n-1, n$ y por $1, 2, 3, \ldots, \frac{n-1}{2}, n, \frac{n+1}{2},\ldots, n-1$.

Primero demostremos dos Lemas que son la clave de la solución.

Lema 1: Si tenemos una configuración en donde ubicamos los números del $1$ al $n$ satisfactoriamente, entonces los vecinos de $n$ suman $n$.

Demostración: Sean $a$ y $b$ los vecinos de $n$. Entonces, como $n$ es el número más grande, $a$ y $b$ son menores a $n$ y por lo tanto $a+b < n+n = 2n$. Luego $a+b$ es un múltiplo de $n$ mayor a $0$ y menor a $2n$, por lo que debe ser $n$.

Lema 2: Si tenemos una configuración en donde ubicamos los números del $1$ al $n$ satisfactoriamente, entonces quitando a $n$ obtenemos una configuración en la cual tenemos ubicados los números del $1$ al $n-1$ y cumplen las condiciones del enunciado, cada número divide a la suma de los vecinos.

Demostración: Sean $a,b,n,c,d$ las ubicaciones de los números alrededor de $n$. Notar que como $n \geq 5$, son todos distintos. Por el Lema 1, $b+c=n$. Si buscamos que $a,b,c,d$ sigan satisfaciendo las hipótesis luego de quitar a $n$, buscamos entonces que $b \mid a+c$ y que $c \mid b+d$. Notar que como $a,b,n,c,d$ satisfacen las hipótesis, entonces en particular $b \mid a+n$. Como $n=b+c$, entonces $b \mid a+b+c$ y por lo tanto $b\mid a+c$, Análogamente $c\mid b+d$. Entonces concluimos que al quitar $n$ de una configuración válida pra los números del $1$ al $n$, obtenemos una configuración válida para los números del $1$ al $n-1$,

Corolario: Para obtener una configuración válida para los números del $1$ al $n$, debemos agregar a $n$ a una configuración válida de los números del $1$ al $n-1$, entre dos numeros adyacente que sumen $n$.

Un ejemplo del corolario sería el siguiente. Tomemos $1,2,3,4,5,6$ al $7$ lo podemos agregar entre dos vecinos que sumen 7 únicamente, que son $3,4$ y $6,1$.

Ahora sí, veamos la inducción.

Vamos a demostrar lo que ya dijimos, que para todo $n \geq 5$, si $n$ es par hay una sola solución dada por $1, 2, 3, \ldots, n-1, n$ y si $n$ es impar hay dos, dadas por $1, 2, 3, \ldots, n-1, n$ y por $1, 2, 3, \ldots, \frac{n-1}{2}, n, \frac{n+1}{2},\ldots, n-1$.

Para $n=5$ basta con cubrir todos los casos posibles, pero es fácil notar que las únicas dos maneras son $1,2,3,4,5$ y $1,2,5,3,4$.

Supongamos que para $n=k$ se cumple la hipótesis inductiva, y veamoslo para $n=k+1$. Debemos separar en dos casos según si $k$ es par o impar.

Caso par: Como por hipótesis inductiva la única valida es $1,2,3,\ldots,k$, ahora a $k+1$ debemos ubicarlos entre dos cuya suma sea $k+1$. Esto solo ocurre entre $k$ y $1$ y entre $\frac{ḱ}{2}$ y $\frac{k+2}{2}$. Luego, las únicas dos maneras son $1,2,3\ldots,k,k+1$ y $1,2,3,\ldots,\frac{k}{2},k+1,\frac{k+2}{2},\ldots,k$, cumpliendo con lo requerido para $n=k+1$.

Caso impar: Como por hipótesis inductiva las únicas validas son $1,2,3,\ldots,k$, y $1,2,3,\ldots,\frac{k-1}{2},k,\frac{k+1}{2},\ldots,k-1$, ahora a $k+1$ debemos ubicarlos entre dos cuya suma sea $k+1$. Esto solo ocurre entre $k$ y $1$ en la primera configuracion, y en la segunda no ocurre. Luego, la única manera es $1,2,3\ldots,k,k+1$, cumpliendo con lo requerido para $n=k+1$.

Por lo tanto, hemos completado el paso inductivo y concluimos que las únicas dos maneras son las descriptas anteriormente si $n$ es impar, que son $1,2,3,\ldots,n-1,n$ y $1,2,3,\ldots,\frac{n-1}{2}, n, \frac{n+1}{2},\ldots,n+1$, y estamos.
1  

Responder