Provincial 2001 P2 N3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 2017 FOFO 7 años - Jurado-FOFO 7 años
OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1124
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Provincial 2001 P2 N3

Mensaje sin leer por Fran5 »

Sea $n$ la suma de todas las potencias de $19$, desde $19$ hasta $19^{2001}$:$$n=19+19^2+19^3+\cdots +19^{2001}.$$Hallar el resto de la división de $n$ por $7620$.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Avatar de Usuario
Javiermov
Mensajes: 117
Registrado: Vie 22 Jun, 2012 9:16 pm

Re: Provincial 2001 P2 N3

Mensaje sin leer por Javiermov »

Spoiler: mostrar
[math]

[math]

[math]
1  
Avatar de Usuario
Guty
Mensajes: 130
Registrado: Mié 17 Oct, 2012 3:48 pm
Nivel: Exolímpico
Ubicación: Munro, Buenos Aires

Re: Provincial 2001 P2 N3

Mensaje sin leer por Guty »

Spoiler: mostrar
Bueno, lo primero que uno hace es mirar las potencias de [math] módulo [math] y encuentra que: (EDITO: había puesto que [math], y bueno, [math])

[math]
[math]
[math]
[math]
[math]
[math]
---
[math]
[math]
[math]
[math]

(Podemos afirmar que se van a repetir porque uno siempre realiza la misma operación para alcanzar el siguiente número (multiplicar por [math]))

O sea, que a dos potencias de [math] con exponentes congruentes a un mismo número módulo [math] les corresponde el mismo resultado.

Las primeras [math] potencias suman [math]

Ahora, podemos agrupar en [math] grupitos de [math] potencias que suman lo mismo, y habremos obtenido la suma hasta [math]. Entonces si miramos nuestra suma módulo [math] nos queda:

[math]

Entonces [math]
1  
Avatar de Usuario
Ivan

Colaborador-Varias
Mensajes: 1023
Registrado: Vie 15 Oct, 2010 7:18 pm
Medallas: 1
Nivel: Exolímpico

Re: Provincial 2001 P2 N3

Mensaje sin leer por Ivan »

Javiermov escribió:
Spoiler: mostrar
[math]

[math]

[math]
Había un error de tipeo, en un lugar te olvidaste de restar el [math].

Igual esa cuenta no siempre anda. Acá anda casi que de casualidad. El problema es que [math] no es coprimo con [math], y lo que pasa es algo parecido a dividir por [math].

Si uno quiere resolver este problema ligeramente distinto:
Sea [math] la suma de todas las potencias de [math], desde [math] hasta [math]
[math]

Hallar el resto de la división de [math] por [math].
hacer lo mismo no anda:
[math]

[math]

[math]
pero en realidad [math]. El error está en el último renglón.


Explico por que vale en el caso del problema:
[math]
Si uno supiera que [math] entonces se puede tirar ese término y queda [math].

Por como son los números del problema vale que [math], pero no siempre pasa (tenemos el contraejemplo anterior). Una explicación de por qué en este caso particular anda es usando el lema de Hensel.

Otro ejemplo de por que hay que tener cuidado con las propiedades de las congruencias al dividir:
[math]
Si los denominadores son coprimos con el módulo no van a pasar estas cosas, pero si no hay que tener mucho cuidado y pensar bien cada paso.
5  
Guía de $\LaTeX$ (sirve para escribir ecuaciones como $2^{3\times 2}+1=13\cdot 5$)
Nowhereman

FOFO 6 años - Mención Especial-FOFO 6 años
Mensajes: 65
Registrado: Mar 17 Mar, 2015 12:18 pm
Medallas: 1
Nivel: 3

Re: Provincial 2001 P2 N3

Mensaje sin leer por Nowhereman »

El problema se resume en:
Spoiler: mostrar
Sea [math]; hallar [math].
Solucion:
Spoiler: mostrar
Factorizando: [math]

Notemos que [math]

Restando:
[math] los términos se cancelan.

[math]

Es fácil ver que [math]

volviendo a la ecuación anterior:

[math]

Puesto a que [math]

Ademas
[math]

[math]

Donde nos queda el sistema de ecuaciones de congruencias [math] que por el teorema chino del resto tiene una única solución.

Notemos que [math]

Es fácil notar que [math]

Entonces [math] [math]
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: 2208
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Provincial 2001 P2 N3

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Tenemos que\begin{align*}n & =19\left (1+19+19^2\right )\left (1+19^3+19^6+\cdots +19^{1998}\right ) \\
& =19\cdot 381\cdot \left (1+19^3+19^6+\cdots +19^{1998}\right ),
\end{align*}con lo que $n\equiv 0\pmod{381}$.
Tenemos que\begin{align*}n & =(1+19)\left (1+19^2+19^4+\cdots +19^{2000}\right )-1 \\
& =20\left (1+19^2+19^4+\cdots +19^{2000}\right )-1,
\end{align*}con lo que $n\equiv -1\pmod{20}$.
Por el Teorema Chino del Resto obtenemos entonces que $n\equiv 7239\pmod{7620}$.
Reemplazando $19$ por $x$, las mismas cuentas muestran que el resto de $n=x+x^2+x^3+\cdots +x^{2001}$ en la división por $(x+1)(x^2+x+1)$ es $x(x^2+x+1)$, lo que explica de dónde sale ese $7620$ que a priori parece tan arbitrario.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
marcoalonzo

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024
Mensajes: 124
Registrado: Mar 18 Abr, 2023 4:52 pm
Medallas: 2

Re: Provincial 2001 P2 N3

Mensaje sin leer por marcoalonzo »

Spoiler: mostrar
Notemos que
$\begin{array}{|c|c|}\hline
19^k&\pmod{7620}\\ \hline
19^1&19\\ \hline
19^2&361\\ \hline
19^3&6859\\ \hline
19^4&781\\ \hline
19^5&7219\\ \hline
19^6&1\\ \hline
19^7&19\\ \hline
19^8&361\\ \hline
\vdots&\vdots\\ \hline
\end{array}$
De modo que el resto de $19^k$ en la división por $7620$ depende del resto de $k$ en la división por $6$.
Además $\sum_{i=1}^{6}19^i=49659540\equiv0\pmod{7260}$. Luego podemos hacer $333$ grupitos de $6$ potencias de $19$ consecutivas, de forma tal que los exponentes de $19$ recorran todos los restos módulo $6$. Cada uno de estos grupitos sumará $0$ en módulo $7260$. Luego nos sobran $2001-333\cdot6=3$ elementos de un grupito, que corresponden a $19, 19^2,$ y $19^3$. Con lo cual $n\equiv\underbrace{0+0+0+\dots +0}_{333}+19+361+6859\equiv 7239\pmod{7620}$, que es lo que buscábamos.
1  
🔮oráculo y magia negra🔮
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024
Mensajes: 418
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 2
Nivel: 3
Contactar:

Re: Provincial 2001 P2 N3

Mensaje sin leer por drynshock »

marcoalonzo escribió: Vie 01 Dic, 2023 7:36 pm
Con tu mensaje me cagaste la racha de "Ultimos posteos" estaba a uno de tener la lista completa jajajajjaja
@Bauti.md ig // Ridin' in a getaway car // $\zeta (s) =\displaystyle\sum_{n = 1}^{\infty}\frac{1}{n^{s}}$
Avatar de Usuario
marcoalonzo

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024
Mensajes: 124
Registrado: Mar 18 Abr, 2023 4:52 pm
Medallas: 2

Re: Provincial 2001 P2 N3

Mensaje sin leer por marcoalonzo »

drynshock escribió: Vie 01 Dic, 2023 7:52 pm
marcoalonzo escribió: Vie 01 Dic, 2023 7:36 pm
Con tu mensaje me cagaste la racha de "Ultimos posteos" estaba a uno de tener la lista completa jajajajjaja
Ahora la tenés
Spoiler: mostrar
Mentira ya no jeje
1  
🔮oráculo y magia negra🔮
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024
Mensajes: 418
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 2
Nivel: 3
Contactar:

Re: Provincial 2001 P2 N3

Mensaje sin leer por drynshock »

Spoiler: mostrar
Notemos que $19 + 19^2 + ... + 19^6 \equiv 0 (mod 7620)$, luego para los siguientes términos nos queda $19^k(19 + 19^2 + ...+ 19^6)$. Finalmente notemos que $\frac{2001-3}{6}$ es entero, por lo que el resto va a quedar determinado por los tres términos sobrantes: $19 + 19^2 + 19^3 = 7239$.
@Bauti.md ig // Ridin' in a getaway car // $\zeta (s) =\displaystyle\sum_{n = 1}^{\infty}\frac{1}{n^{s}}$
Responder