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.)
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.
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.
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.
Hay n números.
No puedo sumar un múltiplo de n distinto de este, por lo que los dos de al lado suman n (un impar), entonces n es un impar con un impar al lado (y un par también).
Los pares deben tener dos impares al lado porque deben tener la misma Paridad y no pueden ser ambos pares porque eso forzaría que todos los números sean pares.
Hay un impar más que los pares, entonces solo hay dos impares consecutivos una vez y el resto de los números son pares e impares intercalados uno a uno. Como consecuencia, n es uno de los dos impares consecutivos, este no puede estar al lado de n-2 porque para que la suma de n el del otro lado de n-2, este debería ser n-4, pero no se puede porque habría tres impares consecutivos.
n-2 debe estar entre n-1 y n-3 sí o sí porque debe estar entre dos pares, sumando estos un par (el doble tiene que ser porque no se llega al cuádruple).
n-3 debe estar entre n-2 y otro número que debe ser n-4, así sucesivamente, porque otros más chicos no sirven, y sólo queda uno más grande que podría interrumpir.
Ahora voy a mostrar cuándo puede interrumpir.
n puede estar primero (antes de n-1), en la primera mitad del círculo que se forma ignorando n originalmente, justo en la mitad o en la segunda mitad (último sería lo mismo que primero al ser circular).
Si está primero no interrumpe nada y queda esta lista:
n; n-1; n-2;…; 3; 2; 1
Si está en la primera mitad (de los más grandes), escribo desde n-1 hasta donde interrumpa n (u), luego escribo n. Debo ubicar los números desde 1 hasta u-1.
Llamo i al mayor impar menor a u. El número i debe estar entre un impar y un par para sumar i, que no se puede porque para eso debería ser el otro impar consecutivo al lado de n, pero la suma sería mayor a i porque n>i. Para dar el doble de i debería estar entre u-1 y u-3, lo que me fuerza a descender de 1 en 1, teniendo que llegar al 1 con el último número, implicando que i+1 está después de n, en cuyo caso, i+1+u=2u-1=n, pero en ese caso, si bien se puede, no cumple que está en la primera mitad, está justo en el medio y se cumple siempre porque (n-1)/2+(n+1)/2=n
Último caso, n está en la mitad de los más chicos, lo que no sirve porque los dos números no llegan a sumar n.
En conclusión, sólo hay dos casos:
Ordenados linealmente: 1;2; 3; …; n-1; n
Igual que antes pero con n en el medio exacto del resto de los números, es decir: 1; 2; 3; …; (n-1)/2; n; (n+1)/2; …;n-2; n-1
