Un problema basado en casillero

Question

Los números de 1 a 1994 se dividen en 6 juegos.Muestran que al menos en un grupo hay dos números cuya suma es también en ese grupo ?

Podemos demostrar que al menos un grupo contendrá más de 332 elementos.

Un conjunto se llama suma libre, si NO CONTIENE la suma de dos cualesquiera de sus elementos o no contiene el doble de un elemento Si un conjunto contiene números naturales de 1 a $2n+1$ la suma de sus partes libre de larga contendrá $n+1 $elementos.O en otras palabras, si tomamos la última mitad de los números de $(\frac{n}{2} $ o $\frac{n+1}{2}$ según el número de elementos del conjunto) será gratuito.

Pero no puedo continuar porque mi selección no necesitan ser consecutivos números.

Tengo que demostrar que si un conjunto contiene más de 332 números no puede ser de suma de forma gratuita..Pero, ¿Cómo..?

Answer 1

Esto es de la OMI de 1978. El problema original es

Una sociedad internacional que cuenta con miembros procedentes de seis países diferentes. La lista de miembros que contiene los nombres de 1978, numerado 1, 2, . . . , 1978. Demostrar que hay al menos uno de sus miembros, cuyo número es la suma de los números de dos miembros de su propio país o en dos veces tan grande como el número de uno de los miembros de su propio país.

Aquí está la solución de Arthur Engel Estrategias de Resolución de problemas, que es donde vi por primera vez

Answer 2

El teorema de Schur (una de las muchas cosas que llaman, por lo menos) los estados que particionado $\{1, ..., n\}$ a $k$ subconjuntos $S_1, \dots, S_k$ siempre tiene un poco de $S_i$ no suma-libre (es decir, no existe$x, y\in S_i$$x + y\in S_i$) si $n > k!\, e$. Desde $6! e = 1927.16 < 1994$, el resultado de la siguiente manera.

Dado que esta es una tarea problema, no sé cuánto combinatoria que ha cubierto ya y qué herramientas están disponibles para usted; como tal, yo te recomiendo buscar pruebas de Schur del teorema, si no ha sido presentado en la clase ya y adaptar los argumentos para este caso. (No sé la prueba de improviso, pero parece ser susceptibles de estándar de Ramsey-estilo de argumentos. El valor de $1994$ en el problema original es también sospechosamente cerca de la enlazado a partir del teorema de Schur.)