Provincial (Metropolitana) 2000 - Nivel 3 - Problema 1

Avatar de Usuario
Monazo

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González
Mensajes: 231
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 7
Nivel: Ñandú

Provincial (Metropolitana) 2000 - Nivel 3 - Problema 1

Mensaje sin leer por Monazo » Mié 20 May, 2020 4:01 pm

Se escribe una lista de números de acuerdo con las siguientes reglas: en el primer paso se escribe $84$; en el segundo paso se escribe $132$. A partir de aquí, en cada paso se escribe el número que resulta de sumarle al último número escrito el máximo común divisor de los dos últimos números escritos. Por ejemplo, el tercer número es el resultado de $132+\text{mcd}(84;132)$.

¿En qué paso se escribirá por primera vez un número terminado en $7$ ceros?

Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020
Mensajes: 20
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 3
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Provincial (Metropolitana) 2000 - Nivel 3 - Problema 1

Mensaje sin leer por Fedex » Jue 21 May, 2020 1:12 am

Spoiler: mostrar
Tomemos $2$ números consecutivos de la sucesión $x$ e $y$ ($y$ viene después de $x$) y escribamos a ambos como:
$x = mcd(x;y) . x'$
$y = mcd(x;y) . y'$
En donde $mcd(x';y')=1$
En el siguiente paso escribiríamos $z$ tal que:
$z = y + mcd(x;y) = mcd(x;y) . y' + mcd(x;y) = mcd(x;y) (y'+1)$
Ahora, notemos que como $y'$ y $y'+1$ son coprimos tenemos que $mcd(y;z) = mcd(x;y)$.
Esto quiere decir que el máximo común divisor entre $2$ parejas de números consecutivas de la sucesión es invariante y, en consecuencia, la condición de la secuencia es equivalente a una progresión aritmética de diferencia $ d = mcd(84;132) = 12$ (Que es la primera pareja de números consecutivos) y de $a_1 = 132$.
En algún $n$ sucede que:
$a_n = a_1 + (n-1).d = 132 + 12n - 12 = 120 + 12n \equiv 0 \; (mod \; 10^7)$
$120 + 12n = 10^7 k$ para algún entero positivo $k$ (minimizar $k$ minimiza $n$).
$10^7 k \equiv 4k \equiv 0 \; (mod \; 12)$ de donde se deduce que el mínimo $k \neq 0$ que cumple con esto es $k=3$.
Entonces:
$120 + 12n = 10^7 . 3$
$n = \frac{10^7 . 3 - 120}{12} = 2499990$
Pero como la sucesion no arranca en $132$ sino en $84$ entonces:
El primer paso en el que ocurre esto es el $2499991$.
2  
$\frac{9}{1^2} \binom{20}{18}$

Responder