FOFO 12 Años - Problema 3

Uli Pereira

OFO - Mención-OFO 2018 OFO - Mención-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años OFO - Medalla de Bronce-OFO 2020
FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Plata-OFO 2021
Mensajes: 12
Registrado: Mar 23 Ene, 2018 12:30 am
Medallas: 9
Nivel: 3

FOFO 12 Años - Problema 3

Mensaje sin leer por Uli Pereira »

Demostrar que existe un número natural $a$ tal que $2^{5n}+5^n\cdot a$ es un múltiplo de $999$ para todo entero positivo impar $n$. Hallar el menor valor posible de $a$ tal que se cumpla lo pedido.
Uli Pereira

OFO - Mención-OFO 2018 OFO - Mención-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años OFO - Medalla de Bronce-OFO 2020
FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Plata-OFO 2021
Mensajes: 12
Registrado: Mar 23 Ene, 2018 12:30 am
Medallas: 9
Nivel: 3

Re: FOFO 12 Años - Problema 3

Mensaje sin leer por Uli Pereira »

Aquí publicaremos la solución oficial.
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 OFO - Medalla de Plata-OFO 2022 FOFO Pascua 2022 - Mención-FOFO Pascua 2022
Mensajes: 52
Registrado: Mié 17 Abr, 2019 11:17 pm
Medallas: 8
Nivel: 3
Ubicación: Corrientes

Re: FOFO 12 Años - Problema 3

Mensaje sin leer por FabriATK »

Solución:
Spoiler: mostrar
Supongamos que existe $a$ tal que $999 \mid 2^{5n} + 5^na$ para cierto $n$
y Veamos que:

$2^{5(n+2)} + 5^{n+2}a - (2^{5n} + 5^na) = 2^{5n}\times(2^{10} -1) + 5^n\times(5^2 -1) = 2^{5n} \times 1023 + 5^na\times 24$

Pero $1023 \equiv 24 \pmod{999}$

Así que $2^{5(n+2)} + 5^{n+2}a - (2^{5n} + 5^na) \equiv 2^{5n}\times 24 + 5^na\times 24 \equiv 24\times(2^{5n} + 5^na) \equiv 0 \pmod{999}$

Así que si encontramos un $a$ que cumpla que $999 \mid 2^{5} + 5a$ (es decir, $n = 1$), ese mismo $a$ va a cumplir para todo $n$ impar. Además, si es el menor $a$ que cumple que $999 \mid 2^{5} + 5a$, en general será el menor $a$(ya que sinó ese $a$ no funciona para $n = 1$, y no cumple para todo $n$ impar).

Ahora, busquemos el mínimo $a$ que cumple:
necesitamos que:
$999 \mid 2^{5} + 5a$
$999 \mid 32 + 5a$
como $a$ es natural, $2^{5} + 5a$ es positivo.
Entonces $999 \leq 2^{5} + 5a$
Pero $5 \nmid 999- 32$
Entonces buscamos el siguiente múltiplo de $999$:
Pero $5 \nmid 2\times 999 - 32 $
Asi que vamos al siguiente que será $3\times 999 = 2997$
Y $2997 - 32$ es múltiplo de $5$. Así que el menor valor de $a$ es $\frac{2997-32}{5} = 593$ y estamos.
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
Mensajes: 2015
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 14
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO 12 Años - Problema 3

Mensaje sin leer por Gianni De Rico »

FabriATK escribió: Mar 25 Oct, 2022 8:22 pm Solución:
Spoiler: mostrar
Supongamos que existe $a$ tal que $999 \mid 2^{5n} + 5^na$ para cierto $n$
y Veamos que:

$2^{5(n+2)} + 5^{n+2}a - (2^{5n} + 5^na) = 2^{5n}\times(2^{10} -1) + 5^n\times(5^2 -1) = 2^{5n} \times 1023 + 5^na\times 24$

Pero $1023 \equiv 24 \pmod{999}$

Así que $2^{5(n+2)} + 5^{n+2}a - (2^{5n} + 5^na) \equiv 2^{5n}\times 24 + 5^na\times 24 \equiv 24\times(2^{5n} + 5^na) \equiv 0 \pmod{999}$

Así que si encontramos un $a$ que cumpla que $999 \mid 2^{5} + 5a$ (es decir, $n = 1$), ese mismo $a$ va a cumplir para todo $n$ impar. Además, si es el menor $a$ que cumple que $999 \mid 2^{5} + 5a$, en general será el menor $a$(ya que sinó ese $a$ no funciona para $n = 1$, y no cumple para todo $n$ impar).
Otra forma de terminarlo
Spoiler: mostrar
Buscamos $a$ tal que $2^5+5a\equiv 0\pmod{999}$, es decir, $5a\equiv -32\pmod{999}$. Multiplicando por $200$ a ambos lados nos queda $1000a\equiv -6400\pmod{999}$. Pero $1000a\equiv a\pmod{999}$ y $-6400\equiv 593\pmod{999}$. Entonces $a$ cumple si y sólo si $a\equiv 593\pmod{999}$, así que el menor natural que anda es ni más ni menos que $593$.
1  
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
Responder