Nacional 2002 N3 P1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
JPablo
Mensajes: 351
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: 351
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 - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 797
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 4
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
Mensajes: 410
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario

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

Responder