Nacional 2017 N3 P2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
FOFO 9 años - Jurado-FOFO 9 años
Mensajes: 457
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 6
Nivel: Exolímpico

Nacional 2017 N3 P2

Mensaje sin leer por 3,14 »

En una fila hay escritos $51$ números enteros positivos. Su suma es $100$. Un entero es representable si se puede expresar como suma de varios números consecutivos de la fila de $51$ enteros. Demostrar que para cada $k$, con $1\leq k\leq 100$, uno de los números $k$ y $100-k$ es representable.
[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: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2017 N3 P2

Mensaje sin leer por Gianni De Rico »

Reformulamos el problema:
Spoiler: mostrar
Ponemos los números en una circunferencia, resulta entonces que si $k$ es representable en la circunferencia, entonces $100-k$ también lo es, con los números sobrantes. Si todos los números son representables, entonces cuando convertimos la circunferencia en una tira, para cada par de números $k$ y $100-k$ pueden pasar $3$ cosas:
Que $k$ quede en los extremos de la tira, y quede $100-k$ entre ellos.
Que $100-k$ quede en los extremos de la tira, y quede $k$ entre ellos.
Que $k$ quede completamente de un lado de la tira, y $100-k$ del otro.

En cualquier caso, tenemos que por lo menos uno entre $k$ y $100-k$ es representable en la tira.
Vamos a usar el siguiente lema:
Spoiler: mostrar
Lema: Si tenemos $k+1$ enteros positivos cuya suma es menor o igual a $2k$, existen algunos de ellos cuya suma es exactamente $k$.
Demostración: Sean $x_1, x_2, \ldots, x_{k+1}$ los enteros positivos, y consideramos los números
$x_1$
$x_1 + x_2$
$x_1 + x_2 + x_3$
$\ldots$
$x_1 + x_2 + x_3 + \ldots + x_{k+1}$
Por el principio del palomar, entre estos $k+1$ números hay dos que tienen el mismo resto en la división por $k$. Supongamos que $x_1+...+x_i$ y $x_1+...+x_j$ tienen el mismo resto en la división por $k$, con $i < j$. Entonces su diferencia, que es $x_{i+1} + ... + x_j$, es múltiplo de $k$, y como es un entero positivo menor que $2k$, tiene que ser exactamente $k$.
Solución:
Spoiler: mostrar
Tomemos los $51$ grupos de $k+1$ números consecutivos. Si todos ellos tienen suma mayor que $2k$ tenemos que la suma total es mayor a $51\times 2k$, pero esta suma es $100(k+1)$, ya que estamos contando cada número $k+1$ veces. Por lo tanto, $100(k+1)>51\times 2k$, o lo que es lo mismo, $100k+100>102k\Rightarrow 100>2k\Rightarrow 50>k$

Tenemos entonces que para todo $k\geqslant 50$ existe por lo menos un grupo de $k+1$ números consecutivos con suma menor o igual a $2k$, y por el lema son todos representables. Por lo que dijimos al principio, tenemos que todos los números menores o iguales a $100-50=50$ son representables. Luego, todos los números son representables. Y nuevamente por lo que dijimos al principio, para todo $k$, por lo menos uno entre $k$ y $100-k$ es representable en la tira.
♪♫ do re mi función lineal ♪♫
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: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: Nacional 2017 N3 P2

Mensaje sin leer por Fran5 »

Gianni De Rico escribió: Dom 24 Dic, 2017 5:00 pm
Spoiler: mostrar
Tenemos entonces que para todo $k\geq 50$ existe por lo menos un grupo de $k+1$ números consecutivos (...)
:?:

No entiendo.. esto anda tomando números repetidos?

EDIT: Si. Lo verificamos con Gabriel :D Tomas los números $a_i$ con $i \in \mathbb{N}$ y lo mirás módulo $51$
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Responder