Selectivo 49° IMO 2008 - Problema 4

Problemas que aparecen en el Archivo de Enunciados.
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

Selectivo 49° IMO 2008 - Problema 4

Mensaje sin leer por sebach »

Denotamos [math] al número de divisores positivos del entero [math], incluyendo [math] y [math]. Hallar todos los enteros positivos [math] tales que [math] es un entero primo.
Avatar de Usuario
Vladislao

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
FOFO Pascua 2017 - Jurado-FOFO Pascua 2017
Mensajes: 808
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Selectivo 49° IMO 2008 - Problema 4

Mensaje sin leer por Vladislao »

Spoiler: mostrar
Pongamos, para facilitar [math] con [math]. Entonces, [math]. Todo ésto, porque es trivial ver que [math]

Del enunciado, tenemos, entonces que [math].

Esto, bastante grotesco en principio, se puede simplificar a: [math]. (1)

De la última igualdad, se sigue que si [math], entonces [math] esta ecuación arroja como únicos resultados [math] y [math] ó [math] y [math]. En tales casos, los valores de [math] son [math] ó [math].

De ahora en más [math]. Es realmente útil notar que dado un entero positivo [math], se tiene que [math] (la prueba de ésto es sencilla puesto que [math]. Y es realmente fácil advertir que [math] para todo entero positivo).

Ahora usamos este pequeño dato, en el hecho de que si [math], entonces [math] (directo de nuestro lemita). Analizamos los casos según [math] ó [math].

Caso 1) [math]. Por nuestro lema, es inmediato que [math]. Entonces, recordando (1), se tiene que [math]. En este caso, tenemos que si [math] la desigualdad es cierta para todo [math]. Y si [math] la única posibilidad es [math] que conduce a [math] que ya teníamos.

Si [math], entonces [math] o lo que es lo mismo: [math]. (2)
Como [math], entonces [math], la única posibilidad es [math] y [math].

Entonces la ecuación (2) se convierte en [math], es decir que el lado derecho es par, pero cada primo [math] con [math] es mayor o igual que 5 (por hipótesis). Absurdo.

En conclusión las únicas posibilidades para el caso 1 son [math] ó [math].

Caso 2) Lo termino otro día, tengo sueño.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.
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: Selectivo 49° IMO 2008 - Problema 4

Mensaje sin leer por sebach »

Yo habia sacado sacado que si n era de la forma 8*p, esto iba a tener 8 divisores, y entonces el resultado era p. Ejemplo: 8*5=40, divisores de 40=1, 2, 4, 5, 8, 10, 20, 40 ----> d(40)=8. Y 40/8=5.
Creo que era porque: Como 8|n, 4|n y 2|n. Entonces hasta aca tenes 4 divisores: 1, 2, 4 y 8.
Al agregarle un primo p>2, como es coprimo con todo el resto excepto con 1, se agregan el 8*p, 4*p y el 2*p. Entonces d(n)=8.
Pero no se cómo sacar cuáles son todos los n, sé que estos casitos valen...
Avatar de Usuario
Vladislao

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
FOFO Pascua 2017 - Jurado-FOFO Pascua 2017
Mensajes: 808
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: Selectivo 49° IMO 2008 - Problema 4

Mensaje sin leer por Vladislao »

Sí con [math] también funciona. Es lindo este problema, lástima que sea 'un poco largo'.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.
Avatar de Usuario
Johanna

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2017 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 65
Registrado: Lun 22 Oct, 2012 9:38 pm
Medallas: 9
Nivel: Exolímpico

Re: Selectivo 49° IMO 2008 - Problema 4

Mensaje sin leer por Johanna »

Spoiler: mostrar
Notemos que la ecuación se puede reescribir de la siguiente manera:
[math], siendo [math] un número primo.
Como ambos números son iguales tenemos que [math]
Notemos que como [math] es primo si [math], ahora si [math] es divisor de [math] entonces escribimos [math]

Entonces [math]

y [math]
[math]

Llamemos [math] entonces queda que [math]
Esto se puede interpretar como que la cantidad de divisores de [math] es al menos [math] por lo que como el mayor divisor de [math], distinto de [math] es a lo sumo [math] entonces la maxima cantidad de divisores de [math], es [math].

Caso [math]

Si [math] es impar entonces la máxima cantidad de divisores de [math] es [math], lo cual solo se cumple si [math].

Caso [math]
Si [math] entonces hay a lo sumo un número menor a [math] que no divide a [math] entonces se cumple alguna de las dos expresiones:
[math] (1)
[math] (2)

De esto se deduce que [math]

Finalmente los posibles valores de [math]

Si [math] Entonces [math] es primo por lo que no existen soluciones
Si [math] Entonces [math]
Si [math] Entonces [math]
o [math] no hay soluciones
Si [math] Entonces [math] no hay soluciones
Si [math] Entonces [math] no hay soluciones
o [math]
[math] no hay soluciones
Si [math] Entonces [math] lo cual no tiene soluciones
o [math] lo cual no tiene soluciones
o [math]
o [math] lo cual no tiene soluciones
Si [math] Entonces [math] lo cual no tiene soluciones
[math] lo cual no tiene soluciones
[math] lo cual no tiene soluciones
[math]n=p_1p_2^5\Rightarrow p_1^2p_2^3=12p_1 \Rightarrow[math]n=p_1^2p_2^3[math] no tiene soluciones
[math] no tiene soluciones
[math]

entonces [math]
BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años
OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 414
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 16
Nivel: 3

Re: Selectivo 49° IMO 2008 - Problema 4

Mensaje sin leer por BrunZo »

Spoiler: mostrar
Lema: $d(n)<2\sqrt{n}$.
Demo: Para cada uno de los divisores $d\le\sqrt{n}$, podemos emparejarlo con $\frac{n}{d}\ge\sqrt{n}$. De este modo, si hay $x$ divisores $d\le\sqrt{n}$, entonces hay a lo sumo $2x$ divisores totales ("a lo sumo" porque podríamos estar repitiendo $\sqrt{n}$). Pero como los $x$ divisores son números entre $1$ y $\sqrt{n}$, entonces $d(x)\le 2x\le 2\sqrt{n}$.
Ahora bien, notar que la igualdad no podría darse, porque para que $x=\sqrt{n}$ sí o sí $\sqrt{n}$ debería ser entero, y por ende, divisor de $n$, pero en dicho caso lo contamos dos veces en las parejas y entonces no puede ocurrir $d(x)=2x$. De este modo, $d(n)<2\sqrt{n}$.

El lema implica que $p=\frac{n}{d(n)}>\frac{n}{2\sqrt{n}}=\frac{\sqrt{n}}{2}$, de donde $n<4p^2$. Si $p^2\mid n$ entonces obligatoriamente $n$ es $p^2$, $2p^2$ o $3p^2$. En cada caso tenemos respectivamente que:
1) $p=\frac{p^2}{3}$, luego $p=3$, de donde $n=9$.
2) $p=\frac{2p^2}{6}$ si $p\neq 2$, luego $p=3$, de donde $n=18$; y si $p=2$ entonces $n=8$, que anda.
3) $p=\frac{3p^2}{6}$ si $p\neq 3$, luego $p=2$, de donde $n=12$; y si $p=3$ entonces $n=27$ que NO anda.
En resumen tenemos los casos $8$, $9$, $12$, $18$, que andan.

Ahora, si esto no ocurre, entonces $n=pk$ donde $k$ es coprimo con $p$. De este modo, se puede escribir $d(n)=2d(k)$, y entonces
$$p=\frac{n}{d(n)}=\frac{pk}{2d(k)}$$
lo que se reduce a $k=2d(k)$. Volviendo a apelar al Lema, $k=2d(k)<4\sqrt{k}$, luego $k<16$. Esto nos da $15$ valores posibles para $k$.
¡Pero no desesperemos! No puede ser $k=1$ puesto que $1\neq 2\times 1$.
Tampoco puede ser $k=q$ primo, puesto que $q\neq 2\times 2=4$ para ningún primo $q$. Esto descarta $2$, $3$, $5$, $7$, $11$ y $13$.
Tampoco puede ser $k=q^2$ con $q$ primo, puesto que $q^2\neq 2\times 3=6$ para ningún primo $q$. Esto descarta $4$ y $9$.
Tampoco puede ser $k=qr$ con $q$ y $r$ primos, puesto que $qr\neq 2\times 2\times 2=8$ para ningunos primos $q$, $r$. Esto descarta $6$, $10$, $14$ y $15$
Los únicos números que quedan entre $1$ y $15$ son $8$ y $12$, que sorprendentemente funcionan ambos (lo vimos arriba).
Esto nos da los casos $8p$ y $12p$, que se puede comprobar que funcionan.

En total tenemos que $n$ puede ser $8$, $9/12/18$, $12p$, $18p$.
2  
Responder