Nacional 2002 N3 P1

Problemas que aparecen en el Archivo de Enunciados.

Nacional 2002 N3 P1

UNREAD_POSTpor JPablo » Vie 20 Jun, 2014 8:27 pm

En la pantalla de la computadora hay inicialmente escritos dos $1$. El programa insertar hace que al apretar la tecla $\text{Enter}$ se inserte entre cada par de números la suma de esos números.

En el primer paso se inserta un número y obtenemos $1-2-1$; en el segundo paso se insertan dos números y tenemos $1-3-2-3-1$; en el tercero se insertan cuatro números y se tiene $1-4-3-5-2-5-3-4-1$; etc. Hallar la suma de todos los números que figuran en la pantalla al finalizar el paso número $25$.
Avatar de Usuario
JPablo
 
Mensajes: 347
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: Nacional 2002 N3 P1

UNREAD_POSTpor JPablo » Vie 20 Jun, 2014 8:59 pm

Spoiler: Mostrar
Hay varias “cosas” que tiene cada sucesión, nosotros vamos a describir tres de ellas:

En primer lugar, cada sucesión tiene una cantidad de elementos. Vamos a definir $c\left ( k \right )$ como la cantidad de elementos que tiene la sucesión en el $k$-ésimo paso.

En segundo lugar, cada sucesión tiene una suma, que denotaremos por $s\left ( k \right )$.

En tercer lugar, aunque parezca raro, lo tendremos en cuenta: cada sucesión tiene guiones entre los números, y a la cantidad de guiones la denotaremos por $g\left ( k \right )$.

Primero que nada, demostraremos varias fórmulas:

Fórmula primera: $g\left ( k \right )=2^{k}$

Demostración: Para $k=1$ es cierto. Supongamos que vale para un $k$ genérico. Por lo tanto, tenemos como hipótesis inductiva que $g\left ( k \right )=2^{k}$. Buscamos ver que $g\left ( k+1 \right )=2^{k+1}$.

Notemos que en el paso $k+1$ cada guión se “dividirá” en dos guiones (en cada paso, introducimos un nuevo número entre dos números, es decir, pasamos de tener un intersticio a tener dos intersticios). Por lo tanto, la cantidad de guiones se duplica. Luego

$g\left ( k+1 \right )=2g\left ( k \right )=2\cdot 2^{k}=2^{k+1}$

Como queríamos demostrar. $\blacksquare$

Fórmula segunda: $c\left ( k \right )=2^{k}+1$

Demostración: Para cada guión, llamemos “compañero de guión” al número que tiene a su izquierda. Todos los guiones tienen un compañero de guión, pero no todos los números son compañeros de guión: el último número, el de la derecha, no es compañero de ningún guión. Por lo tanto, tenemos $g\left ( k \right )$ guiones acompañados de un número, y otro número sin compañero. Por lo tanto $c\left ( k \right )=g\left ( k \right )+1=2^{k}+1$. $\blacksquare$

Fórmula tercera: $s\left ( k \right )=3^{k}+1$

Demostración: Para $k=1$ es cierto. Supongamos que vale para un $k$ genérico. Luego, nuestra hipótesis inductiva es $s\left ( k \right )=3^{k}+1$ y buscamos demostrar que $s\left ( k+1 \right )=3^{k+1}+1$.

Para la sucesión $k$ sea $x_1$ el número ubicado a la izquierda, y sean $x_j$, $x_{j+1}$ dos números ubicados consecutivamente en la sucesión. Entonces

$s\left ( k \right )=\sum_{i=1}^{c\left ( k \right )}x_{i}$

Sabemos que $c\left ( k \right )=2^{k}+1$ y que, por hipótesis inductiva, $s\left ( k \right )=3^{k}+1$. Veamos cuánto vale $s\left ( k+1 \right )$:

Es claro que $s\left ( k+1 \right )$ es la suma entre $s\left ( k \right )$ y la suma entre cada par $x_j$, $x_{j+1}$. Entonces

$s\left ( k+1 \right )=s\left ( k \right )+\sum_{i=1}^{c\left ( k \right )}\left ( x_{i}+x_{i+1} \right )-x_{c\left ( k \right )}-x_{c\left ( k \right )+1}$

Le hemos restado $x_{c\left ( k \right )}+x_{c\left ( k \right )+1}$ porque: el primero, de la misma forma que $x_1$, participa una sola vez en la suma (a diferencia del resto de los $x_j$ que participan dos veces en la suma), y la sumatoria sola implicaría que participa dos veces. En el caso de $x_{c\left ( k \right )+1}$, ese número ni siquiera está definido, y la sumatoria implica que participa en la suma. Luego

$s\left ( k+1 \right )=\sum_{i=1}^{2^{k}+1}x_{i}+\sum_{i=1}^{2^{k}+1}\left ( x_{i}+x_{i+1} \right )-x_{2^{k}+1}-x_{2^{k}+1+1}$

$s\left ( k+1 \right )=\sum_{i=1}^{2^{k}+1}x_{i}+\sum_{i=1}^{2^{k}}\left ( x_{i}+x_{i+1} \right )$

$s\left ( k+1 \right )=\sum_{i=1}^{2^{k}+1}x_{i}+\sum_{i=1}^{2^{k}}x_{i}+\sum_{i=1}^{2^{k}+1}x_{i+1}$

Luego, como ya sabemos por hipótesis inductiva que

$s\left ( k \right )=\sum_{i=1}^{2^{k}+1}x_{i}=3^{k}+1$

Entonces

$s\left ( k+1 \right )=\left ( 3^{k}+1 \right )+\left ( 3^{k}+1-x_{2^{k}+1} \right )+\sum_{i=1}^{2^{k}}x_{i+1}$

Analicemos la única sumatoria que nos quedó: se ve claramente que se suman todos los números desde $x_2$ hasta $x_{2^{k}+1}$. Es claro y fácil de ver que $x_1=x_{2^{k}+1}=1$, ya que son los números que están en los extremos. Por lo tanto

$\sum_{i=1}^{2^{k}}x_{i+1}=\sum_{i=1}^{2^{k}+1}x_{i}-x_{1}=s\left ( k \right )-x_1=3^{k}+1-1=3^{k}$

Por lo tanto tenemos

$s\left (k+1  \right )=\left (3^k+1  \right )+\left (3^k+1-1  \right )+\left (3^k  \right )$

$s\left (k+1  \right )=3\cdot 3^{k}+1$

$s\left (k+1  \right )=3^{k+1}+1$

Como queríamos demostrar. $\blacksquare$

Finalmente, calculamos lo que nos pide el problema:

$s\left ( 25 \right )=3^{25}+1=847288609444$.
Avatar de Usuario
JPablo
 
Mensajes: 347
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: Nacional 2002 N3 P1

UNREAD_POSTpor Fran5 » Sab 21 Jun, 2014 12:46 pm

Spoiler: Mostrar
Una forma más fácil de calcular $s(k+1)$ es usar los subíndices módulo $c(k)$, es decir que $x_{c(k)+1}=x_1=1$ y observar que, como cada $x$ de $s(k)$ aparece en dos sumas y como sí mismo en $s(k+1)$, se tiene

$s(k+1) +2 = s(k) + \sum_{i=1}^{c(k)} x_i+x_{i+1} = 3 s(k)$

(El $+2$ lo agregamos por $x_{c(k)}+x_{c(k)+1}=x_{c(k)}+x_1=1 + 1 =2$)

Luego, Por inducción, sigue que que $s(k) = 3^{k}+1$

Donde $k$ es la cantidad de veces que hicimos la operación
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"
Avatar de Usuario
Fran5
 
Mensajes: 789
Registrado: Mié 21 Mar, 2012 1:57 pm
Ubicación: Santa Fe
Medals: 4
OFO - Medalla de Oro OFO - Jurado OFO - Jurado FOFO Pascua 2017 - Jurado
Nivel: Exolímpico

Re: Nacional 2002 N3 P1

UNREAD_POSTpor Gianni De Rico » Lun 11 Sep, 2017 9:41 pm

Forma todavía más corta de hacer la inducción
Spoiler: Mostrar
Después de probar los primeros casos y conjeturar que en el paso $n$ la suma da $3^n+1$, queda probar por inducción. Cada número nuevo está formado por la suma de los números adyacentes, es decir que metemos dos veces más cada número y una vez más los unos, porque tienen un sólo número adyacente. Entonces podemos poner juntos uno de cada par de números repetidos y los unos y tenemos otro $S_n$, si tuviésemos dos unos más tendríamos un tercer $S_n$, por lo que nos queda:

$S_{n+1}=S_n+S_n+S_n-2=3S_n-2=3^{n+1}+3-2=3^{n+1}+1$
$e^{i\pi}+1=0$
Avatar de Usuario
Gianni De Rico
 
Mensajes: 346
Registrado: Vie 16 Sep, 2016 6:58 pm
Ubicación: Rosario
Nivel: 3


Volver a Problemas Archivados

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado