Erdos Ginzburg Ziv 定理的一个证明

Erdos Ginzburg Ziv 定理的一个证明

定理描述

给定 \(n\in\mathbb{Z}_+\) ,可以从 \(2n-1\) 个数中选出 \(n\) 个数,其和为 \(n\) 的倍数。

定理证明

第一部分 对n为素数

设\(a_1,\cdots a_{2p-1}\)表示这\(2p-1\)个数。\(k_i,l_i\)表示求和的第 \(i\) 个数的下标,\(k_1<\cdots<k_p,l_1<\cdots<l_t\),\(u_i\)表示\(a_{l_i}\)的次数,\(u_i>0\)。\(v_i\)表示\(a_{k_i}\)的次数,\(v_i\geqslant0\)。

\[\begin{align}S&=\sum_{k_1<\cdots<k_p}{}\left(\sum_{i=1}^p a_{k_i} \right)^{p-1}\\ &=\sum_{k_1<\cdots<k_p}{}\left(\sum_{v_1+\cdots+v_p=p-1\\\qquad {v_i\geqslant0}}{}\binom{p-1}{v_1,\cdots,v_p} \prod_{i=1}^t a_{k_i}^{v_i}\right)\\ &=\sum_{k_1<\cdots<k_p}{}\left(\sum_{t=1}^n\sum_{\{l_1,\cdots,l_t\}\subset\{k_1,\cdots,k_p\}}{}\sum_{u_1+\cdots+u_t=p-1\\\qquad {u_i>0}}{}\binom{p-1}{u_1,\cdots,u_t} \prod_{i=1}^t a_{l_i}^{u_i}\right) \\ &=\sum_{t=1}^{p-1}\sum_{\{l_1,\cdots,l_t\}\subset\{1,\cdots,2p-1\}}{}\left(\sum_{u_1+\cdots+u_t=p-1\\\qquad {u_i>0}}{}\sum_{\{l_1,\cdots,l_t\}\subset\{k_1,\cdots,k_p\}}{}\binom{p-1}{u_1,\cdots,u_t} \prod_{i=1}^t a_{l_i}^{u_i}\right) \\ &=\sum_{t=1}^{p-1}\sum_{\{l_1,\cdots,l_t\}\subset\{1,\cdots,2p-1\}}{}\left(\sum_{u_1+\cdots+u_t=p-1\\\qquad {u_i>0}}{}\binom{2p-1-t}{p-t}\binom{p-1}{u_1,\cdots,u_t} \prod_{i=1}^t a_{l_i}^{u_i}\right)\end{align} \]

又由于\(\displaystyle p|\binom{2p-1-t}{p-t},\forall t\in\{1,\cdots,p-1\}\),所以\(\displaystyle p|S,S\not\equiv\binom{2p-1}{p}(mod\;p)\)。若对任意\(\{k_1,\cdots,k_p\}\subset\{1,\cdots,\displaystyle 2p-1\},\;p\not|\sum_{i=1}^p a_{k_i}\),则\(\displaystyle \left(\sum_{i=1}^p a_{k_i} \right)^{p-1}\equiv1(mod\;p)\),对所有\(\{k_1,\cdots,k_p\}\subset\{1,\cdots,2p-1\}\)求和即知矛盾。


第二部分 对n为合数

若命题不正确,我们取所含素因子总次数最少的数\(n\),设\(n=pq\),其中\(p\)为素数,\(q=\frac{n}{p}\)必满足对任意\(2q-1\)个数存在\(q\)个数,其和为\(q\)的倍数。

于是在\(2pq-1\)个数中,我们每次从其中挑选出\(p\)个数,并从中删去,直到剩下数的个数少于\(2p-1\)。可知挑选出了\(2q-1\)组\(p\)个数和为\(p\)的倍数,于是可从中挑出\(q\)组和为\(pq\)的倍数,这\(q\)组*\(n=pq\)个数,其和为\(n\)的倍数。

上一篇:卷积参数计算


下一篇:LightOJ - 1284 Lights inside 3D Grid