OFO 2022 Problema 13

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
joa.fernandez

FOFO 8 años - Mención Especial-FOFO 8 años OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020
FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023
Mensajes: 84
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 11
Nivel: Exolímpico

OFO 2022 Problema 13

Mensaje sin leer por joa.fernandez »

Sea $\tau (n)$ la cantidad de divisores positivos de $n$. Hallar todas las sucesiones crecientes $a_1,a_2,\ldots$ de números naturales tales que $\tau (i+j)=\tau (a_i+a_j)$ para todos $i,j\in \mathbb{N}$.

Aclaración: Una sucesión es creciente si para $i\leq j$ se tiene que $a_i\leq a_j$.
Rotohomotecias como estilo de vida
Avatar de Usuario
joa.fernandez

FOFO 8 años - Mención Especial-FOFO 8 años OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020
FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023
Mensajes: 84
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 11
Nivel: Exolímpico

Re: OFO 2022 Problema 13

Mensaje sin leer por joa.fernandez »

Aquí publicaremos la solución oficial.
Rotohomotecias como estilo de vida
juandodyk

OFO - Medalla de Oro-OFO 2022 OFO - Medalla de Oro-OFO 2023 OFO - Mención-OFO 2024
Mensajes: 42
Registrado: Mar 26 Jun, 2018 1:59 am
Medallas: 3
Nivel: Exolímpico

Re: OFO 2022 Problema 13

Mensaje sin leer por juandodyk »

Spoiler: mostrar
Voy a probar que la unica sucesion es $a_n=n$ para todo $n$ (Prop 5).

Prop 0. Para todo $n$, si $\tau(n)=q$ primo entonces $n=p^{q-1}$ con $p$ primo.

Prueba. Obvio usando la formula $\tau(n) = \prod_{p\mid n} (a_p+1)$ donde $n = \prod_{p\mid n} p^{a_p}$ es la factorizacion en primos de $n$.

Prop 1. $a_1=1$ y $a_2=2$.

Prueba. Para ver $a_1=1$, $2=\tau(2)=\tau(1+1)=\tau(a_1+a_1)=\tau(2a_1)$, luego por la Prop anterior $2a_1=p$ con $p$ primo, $p=2$ y $a_1=1$.

Para ver $a_2=2$, $3=\tau(4)=\tau(2a_2)$, luego $2a_2=p^2$ con $p$ primo, $p=2$ y $a_2=2$.

Prop 2. Para todo $n$, $a_n$ es par sii $n$ es par.

Prueba. Por induccion. Los casos $n=1,2$ salen por la Prop anterior.

Supongamos que la proposicion vale para todo $n'<n$, y $n>2$. Sea $p$ primo tal que $n<p<2n$, que existe por el teorema de Chebyshev. Tenemos $\tau(a_n + a_{p-n}) = \tau(n + p-n) = \tau(p) = 2$, luego $a_n + a_{p-n}$ es primo. Tenemos $a_n + a_{p-n} \geq a_2 + a_1 = 3$ (Prop 1) y es primo, luego es impar. Como $n<p<2n$, $1\leq p-n<n$, luego aplicamos la hipotesis inductiva sobre $p-n$ y obtenemos que $a_{p-n}$ y $p-n$ tienen la misma paridad. Ademas $p>n>2$, luego $p$ es impar. Tenemos pues $1\equiv a_n + a_{p-n} \equiv a_n + p-n \equiv a_n + 1-n \mod 2$, luego $a_n \equiv n \mod 2$, como queriamos.

Prop 3. Para todo $n$, $a_n<a_{n+1}$.

Prueba. Tenemos que $a_{n+1}\geq a_n$ por hipotesis. $a_{n+1}$ y $a_n$ tienen distinta paridad por lo anterior, luego no pueden ser iguales y $a_{n+1}>a_n$.

Prop 4. Para todo primo $p>2$, $a_{2^{p-2}} = 2^{p-2}$.

Prueba. Sea $n=2a_{2^{p-2}}$. Tenemos que $\tau(n) = \tau(2a_{2^{p-2}}) = \tau(a_{2^{p-2}} + a_{2^{p-2}}) = \tau(2^{p-2} + 2^{p-2}) = \tau(2^{p-1}) = p$. Por la Prop 0, $n$ debe ser $q^{p-1}$ con $q$ primo. Ahora $n$ es par, luego $n=2^{p-1}$ y $a_{2^{p-2}} = 2^{p-2}$.

Prop 5. Para todo $n$, $a_n=n$.

Prueba. Sea $n$ entero positivo. Sea $p$ primo tal que $2^{p-2} \geq n$ (existe porque hay infinitos primos) y sea $m=2^{p-2}$. Como $(a_n)_n$ es estrictamente creciente (Prop 3) y $a_1=1$ (Prop 1), tenemos $a_m > a_{m-1} > \ldots > a_1 = 1$ y $a_m \geq m$, con igualdad sii $a_k = a_{k-1}+1$ para todo $2\leq k\leq m$. Ahora por la Prop 4 hay igualdad, luego $a_k = a_{k-1}+1$ para todo $2\leq k\leq m$, luego $a_k=k$ para todo $k\leq m$, y en particular $a_n=n$, como queriamos.
1  
sebach

Colaborador-Varias OFO - Medalla de Bronce-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Medalla de Bronce-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 202
Registrado: Dom 06 Mar, 2011 11:49 am
Medallas: 8
Nivel: Exolímpico

Re: OFO 2022 Problema 13

Mensaje sin leer por sebach »

No recomiendo leer esta solución con mucho detalle sobre todo por lo larga y densa que es, y porque no estoy 100% seguro de haber justificado bien ni todo lo necesario. Pero bueno, pueden chusmearla y ver si encuentran algún error o si se les ocurre en el medio alguna manera más corta de hacer lo que estoy haciendo yo :)

La subo también porque salió de "arremangarse y ver muchas cosas a mano", sin ninguna idea muy "mágica" que mate al problema de una. Bah, hay una idea que para mí es medio mágica (obvio que esta valoración es subjetiva), pero que se me ocurrió después de mirar y pensar muchas cosas antes en este mismo problema, como que para mí tuvo un hilo conductor el hecho de llegar hasta ahí.

Mi solución:
Spoiler: mostrar
Primero notemos que un número $n$ es primo si y sólo si $\tau(n)$ es igual a $2$.
Otra observación importante es que un número $c$ es un cuadrado perfecto si y sólo si $\tau(c)$ es impar. Esto es porque cada divisor $d$ tiene su “pareja” $c/d$, y que la cantidad de divisores sea impar es que la pareja de uno de los divisores sea sí misma, es decir $d = c/d \Rightarrow c = d^2$, por lo que $c$ queda cuadrado perfecto.

Otra observación es que no puede haber dos números consecutivos iguales. Supongo que hay dos valores $x$ en la secuencia, en las posiciones $k$ y $k+1$. Luego, dado un primo $p > k+10$ (que existe porque hay infinitos), se tiene que $a_k + a_{p-k}$ debe ser primo. Ahora, si este número es primo, también lo será $a_{k+1}+a_{p-k}$, por lo que la suma de los índices deberá ser primo. Pero entonces necesito que $p+1$ también sea primo, y como $p>10$ es impar esto es imposible.

Entonces la sucesión será estrictamente creciente.

Tomando $i=1, j=1$, queda que $2a_1$ debe ser primo dado que $1+1$ es primo. Luego, como el único número primo par es $2$, debe ocurrir que $a_1=1$.

Tomando $i=1, j=3$, como $\tau(1+3)=3$, $a_1 + a_3$ debe ser un cuadrado perfecto. De hecho, el único divisor además de $1$ y sí mismo debe ser su raíz cuadrada. Luego $a_1 + a_3 = p_3^2 \Rightarrow a_3 = p_3^2-1$ con $p_3$ un número primo.
Esto además nos dice que $a_3 \geq 3$, dado que $p_3 \geq 2$.

Tomando $i=1, j=4$, $a_1+a_4$ debe ser primo. Luego $a_4 = p_4 - 1$, por lo que, como $a_3 \geq 3$ y la sucesión es no decreciente, $p_4$ debe ser un primo impar, siendo $a_4$ un valor par necesariamente.

Tomando $i=3, j=4$, $a_3 + a_4$ debe ser primo. Como esta suma además es mayor a $2$, debe ser impar. Y como sabemos que $a_4$ es par, obtenemos que $a_3$ debe ser impar.
Ahora, como $a_3 = p_3^2 - 1$, el primo $p_3$ debe ser par para que luego al restarle uno a su cuadrado el resultado sea impar. Obtenemos entonces que $a_3 = 2^2-1=3$ necesariamente.

Tomando ahora $i=2, j=3$, $a_2+a_3$ debe ser primo. Como esa suma va a ser impar, y $a_3=3$, tenemos que $a_2=2$ necesariamente.

TENEMOS HASTA ACA que la sucesión empieza con los valores $1, 2, 3$.

Tomando $i=1, j=6$, $a_1+a_6 = a_6+1$ debe ser primo, por lo que $a_6$ debe ser par. Lo mismo ocurre tomando $i=1, j=10$, $a_{10}+1$ debe ser primo y $a_{10}$ debe ser par.

Ahora, tomando $i=6, j=10$, se tiene que $\tau(a_6+a_{10}) = 5$.
Pensemos en esto, un número $S$ con $5$ divisores. Sean sus divisores, ordenados de menor a mayor, ${1, d_1, d_2, d_3, S}$. Luego $d_1*d_3 = d_2^2 = S$. Además, $d_2$ debe tener un único primo en su factorización en primos, dado que si no habría al menos dos divisores antes. Entonces $d_2=p^\alpha$, por lo que $S = d_2^{2*\alpha}$. Y si su cantidad de divisores es $5$, $S$ debe ser un primo elevado a la cuatro, por lo que $d_2$ debe ser un primo elevado al cuadrado. (También podíamos recurrir a la fórmula de $\tau$ con productos de exponentes $+1$.)
Todo este razonamiento nos lleva a ver que $a_6+a_{10}$ debe ser un primo elevado a la potencia cuarta. Además, como es una suma de dos números pares, lo único que queda es que $a_6+a_{10}=2^4=16$, por lo que los primos $a_6+1$ y $a_{10}+1$ deben sumar $18$. Las únicas dos posibilidades son que los primos sean $(5, 13)$ o $(7, 11)$.

Primer caso, los primos son $(5, 13)$:
Si $a_6+1 = 5$, queda que $a_6 = 4$.

Como $a_3=3$, los valores $a_4$ y $a_5$ deben ser $3$ ó $4$.
Como sabíamos que $a_4$ era par, debe ser $a_4=4, a_5=4$, pero entonces tomando $i=1, j=5$ no se cumple el enunciado dado que $1+5$ no es primo y $a_1+a_4=5$ sí.
Absurdo.

Finalmente, obtuvimos que $a_6=6$ y $a_{10}=10$.

Como $a_4$ es par y debe ser mayor a $3$ y menor o igual a $6$, debe ser $4$ ó $6$. Pero si fuera $6$, tomando $i=3, j=4$ tenemos que $a_3+a_4$ debería ser primo, llegando a un absurdo pues $9$ no es primo.
Entonces $a_4=4$.

Ahora, $a_5$ debe ser $4, 5 ó 6$. Pero tomar $i=1, j=5$ nos dice que $a_1+a_5$ no puede ser primo, por lo que la única posibilidad es que $a_5=5$.

Hasta acá, usando las restricciones del problema, llegamos a que los primeros $6$ valores de la sucesión son $1, 2, 3, 4, 5, 6$ y además $a_{10}=10$.

Tomando $i=2, j=7$ sale que $2+a_7$ debe ser un primo elevado al cuadrado, y como $6 \leq a_7 \leq 10$, sale que $2+a_7=9 \Rightarrow a_7=7$.
Lo mismo tomando $i=1, j=8$, se ve que $a_8=8$.

Ahora $a_9$ debe ser $8, 9 ó 10$, pero tomando $i=4, j=9$ sale que $4+a_9$ debe ser primo por lo que $a_9=9$.

Tomando $i=2, j=11$, $a_{11}+2$ es primo y $a_{11}$ debe ser impar.
Tomando $i=5, j=11$, $a_{11}+5$ debe tener $5$ divisores, e igual que antes sale que es un primo elevado a la $4$. Como la suma es par, debe ser $16$, por lo que $a_{11}=11$.

Tomando $i=1, j=12$, $a_{12}+1$ es primo y $a_{12}$ debe ser par.
Tomando $i=4, j=12$, $a_{12}+4$ debe tener $5$ divisores, e igual que antes sale que es un primo elevado a la $4$. Como la suma es par, debe ser $16$, por lo que $a_{12}=12$.


Bien, los primeros $12$ números de la sucesión deben ser necesariamente los primeros $12$ números naturales.

Bueno, me voy a adelantar un poco. Va la idea un poco mágica, que se me ocurrió de los casitos anteriores y pensar en los cuadrados perfectos:
Supongamos que quiero ver qué pasa con el valor en la posición $p$, y $p+k=c^2$ es el cuadrado perfecto más cercano a $p$ (distinto de $p$), y $p+m=(c+1)^2=c^2+2c+1$ es el siguiente cuadrado perfecto. Supongamos además que $a_k = k, a_m = m$.
Entonces, tomando $i=p, j=k$ y luego $i=p, j=m$ tengo que $a_p+k$ y $a_p+m$ deben ser cuadrados perfectos.
Además, la diferencia entre estos cuadrados perfectos será igual a $m-k$ que, manipulando las igualdades de antes, es igual a $2c+1$.
Teniendo como hipótesis, además, que $a_{p-1} \geq p-1$, ocurre que $a_p \geq p$ necesariamente.
Ahora, si entre los siguientes dos cuadrados perfectos la diferencia es $2c+1$, la diferencia entre otros dos cuadrados perfectos distintos, ambos mayores o iguales que $p$, será mayor. Esto es porque $A < B \Rightarrow (A+1)^2-A^2=2A+1 < 2B+1=(B+1)^2-B^2$, y entonces entre dos cuadrados perfectos consecutivos la diferencia será mayor. Si no son consecutivos será incluso más grande porque en el medio tendremos el consecutivo anterior del mayor, que se distancia del mayor en más de $2c+1$ por lo que vimos antes.

Entonces, resumiendo este último razonamiento, si $a_p \geq p$, y tenemos que $a_k=k, a_m=m$, obtenemos que los únicos cuadrados perfectos que pueden ser $a_p+a_k$ y $a_p+a_m$, cuya distancia sea $m-k$, son $c^2$ y $(c+1)^2$.
Pero entonces esto determina que $a_p = c^2-k = p$ !!

Entonces, si tengo suficientes valores iniciales que necesitan ser iguales a sus índices, usando este razonamiento, podré ver que se debe cumplir eso para toda la sucesión necesariamente.

Todavía no estoy en ese paso, pero voy a usar ese razonamiento para hacer encontrar más fácilmente algunos valores.

Podemos usar esto de arriba para $a_{13}$, con $k=3, m=12$. Se cumplen las hipótesis que dijimos. Tenemos que $a_{13} \geq 13, a_3=3, a_{12}=12$.
Luego, los únicos dos cuadrados perfectos cuya diferencia es $9$ son $16$ y $25$, por lo que $a_{13}=13$.
Lo mismo para $a_{14}$ y $a_{15}$.

Ahora, para $a_{16}$ esto no ocurre, ya que $k=9$ pero $m=20$, y aún no tengo información sobre $a_{20}$.

Volvemos a los métodos anteriores.
Tomamos $i=1, j=16$, sale que $a_{16}$ debe ser par. Tomando $i=9, j=16$, sale que $a_{16}+9$ debe ser un primo elevado al cuadrado. Por congruencia módulo $4$, se tiene que $a_{16}$ es múltiplo de $4$.
Tomando $i=16, j=16$, se tiene que $2a_{16}$ debe tener $6$ divisores. Pensando en la fórmula de $\tau$, o bien $2a_{16}=p^1q^2$ o bien $2a_{16} = p^5$. En el primer caso, como $a_{16}$ es par debe ser $q=2$ y así $a_{16}=2p$, pero entonces no sería múltiplo de $4$. Entonces $a_{16}=2^4=16$.
(Cómo costó este!)

Tomando $i=2, j=17$ se ve que $a_{17}$ es impar. Tomando $i=17, j=17$, $2a_{17}$ debe tener $4$ divisores, por lo que o bien $2a_{17}=p*q$ o bien $2a_{17}=p^3$. La segunda no puede porque debería ser $a_{17}=2^2=4$.
Entonces obtuvimos que $a_{17}$ es primo.
Tomando $i=8, j=17$, sale que $8+a_{17}$ es un cuadrado perfecto impar, por lo que $a_{17} \equiv 1 (4)$.
Tomando $i=7, j=17$, $7+a_{17}$ tiene $\tau(24)=(1+1)*(3+1)=8$ divisores. Además por lo que vimos antes, esa suma debe ser múltiplo de $4$.
Veamos las posibilidades de la factorización de $a_{17}$.
El $8$ como producto lo puedo formar como $8$, que diría que $7+a_{17} = 2^7 = 128$, por lo que $a_{17}=121$, pero $a_{17} + 2$ no es primo, absurdo;
Lo puedo formar como $2*2*2$ que diría que $7+a_{17} = p*q*r$, pero eso no puede ser múltiplo de $4$;
O lo puedo formar como $2*4$, que diría que $7+a_{17} = p*q^3$, que como debe ser múltiplo de $4$, tenemos que $7+a_{17} = 8p$, siendo entonces $a_{17} \equiv 1 (8)$.
Tomando finalmente $i=15, j=17$, tenemos que $15+a_{17}$ debe tener $6$ divisores, por lo que o bien $15+a_{17} = p*q^2$ o bien $15+a_{17}=p^5$. Como $15 \equiv -1 (8)$, tenemos que $15+a_{17}$ será múltiplo de $8$, descartando el primero caso. Luego por paridad $15+a_{17} = 2^5 = 32 \Rightarrow a_{17} = 17$.
(También costó)

Tomando $i=1, j=18$ sale que $a_{18}$ debe ser par. Tomando $i=j=18$, sale que $2a_{18}$ debe tener $\tau(36)=(2+1)*(2+1)=9$ divisores, por lo que: o bien $2a_{18} = 2^8 = 256 \Rightarrow a_{18}=128$, que no cumple que $a_1+a_{18}$ sea primo; o bien $2a_{18}=2^2*q^2 \Rightarrow a_{18} = 2q^2$.
Veamos el resto de $a_{18}$ en la división por $3$:
Si es $1$, tomando $i=2, j=18$ vemos que $\tau(a_{18}+2)=\tau(20)=(2+1)*(1+1)=6$. Esto dice que $a_{18}+2=p^5$ ó $a_{18}+2=p*q^2$. Como es par, la primera posibilidad da que $a_{18}=30$ que no cumple con el enunciado tomando $i=5, j=18$. La segunda posibilidad, como la suma es par y en este caso hipotético es múltiplo de $3$, debe ser que $a_{18}+2=2*3^2=18$ o bien $a_{18}+2=3*2^2=12$, ambas son absurdas pues la sucesión debe ser creciente.
Entonces el resto módulo $3$ de $a_{18}$ no puede ser $1$.
Si el resto es $2$, tomando $i=1, j=18$ sale que $a_{18}+1$, que debe ser primo pues $19$ es primo, será múltiplo de $3$. Absurdo pues $a_{18} > 3$.
Finalmente, $a_{18}$ debe ser múltiplo de $3$, por lo que $a_{18}=2*3^2=18$ necesariamente.
(Costó pero la idea del módulo $3$ estuvo piola y vino un poco rápido ahora)

Ahora, a partir de la posición $19$ hasta la $24$, podemos usar el argumento de los cuadrados perfectos pues se cumplen todas las hipótesis. Es decir, por ejemplo $a_{19} \geq 19, a_{19}+6$ y $a_{19}+17$ deben ser cuadrados perfectos distanciados por $11$.
Luego $a_{19}=19, a_{20}=20, a_{21}=21, a_{22}=22, a_{23}=23, a_{24}=24$.

Para la posición $25$ también puedo hacer esto, dado que desde $25$ faltan $11$ y $24$ para los siguientes cuadrados perfectos.
Y a partir de acá podré usar este argumento siempre.

Obviamente hay que demostrarlo.
Lo que voy a probar es que para todo número natural mayor a $25$, la distancia entre ese número y los dos siguientes cuadrados perfectos es menor a sí mismo.
Es decir, dado $n>25$, $(c-1)^2 \leq n < c^2$, ocurre que $(c+1)^2 - n < n \Rightarrow (c+1)^2 < 2n$.
De $(c-1)^2 \leq n$ se tiene que $c^2-2c+1 \leq n \Rightarrow 2c^2-4c+2 \leq 2n$.

$$2n \geq 2c^2-4c+2 = (c^2+2c+1)+(c^2-6c+1) > (c^2+2c+1)=(c+1)^2 \Leftrightarrow c^2-6c+1 > 0 \Leftrightarrow c^2 > 6c-1 \Leftrightarrow c > 5$$

Como $n > 25$, se tiene que el próximo cuadrado perfecto será al menos $6^2=36$, por lo que efectivamente para estos casos tenemos que $c > 5$. Esto significa que a partir de la posición $26$ siempre se cumplirán nuestras hipótesis que son que $a_k=k, a_m=m$ con $k, m$ definidos como antes (esto lo podemos garantizar porque se cumple para todo $i < n$) y además $a_n \geq n$ por lo mismo, porque todos los valores vienen siendo iguales a su posición.

Finalmente, después de todo esto, podemos concluir que la única sucesión que puede cumplir con el enunciado es $a_i = i$ para todo $i$ natural. Como trivialmente esta sucesión cumple, pues $i+j = a_i+a_j \Rightarrow \tau(i+j) = \tau(a_i+a_j)$, probamos que es la única.
1  
Responder