Erdos-Ginzburg-Ziv 定理学习笔记

· · 个人记录

Erdos-Ginzburg-Ziv 定理： 对于 2n-1 个整数，一定能选出其中 n 个使得它们的和为 n 的倍数。

引理 1：如果两个正整数 m,n 都满足 EGZ 定理 (m>1,n>1)，那么 mn 一定也满足 EGZ 定理。

现在总共有 2mn-1 个数，我们把它分成两个可重集 A,B，使得 |A|=m(2n-1)，|B|=m-1。

那么我们一定可以进行如下操作 2n-1 次：

设第 i 次操作得到的可重集为 S_i，该可重集中元素和为 b_i。

由于 n 满足 EGZ 定理，则在 \frac{b_1}{m},\frac{b_2}{m},\dots,\frac{b_{2n-1}}{m} 中，一定能够取出 n 个数使得它们的和为 n 的倍数。

那么从 b_1,b_2,\dots,b_{2n-1} 中，一定能够取出 n 个数使得它们的和为 mn 的倍数。

所以存在其中 n 个可重集 S 含有的所有元素之和为 mn 的倍数，总共取出了 mn 个数。

引理 2：对于一个奇质数 p，如果有 k 个数 a_1,a_2,\dots,a_k 都与 p 互质 (1\le k < p)，且它们不都相同，那么从中取 0 个或若干个出来，它们的和对 p 取模，可能得到的数组成的集合为 S_{k}，那么一定有 |S_{k}|\ge k+1。

考虑用数学归纳法证明。

对于 k=2，显然成立，下面对于 k>2 进行归纳。

若 |S_{k-1}|\ge k+1，由于 S_{k-1} \subseteq S_k，那么一定有 |S_k|\ge k+1。

否则 |S_{k-1}|=k，此时设 S_{k-1} 中的数分别为 b_1,b_2,\dots,b_k。

现在我们要插入一个数 a_k。

我们可以得到一定存在一个 i\ (1\le i\le k)，使得 b_i+a_k 在模 p 下不存在于 S_{k-1} 中，这个可用反证法证明：

如果对于所有 i\ (1\le i\le k)，b_i+a_k 在模 p 下都存在于 S_{k-1} 中，那么就存在 \sum_{i=1}^{k} b_i \equiv \sum_{i=1}^{k} b_i+a_k\ (\operatorname{mod} p)，可得 ka_k \equiv 0\ (\operatorname{mod} p)，显然不成立，得证。

那么此时插入 a_k，就会有 |S_k|\ge|S_{k-1}|+1=k+1。

现在我们可以对 EGZ 定理进行证明了。

当 n \le 2 时，显然满足定理。

若 n 为一个合数，且所有奇质数也满足定理，那么根据引理 1也可得到 n 满足定理。

现在我们只需要证明所有奇质数 n 满足该定理。

设当前有 2n-1 个数 a_1 \le a_2 \le \dots \le a_{2n-1}，所有数已对 n 取模（这显然不会造成影响），即 0\le a_i < n。

若存在 i 使得 a_i=a_{i+n-1}\ (1\le i\le n)，那么就有 a_i=a_{i+1}=\dots=a_{i+n-1}，那么取出这些数即可满足要求。

那么剩下的情况对于任意 i 都存在 a_i\neq a_{i+n-1}\ (1\le i\le n)。

引理 3：设 b_i=a_{i+n}-a_{i+1}\ (1\le i <n)，那么 b_1,b_2,\dots,b_{n-1} 这些数取 0 个或若干个出来，它们的和对 n 取模，可能得到的数组成的集合 S 必然是模 n 的完系。

考虑如果当 b_1=b_2=\dots=b_{n-1}\ne0，结论显然成立。

否则可由引理 2得到结论成立。

现在可以先假设取了 a_1,a_2,\dots,a_n，得到的总和模 n 后为 c。

若 c=0，此时取这些数即可满足要求。

否则根据引理 3，可以加上若干个 b_i 使得 c=0，由于加上一个 b_i 的意义是不取 a_{i+1} 而换成 a_{i+n}，所以取的数字总数还是 n 个，满足要求。

综上可得证 Erdos-Ginzburg-Ziv 定理。