Selectivo de IMO 2018 - Problema 6

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 872
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Selectivo de IMO 2018 - Problema 6

Mensaje sin leer por Matías V5 » Vie 04 May, 2018 3:38 pm

Sean $1 = d_1 < d_2 < \ldots < d_k = n$ todos los divisores positivos del número entero positivo $n$. Hallar todos los posibles valores de $k$ si se sabe que $n = d_2d_3 + d_2d_5 + d_3d_5$.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 872
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Re: Selectivo de IMO 2018 - Problema 6

Mensaje sin leer por Matías V5 » Vie 04 May, 2018 10:48 pm

Spoiler: mostrar
Voy a usar varias veces la siguiente observación: si un divisor $d_i$ con $i>1$ es coprimo con todos los divisores anteriores, entonces $d_i$ es primo. Esto es así porque en caso contrario, podríamos tomar un divisor propio $d$ de $d_i$, que sería también un divisor de $n$ y por lo tanto igual a un $d_j$ con $j<i$, pero este $d$ no es coprimo con $d_i$, contradiciendo la hipótesis.

En primer lugar podemos concluir de la observación anterior que $d_2 = p$ con $p$ primo (pues $d_2$ es coprimo con $1$). Ahora notemos que como $n = d_2d_3 + d_2d_5 + d_3d_5$ y tanto $n$ como los primeros dos términos del lado derecho son múltiplos de $p$, se deduce que $p \mid d_3d_5$.

Caso 1. $p \mid d_3$
Si $p \mid d_3$, entonces $\frac{d_3}{p}$ también es un divisor de $n$ y es menor que $d_3$, luego sólo puede ser $1$ o $p$, pero el primer caso se descarta porque $d_3 > d_2 = p$. Deducimos entonces que $d_3 = p^2$.
Ahora, en $n = d_2d_3 + d_2d_5 + d_3d_5$, tanto el lado izquierdo como los dos últimos términos del lado derecho son múltiplos de $d_5$, luego $d_5 \mid d_2d_3 = p \cdot p^2 = p^3$. Necesariamente entonces es $d_5 = p^3$, ya que los demás divisores ($1$, $p$ y $p^2$) ya aparecieron antes.
Reemplazando esta información en la igualdad del enunciado llegamos a que $n = p^3 + p^4 + p^5 = p^3 (1+p+p^2)$. Notemos que $1 + p + p^2$ es un divisor de $n$ que no es múltiplo de $p$ y además cumple $1 + p + p^2 = \frac{p^3 - 1}{p-1} \leq p^3 - 1 < p^3 = d_5$. La única forma de que esto ocurra es que sea $d_4 = 1 + p + p^2$. Entonces $n = d_4d_5$ y de esto se deduce que $n$ tiene $\boxed{k=8}$ divisores positivos (ya que en general $\frac{n}{d_j} = d_{k+1-j}$).
Un ejemplo de esta situación es $n = 56 = 2^3 \cdot 7 = 2^3 \cdot (1 + 2 + 2^2)$, que es fácil verificar que cumple la condición.

Caso 2. $p \nmid d_3$
Por la observación inicial tenemos que $d_3 = q$ con $q$ primo. Ahora, razonando como en el caso anterior, $d_5 \mid d_2d_3 = pq$ y entonces $d_5 = pq$, ya que los demás divisores ($1$, $p$ y $q$) ya aparecieron antes. Reemplazando esta información en la igualdad del enunciado llegamos a que $n = pq + p^2q + pq^2 = pq (1 + p + q)$. Afirmo que $1 + p + q \leq pq$: en efecto, esa desigualdad equivale a $pq - p - q + 1 \geq 2$, y el lado izquierdo se factoriza como $(p-1)(q-1)$. Al ser $p$ y $q$ primos distintos, el mínimo valor posible de esta expresión es $(2-1)(3-1) = 2$, como queríamos.
En particular esto implica que $1+p+q$ es un divisor de $n$ menor o igual que $d_5$, y claramente mayor que $d_3$. Así que sólo puede ser $d_4$ o $d_5$. Si es $d_4$, otra vez nos queda $n = d_4d_5$ que conduce a $k=8$ que ya sabemos que es una solución. Así que sólo hace falta analizar el caso $1+p+q = d_5 = pq$. Aquí queda $n = d_5^2$, de donde se deduce que $n$ tiene $\boxed{k=9}$ divisores positivos.
La demostración de la desigualdad que hicimos antes muestra también que $1+p+q = pq$ ocurre si y sólo si $p=2$ y $q=3$. Así obtenemos $n= 2 \cdot 3 \cdot (1+2+3) = 36 = 2^2 \cdot 3^2$, que tiene $9$ divisores positivos y es fácil verificar que cumple la condición del enunciado.

Cubiertos todos los casos, concluimos que los únicos posibles valores de $k$ son $8$ y $9$. $\blacksquare$
3  
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

Avatar de Usuario
enigma1234

OFO - Medalla de Oro
Mensajes: 45
Registrado: Sab 03 Jun, 2017 8:07 pm
Medallas: 1
Nivel: 2

Re: Selectivo de IMO 2018 - Problema 6

Mensaje sin leer por enigma1234 » Lun 07 May, 2018 4:47 pm

Spoiler: mostrar
Veamos que los únicos valores de $k $ son $8$ y $9$ para estos es fácil ver que $n=231,36$ respectivamente cumplen.
En el problema tenemos que $n=d_i.d_{k+1-i}$ para todo $i$ entonces:
$$n=d_5.d_{k-4}=d_2d_3+d_3d_5+d_5d_2\dots (1) $$
De esto:$d_5.d_{k-4}>d_3d_5 \to d_{k-4}>d_3\to k-4>3\to k>7$
Supongamos que $k\geq 10$,es fácil ver que $d_2$ es primo, sea $d_2=p $ si $(d_2,d_3)=1$ entonces es fácil notar que $d_3$ es primo($d_3=q$) y si $(d_2,d_3)=p $ entonces $d_3=px $ $x>1$ y $x $ no puede tener divisores mayores que 1 y coprimos con $p $ pues serian otros divisores menores que $px $ entonces $x$ es una potencia de $p $ entonces $d_3$ es una potencia de $p $ y como es el menor divisor mayor que $p $ $\to d_3=p^2$.
De $(1) $ tenemos que $d_5 (d_{k-4}-d_2-d_3)=d_2.d_3 \to d_5\mid d_2.d_3$.
Si $d_3=q,\to d_5\mid pq ,d_5>d_2,d_3=p,q $ $\to d_5=pq=d_2d_3$ y si $d_3=p^2\to d_5\mid p^3$ y $d_5>d_3=p^2$ entonces $d_5=p^3=d_2d_3$. En ambos casos $d_5=d_2.d_3$ entonces $d_{k-4}=d_2+d_3+1$.
Como $k\geq 10$ $\to d_2+d_3+1=d_{k-4 }\geq d_6>d_5=d_2d_3\to 2>(d_2-1)(d_3-1)$ pero como $1 <d_2 <d_3$ entonces $2\leq d_2,3\leq d_3$ $\to 2> (d_2-1)(d_3-1)\geq 1.2$ lo que es una contradicción. Entonces $k<10$ y como $k>7$ los únicos valores posibles de $k$ son $8,9$ y cumplen por lo dicho al principio.
1  
One in a millon...my lucky strike! :D

Responder