Erdős, Ginzburg y Ziv demuestran lo siguiente: Sea $n \geq 1$ y $a_1,\ldots, a_{2n-1}\in \mathbb{Z}$ . Existen distintos $i_1,\ldots , i_n$ tal que $$ a_{i_1} + \cdots + a_{i_n} \equiv 0 \pmod{n}. $$ ¿Existe alguna prueba que no utilice el teorema de Chevalley-Warning (o una variante de su prueba)?
Respuestas
¿Demasiados anuncios?
El original de la prueba utilizada de Cauchy-Davenport lema. Varias pruebas se dan en este artículo de Alon-Dubiner (Las pruebas tratar sólo con el caso de al $n$ es primo, pero deducir el caso general es sencillo de allí). Tenga en cuenta que las ideas detrás de la mayoría de estas pruebas podría ser interpretado como un caso especial de los más poderosos teorema que se conoce comúnmente como "Combinatoria Nullstellensatz" (como se ha demostrado por N. Alon, ver aquí). La palabra clave para obtener resultados como estos es "de suma Cero Ramsey teoría".
ETA: también puede encontrar el papel de Olson, "Un problema combinatorio en lo finito abelian grupos", Revista de Teoría de números (1969) Vol.1 muy interesante. Resulta una generalización de EGZ teorema para finitos abelian p-grupos (creo que este fue uno de los primeros entre muchas otras generalizaciones).
JimmyJ
Puntos
1443
Esto es lo que recuerdo de una prueba que se me ocurrió hace tiempo (apareció en algunos concursos). Estoy seguro de que es conocida, pero como la prueba es corta, la pondré aquí:
La afirmación puede reducirse al caso en que $n=p$ es primo. Ahora se deduce de lo siguiente:
Lema : Dejemos que $2\leq i\leq p$ y considerar cualquier conjunto $A$ de elementos $ a_1,\cdots, a_{2i-1} \in \mathbb F_p$ de tal manera que no $i$ de ellos son los mismos. Dejemos que $S$ sea el conjunto de todas las sumas de $i$ elementos de $A$ . Entonces $\left|S\right|\geq i$ .
Prueba : Inducción en $i$ el caso $i=2$ es fácil. Supongamos que el resultado es verdadero para $p>i=k\geq 2$ . Considere el conjunto $A'$ de $2k+1$ elementos $\{a_1,\cdots,a_{2k-1},b,c\}$ WLOG podemos suponer que $b,c$ representan los dos elementos que aparecen con más frecuencia en $A'$ . Por supuesto $b\neq c$ .
El conjunto $\{a_1,\cdots,a_{2k-1}\}$ satisface la condición de que cualquier frecuencia es menor que $k$ De lo contrario, habrá $3$ elementos que aparecen al menos $k$ veces en $A'$ imposible. Por inducción podemos elegir $k$ subconjuntos de $k$ elementos cuyas sumas $s_1,\cdots, s_{k}\in \mathbb F_p$ son distintos. Sea $B=\{b+s_1,\cdots, b+s_{k}\}$ y $C=\{c+s_1,\cdots, c+s_{k}\}$ , obviamente $\left|B\right|=\left|C\right|=k$ . Lo haremos mostrando $B \neq C$ . Si no, sumando todos los elementos de cada conjunto se obtiene $k(b-c)=0$ imposible. QED.
Aplicando el lema para $i=p$ , tenga en cuenta que si hay $p$ elementos idénticos entonces su suma es $0$ .
Por cierto, hice algunas preguntas sobre las generalizaciones de este teorema, y obtuve muy buenas respuestas aquí .
