Vi a este problema recientemente. Se pide demostrar que siempre es posible elegir 100 números de 200 números positivos tales que su suma sea divisible por 100.
Intento de resolver: mi primer paso fue tomar mod de cada número. Ayuda porque entonces tenemos que trabajar sólo con números del 1 al 99 (200 en total). Entonces tengo que demostrar que siempre hay una suma tal que $a_1+a_2+a_3+...a_{100}$ donde $a_i \le 99$ es divisible por 100. Y aquí me quedé. Una sugerencia se agradece.
Este resultado es un caso especial de la famosa EGZ o Erdős Ginzburg Ziv teorema, que establece que cualquier conjunto de $2n-1$ enteros, debe tener algún subconjunto de tamaño $n$ cuya suma es múltiplo de $n$. Por lo tanto nos puede incluso tirar de uno de los 200 números; de cualquier 199 enteros, unos 100 debe sumar un múltiplo de 100.
Usted puede encontrar algunas hermosas pruebas de EGZ en mathoverflow.
El EGZ teorema puede ser demostrado a través de la de Cauchy-Davenport teorema:
Si $A$ $B$ son subconjuntos de a $\mathbb{Z}_{/100\mathbb{Z}}$, $$ |A+B| \geq \min(100,|A|+|B|-1) $$
o el Kneser del teorema:
Si $A,B$ son subconjuntos de a $\mathbb{Z}_{/100\mathbb{Z}}$ $C$ es el restringido sumset $\{a+b:(a,b)\in A\times B, a\neq b\}$, entonces: $$ |C| \geq \min(100,|A|+|B|-3). $$
Ambos teoremas puede ser demostrado a través de la Dirichlet cuadro de principio con bastante sofisticadas pruebas, o a través de la combinatoria nullstellensatz como se muestra por Noga Alon en la década de los ochenta.
En cualquier caso, entre los $199$ enteros hay seguro $100$ enteros tener suma $\equiv 0\pmod{100}$.
Así que he encontrado una solución en una vieja revista rusa para los estudiantes de secundaria (se llama "Kvant"). La instrucción es la siguiente:
Siempre es posible elegir entre un conjunto de $2n-1$ números de $n$ números tales que su suma es divisible por n. En otras palabras $\frac{a_1 + a_2 + ... + a_n}{n}$ es un entero.
Al parecer, para probar esta afirmación, en general, no es muy fácil, como se puede ver a partir de las respuestas. Pero uno puede demostrar un lema que es la clave para resolver el problema original.
Consideremos dos conjuntos de números con $2a-1$ $2b-1$ números en cada uno. Deja que estos dos conjuntos de satisfacer la instrucción anterior. A continuación, un conjunto con $2ab-1$ números también satisfacer la declaración.
La prueba de este lema es fácil:
Vamos a denotar los conjuntos con $2a-1$, $2b-1$, $2ab-1$ números como $S_a$, $S_b$, $S_{ab}$. Como $2ab-1>2b-1$ podemos optar $b$ números de $S_{ab}$ tales que su suma es divisible por $b$. Podemos eliminar el $b$ números de $S_{ab}$ $2a-1$ veces debido a $2ab-1=b(2a-1)+(b-1)$. Así que ahora tenemos $2a-1$ conjuntos de números con $b$ números en cada uno. Pero también sabemos que $S_a$ satisface la declaración (y la suma de los números en la que cada conjunto es divisible por $b$ ). Ahora reemplace el cada uno de $2a-1$ define por la suma correspondiente. Así que terminamos con un conjunto que contiene a $2a-1$ números. Obviamente, es posible elegir $a$ números de este conjunto, tales que su suma es divisible por $ab$.
Ahora para resolver el problema tenemos que demostrar la declaración para algunos pequeños números primos, simplemente por la fuerza bruta y, a continuación, utilizar el lema.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
