Проблема Эрдеша – Гинзбурга – Зива

Теорема (ЭГЗ). Пусть $n \in \mathbb {N}, a_1, \ldots , a_{2n-1} \in \mathbb {Z}$. Тогда $\exists I \subset \{ 1, 2, \ldots , 2n-1\} \colon $ $|I| = n$ и $\sum \limits _{i\in I} a_ i \equiv 0\pmod n$.

Замечание. Если взять $2n-2$ числа, то утверждение теоремы может оказаться неверным. Например, $\underbrace{0, \ldots , 0}_{n-1}, \underbrace{1, \ldots , 1}_{n-1}$. Ноль можно заменить на число, сравнимое с нулём по модулю $n$ (чтобы все числа были различными).

$\blacktriangle $ Рассмотрим случай, где $n = p$. Даны числа $a_1, \ldots , a_{2p-1}$. Предположим, что
$\forall I \subset \{ 1, 2, \ldots , 2p-1\}, |I| = p\colon \sum \limits _{i\in I} a_ i \not\equiv 0\ (p)$.
Рассмотрим
$$ S = \sum \limits _{\substack { \scriptscriptstyle I \subset \{ 1, 2, \ldots , 2p-1\} \\ \scriptscriptstyle |I| = p}} \left(\sum \limits _{i\in I} a_ i \right)^{p-1} \stackrel{\mbox{МТФ}}{\equiv } \sum \limits _{\substack {\scriptscriptstyle I \subset \{ 1, 2, \ldots , 2p-1\} \\ \scriptscriptstyle |I| = p}} 1 = C_{2p-1}^ p \equiv 1\pmod p $$

Докажем, что $C_{2p-1}^ p \equiv 1$. Это следует из того, что $C_{2p}^ p \equiv 2\ (p)$ и

$C_{2p}^0 + C_{2p}^1 + \ldots + C_{2p}^{p-1} + C_{2p}^ p + C_{2p}^{p+1} + \ldots + C_{2p}^{2p-1} + C_{2p}^{2p} = 4^ p \equiv _ p 4\ =$

$= 1 + 0 +\ldots + 0 + C_{2p}^ p + 0 + \ldots + 1 \Rightarrow C_{2p}^ p \equiv 2\ (p)$.

Расскроем скобки в записи $S$ выше (наборы во второй сумме упорядочены, $\alpha _{j_*} \neq 0, 1\leqslant q \leqslant p-1$).
$$ S = \sum \limits _{\substack {\scriptscriptstyle I \subset \{ 1, 2, \ldots , 2p-1\} \\ \scriptscriptstyle |I| = p}} \sum \limits a_{i_1}^{\alpha _{i_1}} \cdot \ldots \cdot a_{i_ p}^{\alpha _{i_ p}} = \sum \limits _{\substack {\scriptscriptstyle I \subset \{ 1, 2, \ldots , 2p-1\} \\ \scriptscriptstyle I = \{ i_1, \ldots , i_ p\} }} \sum \limits a_{j_1}^{\alpha _{j_1}}\cdot \ldots \cdot a_{j_ q}^{\alpha _{j_ q}}. $$

Для скольких $I \subset \{ 1, 2, \ldots , 2p-1\} , |I| = p$ во внутреннем суммировании возникнет $a_{j_1}^{\alpha _{j_1}}\cdot \ldots \cdot a_{j_ q}^{\alpha _{j_ q}}$?

Для тех $I$, которые целиком содержат набор индексов $\{ j_1, \ldots , j_ q\} $, т.е. для $C_{2p-1-q}^{p-q} \equiv 0\ (p)$
$\forall q = 1, \ldots , p-1$.

Любой моном входит в сумму делящееся на $p$ число раз $\Rightarrow $  сумма делится на $p$. Противоречие. $\blacksquare $

Упражнение. Доказать, что если Теорема Э-Г-З верна для $n_1, n_2$, то она верна и для $n_1 \cdot n_2$.