Nacional 2002 N3 P1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
JPablo
Mensajes: 356
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Nacional 2002 N3 P1

Mensaje sin leer por JPablo » Vie 20 Jun, 2014 8:27 pm

En la pantalla de la computadora hay inicialmente escritos dos [math]. El programa insertar hace que al apretar la tecla [math] 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 [math]; en el segundo paso se insertan dos números y tenemos [math]; en el tercero se insertan cuatro números y se tiene [math]; etc. Hallar la suma de todos los números que figuran en la pantalla al finalizar el paso número [math].

Avatar de Usuario
JPablo
Mensajes: 356
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: Nacional 2002 N3 P1

Mensaje sin leer por 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 [math] como la cantidad de elementos que tiene la sucesión en el [math]-ésimo paso.

En segundo lugar, cada sucesión tiene una suma, que denotaremos por [math].

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 [math].

Primero que nada, demostraremos varias fórmulas:

Fórmula primera: [math]

Demostración: Para [math] es cierto. Supongamos que vale para un [math] genérico. Por lo tanto, tenemos como hipótesis inductiva que [math]. Buscamos ver que [math].

Notemos que en el paso [math] 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

[math]

Como queríamos demostrar. [math]

Fórmula segunda: [math]

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 [math] guiones acompañados de un número, y otro número sin compañero. Por lo tanto [math]. [math]

Fórmula tercera: [math]

Demostración: Para [math] es cierto. Supongamos que vale para un [math] genérico. Luego, nuestra hipótesis inductiva es [math] y buscamos demostrar que [math].

Para la sucesión [math] sea [math] el número ubicado a la izquierda, y sean [math], [math] dos números ubicados consecutivamente en la sucesión. Entonces

[math]

Sabemos que [math] y que, por hipótesis inductiva, [math]. Veamos cuánto vale [math]:

Es claro que [math] es la suma entre [math] y la suma entre cada par [math], [math]. Entonces

[math]

Le hemos restado [math] porque: el primero, de la misma forma que [math], participa una sola vez en la suma (a diferencia del resto de los [math] que participan dos veces en la suma), y la sumatoria sola implicaría que participa dos veces. En el caso de [math], ese número ni siquiera está definido, y la sumatoria implica que participa en la suma. Luego

[math]

[math]

[math]

Luego, como ya sabemos por hipótesis inductiva que

[math]

Entonces

[math]

Analicemos la única sumatoria que nos quedó: se ve claramente que se suman todos los números desde [math] hasta [math]. Es claro y fácil de ver que [math], ya que son los números que están en los extremos. Por lo tanto

[math]

Por lo tanto tenemos

[math]

[math]

[math]

Como queríamos demostrar. [math]

Finalmente, calculamos lo que nos pide el problema:

[math].

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 OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González
Mensajes: 940
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 12
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2002 N3 P1

Mensaje sin leer por Fran5 » Sab 21 Jun, 2014 12:46 pm

Spoiler: mostrar
Una forma más fácil de calcular [math] es usar los subíndices módulo [math], es decir que [math] y observar que, como cada [math] de [math] aparece en dos sumas y como sí mismo en [math], se tiene

[math]

(El [math] lo agregamos por [math])

Luego, Por inducción, sigue que que [math]

Donde [math] 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
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 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: 1242
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2002 N3 P1

Mensaje sin leer por 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 [math] la suma da [math], 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 [math], si tuviésemos dos unos más tendríamos un tercer [math], por lo que nos queda:

[math]
Queda Elegantemente Demostrado

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: Nacional 2002 N3 P1

Mensaje sin leer por Fedex » Lun 18 May, 2020 12:44 am

Spoiler: mostrar
Llamemos $S_n$ a la suma de números en la pantalla una vez apretado el enter $n$ veces.
Siendo la configuración: $a_1$, $a_2$, $a_3$ , ... , $a_k$
$S_n = \sum_{i=1}^{k}a_i$
En donde es claro que los extremos: $a_1 = a_k = 1$
Ahora, escribamos a $S_{n+1}$ en función de $S_n$:
$S_{n+1} = S_n + \sum_{i=1}^{k-1}a_i + a_{i+1}$
(Si tenemos $a_x$ y $a_{x+1}$ en el medio escribiríamos $a_x + a_{x+1}$).
$S_{n+1} = S_n + \sum_{i=1}^{k-1}a_i + a_{i+1} = S_n + \sum_{i=1}^{k-1}a_i + \sum_{i=1}^{k-1} a_{i+1} = S_n + \sum_{i=1}^{k-1}a_i + \sum_{i=2}^{k} a_{i} = S_n + \sum_{i=1}^{k-1}a_i + \sum_{i=2}^{k} a_{i} + a_1 + a_k - 2$
$S_{n+1} = S_n + 2\sum_{i=1}^{k} a_i - 2 = 3 S_n-2$

De esta forma tenemos lo que queríamos, una relación de recurrencia definida por:
$S_0 = 2$
$S_{n+1} = 3 S_n-2$

Lemita: $S_n = 3^n . S_0 - 2 (1 + 3 + ... + 3^{n-1})$
Spoiler: mostrar
Para $S_1$ es claro ya que $S_1 = 3 S_0 - 2$
Entonces si $S_n = 3^n . S_0 - 2 (1 + 3 + ... + 3^{n-1})$
$S_{n+1} = 3 S_n-2 = 3 (3^n . S_0 - 2 (1 + 3 + ... + 3^{n-1})) - 2 = 3^{n+1}. S_0 - 2 (3 + 3^2 + ... + 3^{n}) - 2$
Finalmente $S_{n+1} = 3^{n+1} . S_0 - 2 (1 + 3 + 3^2 + ... + 3^{n})$ y estamos.
Entonces:
$S_n = 3^n . S_0 - 2 (1 + 3 + ... + 3^{n-1}) = 3^n . S_0 - 2 (\frac{3^n -1}{2}) = 3^n . S_0 - 3^n + 1$
Como $S_0 = 2$
$S_n = 3^n + 1$

Entonces:
$S_{25} = 3^{25} +1$
Y esa es la respuesta.
1  
$\frac{9}{1^2} \binom{20}{18}$

Responder