Nacional 2018 P1 N2

Problemas que aparecen en el Archivo de Enunciados.
tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado FOFO 7 años - Jurado
FOFO 8 años - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 593
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 10
Nivel: Exolímpico

Nacional 2018 P1 N2

Mensaje sin leer por tuvie » Sab 10 Nov, 2018 7:09 am

Se hace una lista de $2018$ números con el siguiente procedimiento: el primer número es el $47$, el segundo número es el $74$, y a partir de allí, cada número es igual al número que forman las dos últimas cifras de la suma de los dos números anteriores:
$47,$ $74,$ $21,$ $95,$ $16,$ $11,$ ...
Bruno eleva cada uno de los $2018$ números al cuadrado y los suma. Determinar el resto de dividir esta suma por $8$.

bruno
Mensajes: 216
Registrado: Vie 17 Dic, 2010 12:50 am

Re: Nacional 2018 P1 N2

Mensaje sin leer por bruno » Dom 11 Nov, 2018 1:12 pm

Spoiler: mostrar
Primero hago una lista comparando el resto modulo $8$ de $x^{2}$ respecto del resto modulo $8$ de $x$:

$\begin{matrix}
x &x^{2} \\
0 &0 \\
1 &1 \\
2 &4 \\
3 &1 \\
4 &0 \\
5 &1 \\
6 &4 \\
7 &1
\end{matrix}$

Como se puede ver el resto de $x^{2}$ se repite en un ciclo de $4$. Entonces si $x\equiv a (mod 8)$ e $y\equiv b (mod 8)$ / $\mid a-b \mid =4$ entonces $x^{2}\equiv y^{2} (mod 8)$.

Ahora en la lista, si $x$ e $y$ son dos numeros consecutivos el siguiente sera $x+y$ si $x+y<100$ o $x+y-100$ si $x+y\geq 100$ . Pero como $100\equiv 4 (mod 8)$ entonces $(x+y)^{2}\equiv (x+y-100)^{2} (mod 8)$ .Por lo tanto se puede operar directamente sobre los restos$mod 8$ de los numero en la lista, ya que se llegara al mismo resultado al elevar al cuadrado.

Empezando con los primeros dos numeros de la lista que tienen resto $7$ el primero y resto $2$ el segundo, se forma un ciclo infinito de $12$ restos: $7, 2, 1, 3,4, 7, 3, 2, 5, 7, 4, 3$ y luego se volvera a repetir $7,2,...$. Entonces si la lista tiene $2018$ numeros tendra $168$ de estos ciclos y un $7,2$.

Ahora si fijamos el resto de $x^{2}$ del ciclo se tiene : $1, 4 ,1, 1, 0, 1, 1, 4, 1, 1, 0, 1$. La suma de esos restos es multiplo de $8$. Entonces la suma de un ciclo entero es multiplo de $8$. Entonces solo importa fijarse en el resto modulo $8$ de los primeros dos numeros del ciclo. Sus cuadrados tienen resto $1$ el primero y $4$ el segundo.

Entonces el resto modulo $8$ de la suma de los $2018$ cuadrados de la lista es $1+4=5$

Matías

OFO - Medalla de Bronce FOFO Pascua 2019 - Medalla OFO - Medalla de Plata FOFO 8 años - Medalla Especial OFO - Medalla de Oro
Mensajes: 189
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 7
Nivel: 3

Re: Nacional 2018 P1 N2

Mensaje sin leer por Matías » Mar 03 Sep, 2019 7:23 pm

Spoiler: mostrar
Sea $(a_n)_{n\in N\wedge n\leq 2018}$ tal que $a_1=47$, $a_2=74$ y $a_{n+2}=a_{n+1}+a_n-100\lfloor\frac{a_{n+1}+a_n}{100}\rfloor$ $\forall(n\in N\wedge n\leq 2016)$. Tenemos que $a_{n+2}\equiv a_{n+1}+a_n(4)$ $\forall(n\in N\wedge n\leq 2016)$.
Sea $(b_n)_{n\in N\wedge n\leq 2018}$ tal que $b_n\in\{0,1,2,3\}\wedge b_n\equiv a_n(4)$ $\forall(n\in N\wedge n\leq 2018)$. Tenemos que $b_1=3$, $b_2=2$ y $b_{n+2}\equiv b_{n+1}+b_n(4)$.
Como $b_n\equiv a_n(4)$ tenemos que $b_n^2\equiv a_n^2(8)$ $\forall(n\in N\wedge n\leq 2018)$ ya que $4\mid b_n-a_n\implies 2\mid b_n-a_n\implies 2\mid b_n-a_n+2a_n=b_n+a_n$, así que $8=2\times 4\mid (b_n+a_n)(b_n-a_n)=b_n^2-a_n^2$.
Entonces tenemos que $\sum_{i=1}^{2018}a_i^2\equiv\sum_{i=1}^{2018}b_i^2(8)$.
Como $b_1=3$, $b_2=2$, $b_3=1$, $b_4=3$, $b_5=0$,
$b_6=3$, $b_7=3$, $b_8=2$ y se repite el ciclo, así que $b_{6k+1}=3$, $b_{6k+2}=2$ $\forall(k\in N_0\wedge k\leq 336)$, $b_{6k+3}=1$, $b_{6k+4}=3$, $b_{6k+5}=0$,
$b_{6k+6}=3$ $\forall(k\in N\wedge k\leq 335)$,
por lo tanto $\sum_{i=1}^{2018}b_i^2\equiv 336(3^2+2^2+1^2+3^2+0^2+3^2)+(3^2+2^2)\equiv 9+4\equiv 5(8)$, por lo tanto $\sum_{i=1}^{2018}a_i^2$ tiene resto $5$ en la división por 8.
2  

Responder