Nacional 2014 N3 P6

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 829
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Nacional 2014 N3 P6

Mensaje sin leer por Gianni De Rico » Dom 29 Jul, 2018 9:14 pm

Spoiler: mostrar
Supongamos que existen enteros positivos $a_1<a_2<\ldots <a_k$ tales que todas las sumas $a_i+a_j$ con $1\leqslant i<j\leqslant k$ son distintas y hay entre ellos $n$ enteros consecutivos, con $n$ máximo. Sean $g+1,g+2,\ldots g+n$ dichos enteros.

Desarrollamos el siguiente algoritmo:
Elegimos $a_{k+1}=\sum \limits _{i=1}^ka_i+1$, agregamos $g+n+1-a_{k+1}$ al conjunto, sumamos $G=1-(g+n+1-a_{k+1})$ a todos los números del conjunto.

Demostración de que el algoritmo funciona:
Spoiler: mostrar
Sea $a_{k+1}=\sum \limits _{i=1}^ka_i+1$, tenemos que $g+n\leqslant a_{k-1}+a_k\Rightarrow g+n+1\leqslant a_{k-1}+a_k+1<a_{k+1}\Rightarrow g+n+1-a_{k+1}<0<a_1$, además, $a_{k+1}+a_x$ es mayor que cualquiera de las sumas anteriores y $g+n+1-a_{k+1}+a_x<0$ para todo $1\leqslant x\leqslant k$. Entonces los enteros $g+n+1-a_{k+1}<a_1<a_2<\ldots <a_k<a_{k+1}$ cumplen que las sumas de cualesquiera dos de ellos son distintas dos a dos, y todos los enteros desde $g+1$ hasta $g+n+1$ aparecen en ellas. Ahora, sea $G=1-(g+n+1-a_{k+1})$, sumando $G$ a $g+n+1-a_{k+1}$ y $a_x$ para $1\leqslant x\leqslant k+1$ tenemos que las desigualdades se mantienen, todos los números son positivos (pues el menor de ellos es $1$), que las sumas de cualesquiera dos de ellos son distintas dos a dos (ya que todas las sumas aumentaron en $2G$) y que aparecen entre ellas $n+1$ enteros consecutivos (desde $2G+g+1$ hasta $2G+g+n+1$).
Luego, si entre las sumas de dos de los enteros positivos $a_1<a_2<\ldots <a_k$ aparecen $n$ números consecutivos, podemos generar un nuevo conjunto de enteros que cumpla con las condiciones tal que aparezcan entre sus sumas $n+1$ enteros consecutivos. Tomando $k=2$, vemos que un entero positivo ($a_1+a_2$) aparece entre las sumas, entonces podemos aplicar nuestro algoritmo $n$ veces logramos que aparezcan $n+1$ números consecutivos entre las sumas. En particular, aplicándolo $999$ veces logramos que aparezcan $1000$ enteros consecutivos entre las sumas.
[math]

Responder