wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

算法基础

二维偏序

高维前缀和

树上差分

中位数定理

栈和队列

区间加等差数列

EGZ定理

[[ item.c ]]

EGZ定理

## Cauchy-Davenport 引理
对于$$\bmod p \ (p \text{是素数})$$意义下的两个非空集合$$A, B$$
它们所有可能的两两之和$$A + B$$，其大小满足
```math
\displaystyle
|A + B| \geqslant \min(p, |A| + |B| - 1)
```
**情形一**
如果$$|A + B|$$定义为模$$p$$意义下，那么$$|A + B|$$撑死了就是填满$$\\{0, 1, \cdots, p - 1\\}$$
从而$$|A + B| \leqslant p$$

进一步的，如果有$$|A| + |B| > p$$，根据鸽笼原理，此时我们有$$|A| + |B| = p$$
![](/media/content_img/EGZ-01.png)

**情形二**
怎么样让$$|A + B|$$尽可能小，那就是令$$A, B$$尽可能重叠
```math
\displaystyle
A = \{0, 1, 2, \cdots, |A|- 1\} \\
B = \{0, 1, 2, \cdots, |B| - 1\}
```
这个时候$$A + B$$取遍$$\\{0, 1, 2, \cdots, |A| + |B| - 2\\}$$的所有数
所以下界一定是$$\geqslant |A| + |B| - 1$$

**多项式证明**
假设$$|A + B| \leqslant |A| + |B| - 2$$
那就意味着，我们可以补上剩余的数，补到集合的大小是$$|A| + |B| - 2$$为止
这样的集合我们将其称为$$C$$，其中$$c \in C$$，并且所有的$$a \in A, b \in B$$，一定有$$a + b \in C$$

构造多项式，$$f(x, y) = \prod\_{c \in C} (x + y - c)$$，其中$$|C| = |A| + |B| - 2$$
这个多项式只在$$A, B$$上取值，存在
```math
\displaystyle
P_A(x) = \prod_{a \in A} (x - a) = 0 \ (\text{最高次为} x^{|A|}) \\
P_B(y) = \prod_{b \in B} (y - b) = 0 \ (\text{最高次为} x^{|B|})
```
针对我们构造的多项式
```math
\displaystyle
f(x, y) = \prod_{c \in C} (x + y - c)
```
因为$$c$$取遍了$$|A| + |B| - 2$$所有可能的值，所以对于任意一个$$x + y$$
都能在$$c \in C$$找到一个$$c$$满足$$x + y = c$$，换句话说，$$f(x, y) \equiv 0$$

然后我们考虑多项式展开
```math
\displaystyle
f(x, y) = Q_1(x, y) \prod_{a \in A} (x - a) + Q_2(x, y) \prod_{b \in B} (y - b) + R(x, y)
```
注意到，$$\prod\_{a \in A} (x - a)$$已经包揽了所有$$x^{|A|}$$的项
同时$$\prod\_{b \in B} (y - b)$$已经包揽了所有$$y^{|B|}$$的项

上面的两项都是`0`，那么余下的多项式$$R(x, y) = 0$$，并且它关于$$x, y$$的最高次项分别是$$x^{|A|-1}, y^{|B| - 1}$$

而关于$$x^{|A|-1} y^{|B|-1}$$的项只能从$$R(x, y)$$中构造，又因为$$R(x, y)$$是**全`0`多项式**
从而$$x^{|A|-1}y^{|B|-1}$$的系数是`0`

那么它的系数具体是多少呢？考虑$$f(x, y) = \prod\_{c \in C} (x + y - c)$$的展开
一共有$$|A| + |B| - 2$$项，$$x, y$$的最高次幂，从$$(x + y)^{|A| + |B| - 2}$$中构造

那么系数是$$coef = \displaystyle \binom{|A| + |B| - 2}{|A| - 1}$$

因为$$|A| + |B| - 1 \leqslant p$$，那么一定有$$|A| + |B| - 2 < p$$，从而`coef`在模`p`意义下绝不可能是`0`

矛盾，从而$$|A + B| \geqslant |A| + |B| - 1$$

## EGZ 定理
对于任意$$2m-1$$个整数，必然可以从中选出恰好$$m$$个数，使得它们的和是$$m$$的倍数
### 简单情况
先看$$m = p$$（素数）时候的情况
假设我们有$$2p-1$$个数，将它们从小到大排序（在模$$p$$意义下同余的归在一类）
```math
\displaystyle
a_1 \leqslant a_2 \leqslant \cdots \leqslant a_{2p-1}
```
1）如果存在某个$$i \leqslant p$$，使得$$a\_i \equiv a\_{i+p-1} (\bmod p)$$
因为已经按照$$\bmod p$$排序了，所以$$a[i \sim i+p-1]$$这连续的`p`个数在$$\bmod p$$意义下是完全相同的

所以这些数的和$$\equiv p \cdot a_i \equiv 0(\bmod p)$$，直接得证

2）对于所有的$$1 \leqslant i \leqslant p - 1$$，如果都有$$a\_i \not \equiv a\_{i+p-1} (\bmod p)$$
那么取集合
```math
\displaystyle
A_1 = \{a_1, a_p\} \\
A_2 = \{a_2, a_{p+1}\} \\
\cdots \\
A_{p-1} = \{a_{p-1}, a_{2p-2}\}
```

因为$$a\_i \not \equiv a\_{i+p-1} (\bmod p)$$，所以每个集合中都有`2`个模$$p$$不同的元素
从而$$|A\_i| = 2$$

那么根据柯西-达文波特定理，这$$p-1$$个集合的和集合
```math
\displaystyle
S = A_1 + A_2 + \cdots + A_{p-1} \\
|S| \geqslant \min(p, |A_1| + (|A_2| - 1) + (|A_3| - 1) + \cdots + (|A_{p-1}| - 1) ) \\
= \min(\ p, \ 1 + (|A_1| - 1) + \cdots +  (|A_{p-1}| - 1)\ ) = \min(p, 1 + (p-1)(2 - 1)) = p
```
和集的大小等于$$p$$，说明什么？说明在$$\bmod p$$意义下
它覆盖了$$\\{0, 1, \cdots, p-1\\}$$的所有数，不管你想凑出**和模`p`等于几**的数

只要从构造的$$A\_1, A\_2 \cdots, A\_{p-1}$$这$$p-1$$个集合里挑，挑一个数加起来
总是能凑出来的

最后我们有一个孤零零的$$a\_{2p-1}$$还没有用
那么我们在挑出一种方案，凑出$$-a\_{2p-1}$$即可保证$$\bmod p \equiv 0$$

### 归纳证明
用数学归纳法，证明定理如果对$$a, b$$成立，那么对$$a \times b$$也成立
现在我们有$$2ab - 1$$个数

1）因为$$2ab - 1 \geqslant 2a - 1$$，那么我们一定可以从中挑出$$a$$个数，使得它的和是$$a$$的倍数
把挑出来的数打包成第一组，然后从原序列中删去

2）还剩下$$2ab - 1 - a$$个数，如果仍然满足$$\geqslant 2a - 1$$，继续打包，继续删

3）能打包多少组呢？假设说我们已经打包了$$2b - 2$$组
那么还剩下$$2ab - 1 - (2b - 2)a = 2a - 1$$，恰好满足$$\geqslant 2a - 1$$的限制
也就是说，恰好我们能够打包$$2b - 1$$组，每组$$a$$个数，他们的和都是$$a$$的倍数（归纳假设）

假设这$$2b - 1$$组的和分别是$$S\_1, S\_2, \cdots S\_{2b - 1}$$

那么$$S\_i = a \cdot k\_i$$，只看系数，我们有$$k\_1, k\_2, \cdots, k\_{2b - 1}$$
必然能挑出$$b$$个数，使得他们的和是$$b$$的倍数，不放设他们的和是$$bm$$

那么总的数字个数是`(b 组) * (a 个 / 组) = ab`个数，和是$$a \sum k_i = a(b \cdot m) = ab \cdot m$$
这就证明了结论

看完文章有啥想法

算法小站

wiki 主题

算法基础

EGZ定理

目录