MENU

Erdos-Ginzburg-Ziv Theorem

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$

Related Problems

CF1798F Gifts from Grandfather Ahmed

对 EGZ 定理的简单运用,题目的数据范围允许从 $2n-1$ 个数中通过暴力背包 $O(n^3)$ 找出想要的 $n$ 个数。使用 std::bitset 则可以方便的做到 $O(n^3/w)$。

UOJ771【UER #11】科考工作

本题要求对 EGZ 定理给出一个高效的构造算法。

按照 Proof 1 的证明,我们可以给出一个构造算法,只需要做一个类似背包的操作即可。可以通过 std::bitset 做到 $O(n^2/w)$,另外由于在可达性背包问题中,每个位置值只会发生一次修改,可以基于此给出均摊的线段树 + hash 或 bit + 二分 + hash 做法,复杂度为 $O(n\log^2 n)$,但线段树做法常数较大,难以通过本题。

按照 Proof 2 的证明,我们只需要实现那个寻找 $kx\in S,(k+1)x \not\in S$ 的操作即可,这可以通过二分实现,复杂度 $O(n\log n)$。(arXiv:2208.07728 详细呈现了这个算法)

Last Modified: February 21, 2024
Archives Tip
QR Code for this page
Tipping QR Code