Erdos-Ginzburg-Ziv Theorem

对任意 $2n-1$ 个整数，可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。

形式化的，对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$，存在两两不同的 $i_1,\dots,i_n$ 使得：
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$

Proof 1

接下来给一种初等证明。

引理 1：若 EGZ 定理对 $n,m$ 分别成立，则其对 $nm$ 成立。

证明：考虑任意 $2nm-1$ 个整数 $a_1,\dots,a_{2nm-1}$，首先取出 $n-1$ 个数，从剩下的数中取出 $n$ 个，我们可以从这 $2n-1$ 个数中找出 $n$ 个数使其和为 $n$ 的倍数，这样就又留下了 $n-1$ 个数，重复这个过程，我们可以得到 $2m-1$ 个数 $s_1,\dots,s_{2m-1}$，其均为 $n$ 的倍数。对于 $\dfrac{s_1}{n},\dots,\dfrac{s_{2m-1}}{n}$，我们可以找出 $m$ 个数使其和为 $m$ 的倍数。于是我们从 $2nm-1$ 个数中找到了 $nm$ 个数和为 $nm$ 的倍数。$\blacksquare$

由引理 1，我们只需要证明 EGZ 定理对于质数 $p$ 成立即可。

接下来的所有运算在 $\mathbb F_p$ 上进行。

引理 2：$2\le n\le p$，若大小为 $2n-1$ 的可重集 $A$ 中不存在 $n$ 个相同的数，令 $S$ 为 $A$ 中任意 $n$ 个数的和构成的不可重集合，有 $|S|\ge n$。

证明：对 $n$ 归纳。$n=2$ 的情况是 trivial 的。

现在假设引理对 $n$ 成立，下证其对 $n+1$ 成立。

考虑大小为 $2n+1$ 的可重集 $A'=\{a_1,\dots,a_{2n-1},b,c\}$，不妨设 $b,c$ 为 $a_1,\dots,a_{2n-1}$ 中出现次数最多的两个数，$b\ne c$。$A'$ 中没有数出现了 $\ge n+1$ 次，则 $A=\{a_1,\dots,a_{2n-1}\}$ 没有数出现了 $\ge n$ 次，否则 $A'$ 中除 $b,c$ 外还有数出现了 $n$ 次，即至少三个数出现了 $n$ 次，这显然是不可能的。

根据归纳假设，我们可以从 $A$ 中取出 $n$ 个子集，其元素和不同，设这些和为 $s_1,\dots,s_n$。设 $B=\{s_i+b\},C=\{s_i+c\}$，若 $B\ne C$，则引理得证，否则 $B$ 和 $C$ 的元素和相同，即 $n(b-c)=0$，由于 $p$ 是质数，$n,(b-c)$ 非零，于是这与假设矛盾。$\blacksquare$

接下来考虑分两种情况讨论。

在 $2p-1$ 个数中有一个数出现了不少于 $p$ 次，则这 $p$ 个数的和就是 $p$ 的倍数。
否则，通过引理 2 可知，$|S|\ge p$，事实上 $S$ 构成模 $p$ 的完全剩余系，故可以找到 $p$ 个数是 $p$ 的倍数。

综上，定理得证。$\blacksquare$

Proof 2

为了加深对定理的认识，这里还有另外一种证法。

证明的主体是相似的，我们直接来考虑规模为质数 $p$ 且没有数出现了不少于 $p$ 次的情况。

此时，我们总是可以将 $2p-1$ 个数分成 $p-1$ 组两数不等的数对和一个单独的数，事实上引理 2 就是做了这件事情。我们先选中单独的数和每组数中较小的那个，这样我们就已经选出了 $p$ 个数，只不过和可能不是 $p$ 的倍数。接下来我们会说明，我们可以通过调整一些组的选择方案而使总和成为 $p$ 的倍数。

将每组中的两数作差，问题转化为：从 $p-1$ 个非 $0$ 整数中选取若干个，使其和模 $p$ 等于 $r$。

我们可以证明，$p-1$ 个非 $0$ 整数的所有子集和模 $p$ 的值构成的集合大小为 $p$，也就是构成了模 $p$ 的完系，这样自然上述问题总能解决。

我们考虑动态维护一个集合 $S$ 和一个数集 $A$，保证 $S$ 中的数都可以通过 $A$ 的子集和模 $p$ 得到（反之则未必成立）。初始 $S=\{0\},A=\varnothing$，接下来我们将 $p-1$ 个数逐个加入 $A$。

向 $A$ 中加入 $x$ 时，考虑长度为 $p$ 的序列 $a_{0\dots p-1}$，其中 $a_k=kx$，由于 $x$ 非 $0$ 且 $p$ 是质数，所以 $a_k$ 取遍 $0\sim p-1$。因为 $a_0\in S$ 且 $\exists k,a_k\not\in S$，所以总有 $k$ 使得 $a_k\in S \land a_{k+1}\not \in S$，此时只要将 $x$ 和组成 $kx$ 的数拼起来，就可以将 $S$ 的大小扩大 $1$。重复此过程 $p-1$ 次后，$S$ 的大小恰好为 $p$。$\blacksquare$

Catalog

Erdos-Ginzburg-Ziv Theorem