Nacional 2017 N3 P2

Avatar de Usuario
3,14

OFO - Medalla de Plata FOFO 6 años - Medalla Especial OFO - Medalla de Oro
Mensajes: 444
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 5
Nivel: Exolímpico

Nacional 2017 N3 P2

Mensaje sin leer por 3,14 » Sab 18 Nov, 2017 12:14 pm

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
Mensajes: 753
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2017 N3 P2

Mensaje sin leer por Gianni De Rico » Dom 24 Dic, 2017 5:00 pm

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

Responder