Selectivo IMO 2019 - Problema 4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Selectivo IMO 2019 - Problema 4

Mensaje sin leer por Matías V5 »

Hallar todos los enteros positivos $n$ para los cuales existe un entero positivo $k$ tal que para todo divisor positivo $d$ de $n$, el número $d-k$ también es un divisor (no necesariamente positivo) de $n$.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020 OFO - Jurado-OFO 2021
Mensajes: 1114
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 8
Nivel: Exolímpico

Re: Selectivo IMO 2019 - Problema 4

Mensaje sin leer por Matías V5 »

Spoiler: mostrar
Supongamos que existe un tal entero positivo $k$. Notemos que $n-k$ debe ser un divisor de $n$ menor que $n$, por lo tanto, $n-k \leq \frac{n}{2}$, de donde $k \geq \frac{n}{2}$. Veamos que de hecho no puede ser $k = \frac{n}{2}$. Si esto ocurre, necesariamente $n$ es par para que $k$ sea entero, y entonces $\frac{n}{2}$ es un divisor de $n$. Si tomamos $d = \frac{n}{2}$ y hacemos $d - k$, obtenemos $0$, que no es un divisor de $n$. Entonces $k > \frac{n}{2}$.
Por otra parte, como $1$ es un divisor positivo de $n$, también $1-k$ debe ser un divisor de $n$, así que $1-k \geq -n$, de donde $k \leq n+1$. Si $k<n+1$, entonces $1-k > -n$ y por lo tanto debe ser $1-k \geq -\frac{n}{2}$, de donde $k \leq 1 + \frac{n}{2}$.
Del análisis anterior vemos que hay solamente dos posibilidades: o bien $k=n+1$, o bien $\frac{n}{2} < k \leq \frac{n}{2} + 1$. Dejamos la primera posibilidad para el final, y analizamos la segunda considerando dos casos, según si $n$ es par o impar.
Si $n$ es par, digamos $n=2m$, la desigualdad anterior es $m < k \leq m+1$, así que $k=m+1$. Ahora $n-k = m-1$ tiene que ser un divisor de $n=2m$. Pero $m-1$ divide a $2m-2$, luego, para que divida a $2m$, tiene que dividir a $2$. Las únicas posibilidades son $m=2$ y $m=3$, que nos conducen a $n=4$ y $n=6$. Verifiquemos que ambos son soluciones:
Los divisores positivos de $4$ son $1$, $2$ y $4$. Al restarles $3$ obtenemos $-2$, $-1$ y $1$, que son divisores de $4$.
Los divisores positivos de $6$ son $1$, $2$, $3$ y $6$. Al restarles $4$ obtenemos $-3$, $-2$, $-1$ y $2$, que son divisores de $6$.
Supongamos ahora que $n$ es impar, digamos $n=2m-1$. Ahora la desigualdad de antes es $m - \frac{1}{2} < k \leq m + \frac{1}{2}$, de donde $k=m$. Tenemos que $n-k = m-1$ tiene que ser un divisor de $n=2m-1$. Razonando como antes llegamos a que $m-1$ divide a $1$, así que $m=2$ y obtenemos $n=3$, que es solución ya que al restarle $2$ a $1$ y a $3$ obtenemos $-1$ y $1$ respectivamente.
Sólo nos resta analizar el caso $k=n+1$. Observemos que en este caso, para todo divisor positivo $d$ de $n$ el número $d-k$ es negativo. Se deduce que al restarle $n+1$ a todos los divisores positivos de $n$ debemos obtener todos los divisores negativos de $n$. Más precisamente, si $1 = d_1 < d_2 < \ldots < d_t = n$ son todos los divisores positivos de $n$, entonces al restarles $n+1$ debemos obtener $-d_t, -d_{t-1}, \ldots, -d_1$ respectivamente.
Si $t=1$ entonces $n=1$, que es solución porque al restarle $2$ obtenemos $-1$.
Supongamos $t \geq 2$ y tomemos $d=d_2$. Observemos que $d_2 \cdot d_{t-1} = n$, de donde $d_{t-1} = \frac{n}{d}$. Con esto, la igualdad $d_2 - (n+1) = -d_{t-1}$ se convierte en $d - (n + 1) = -\frac{n}{d}$, que multiplicando por $d$ y reacomodando términos equivale a $d^2 - (n+1)d + n = 0$. Las raíces de esta ecuación cuadrática en $d$ son $1$ y $n$. Pero $d=1$ es imposible, pues $d_2 > d_1 = 1$. Así que $d=n$, lo que significa que $n$ tiene sólo dos divisores positivos, es decir que es primo. Todos ellos son soluciones ya que al restarle $p+1$ a los divisores positivos $1$ y $p$ obtenemos $-p$ y $-1$ respectivamente.
En conclusión, los valores de $n$ que cumplen la condición del enunciado son: el $1$, el $4$, el $6$ y todos los primos. $\blacksquare$
1  
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
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 IMO 2019 - Problema 4

Mensaje sin leer por BrunZo »

Creo que es parecida a la de arriba: Solución:
Spoiler: mostrar
Es claro que $n$ primo cumple con $k=n+1$. Desde ahora $n$ es compuesto.
Denotemos por $f(d)$ a $d-k$. Es claro que que $f(x)-f(y)=x-y$
Sean $1=d_1<d_2<\dots<d_{m-1}<d_m=n$ los divisores positivos de $n$. Es claro que $d_{m-1}\leq \frac{n}{2}$. Luego, $k\geq\frac{n}{2}$.

Parte primera: $f(d_{m-1})<0$:
Spoiler: mostrar
Supongamos que $f(d_{m-1})\geq 1$.
Entonces, $f(n)-f(d_{m-1})\leq d_{m-1}-1\leq \frac{n}{2}-1$.
Pero, $n-d_{m-1}\geq\frac{n}{2}$.
Absurdo.
Parte segunda: $f(d_1)>-n$:
Spoiler: mostrar
Supongamos que $f(d_1)=-n$.
Entonces, $d_2-1=f(d_2)-f(d_1)\geq n-d_{m-1}\geq\frac{n}{2}$.
Pero, esto implica que $d_2>\frac{n}{2}$, por lo que no podría ser divisor de $n$.
Absurdo.
Parte tercera: $n\leq 6$
Spoiler: mostrar
De este modo, tenemos que para todo $i$, necesariamente $f(d_i)=-d_{m-i}$.
Entonces $k=d_{m-1}+1$, por lo que $f(n)=n-d_{m-1}-1=(d_2-1)d_{m-1}-1$.
Ahora, $d_{m-1}\leq (d_2-1)d_{m-1}-1\Longleftrightarrow 1\leq (d_2-2)d_{m-1}\Longleftrightarrow d_2=2$.
Entonces, queremos todos los $n$ pares tales que $\frac{n}{2}-1$ dividen a $n$.
Es claro que $\frac{n}{2}$ también lo divide y es coprimo con el otro divisor, luego $n\geq\frac{n}{2}(\frac{n}{2}-1)=\frac{n^2}{4}-\frac{n}{2}\Longleftrightarrow 6n\geq n^2\Longleftrightarrow n\leq 6$.
De entre estos casos, no es difícil notar que sólo $1$, $4$ y $6$ funcionan.
En definitiva, tenemos que los casos que funcionan son
Spoiler: mostrar
$1$, $4$, $6$ y todos los primos
1  
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 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo IMO 2019 - Problema 4

Mensaje sin leer por Gianni De Rico »

BrunZo escribió: Mar 16 Abr, 2019 5:58 pm
Spoiler: mostrar
$1\leq (d_2-2)d_{m-1}\Longleftrightarrow d_2=2$
Chei...
Spoiler: mostrar
Si $d_2=2$ entonces te queda $$1\leqslant (d_2-2)d_{m-1}=0\cdot d_{m-1}=0$$ que claramente es falso.
♪♫ do re mi función lineal ♪♫
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 IMO 2019 - Problema 4

Mensaje sin leer por BrunZo »

Gianni De Rico escribió: Sab 20 Abr, 2019 6:21 pm
BrunZo escribió: Mar 16 Abr, 2019 5:58 pm
Spoiler: mostrar
$1\leq (d_2-2)d_{m-1}\Longleftrightarrow d_2=2$
Chei...
Spoiler: mostrar
Si $d_2=2$ entonces te queda $$1\leqslant (d_2-2)d_{m-1}=0\cdot d_{m-1}=0$$ que claramente es falso.
Spoiler: mostrar
Sí, debe de ser un error de tipeo. Me parece que la desigualdad está invertida. O sea, uno debería tener $d_{m-1}\geq f(n)=(d_2-1)d_{m-1}-1$ en vez de $d_{m-1}\leq f(n)=(d_2-1)d_{m-1}-1$...
EDIT:
Spoiler: mostrar
Me acabo de dar cuenta que en ese caso, uno tendría
$$d_{m-1}\geq (d_2-1)d_{m-1}-1\Longrightarrow 1\geq (d_2-2)d_{m-1}\Longrightarrow d_2\leq 2\Longrightarrow d_2=2$$
que tiene un poquitín más de análisis (hay que notar que $d_2$ y $d_{m-1}$ son mayores que $1$), pero con eso se está.
Responder