ONEM 2019 - Fase 3 - Nivel 1 - P9

Problemas que aparecen en el Archivo de Enunciados.
luisq
Mensajes: 20
Registrado: Jue 25 Oct, 2018 10:45 am
Nivel: 3

ONEM 2019 - Fase 3 - Nivel 1 - P9

Mensaje sin leer por luisq »

Para cada entero positivo $n$, sea $G_n$ el número que se obtiene al escribir $n$ y a continuación $n-1$ (sin dejar espacio). Por ejemplo, $G_1=10$, $G_2=21$ y $G_{100}=10099$. Determine cuántos elementos distintos tiene el conjunto: $\left \{\text{mcd}(1,G_2),\text{mcd}(2,G_3),\text{mcd}(3,G_4),\ldots ,\text{mcd}(2018,G_{2019})\right \}$.

Aclaración: $\text{mcd}(a,b)$ denota al máximo común divisor de $a$ y $b$.

FabriATK

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Iván Sadofschi OFO - Medalla de Plata-OFO 2021
FOFO 11 años - Mención-FOFO 11 años
Mensajes: 32
Registrado: Mié 17 Abr, 2019 11:17 pm
Medallas: 6
Nivel: 2
Ubicación: Corrientes

Re: ONEM 2019 - Fase 3 - Nivel 1 - P9

Mensaje sin leer por FabriATK »

Spoiler: mostrar
$G_n = 10^a \times n + n-1$ para algún entero positivo $a$
$\Rightarrow mcd(n-1, G_n) = mcd(n-1, 10^a\times n + n-1)$
Como $mcd(x, y) = mcd(x, y \pm zx)$ (para $x,y,z$ enteros)
Entonces $mcd(n-1, 10^a\times n + n-1) = mcd(n-1, 10^a\times n + n - 1 - (n-1)) = mcd(n-1, 10^a\times n)$
y Como $mcd(n-1, n) = 1$:
$mcd(n-1, 10^a\times n) = mcd(n-1, 10^a)$
Como $n \leq 2019 \Rightarrow a \leq 4$
Y la cantidad de elementos distintos del conjunto será igual a la cantidad de divisores de $10^4$ menores a $2019$(notemos que $a$ también podría ser $1, 2$ o $3$, pero los divisores de $10$ elevado a cualquiera de ellos también son divisores de $10^4$)
$10^4 = 2^4\times 5^4$ y la cantidad de divisores de $10^4$ será $(4+1) \times (4+1) = 25$. Y los mayores a $2018$ son $10000$, $5000$ y $2500$
Y veamos que podemos construir un ejemplo para cada uno de los restantes:
Si queremos construir un ejemplo para $2^{m_1} \times 5^{m_2}$ tomamos $k$ tal que $2$ y $5$ no dividen a $k$ y si $b$ es la cantidad de dígitos de $2^{m_1} \times 5^{m_2} \times k$, entonces $10^b$ tenga al menos $m_1$ factores $2$ y $m_2$ factores $5$. Y elegimos $n = 2^{m_1} \times 5^{m_2} \times k +1 $
Como podemos construir un ejemplo para todos, entonces todos aparecen en el conjunto. Es decir que el conjunto pedido tiene $25 - 3 = 22$ elementos distintos.

Responder