Question

证明：任给2n-1个数，定有n个数和为n的倍数。

证明：任给2n-1个数，定有n个数和为n的倍数。

Answer 1

不难验证，若命题对两个正整数m、n分别成立，则对mn也成立。于是只要验证命题对任意素数p成立。用反证法，假设存在2p-1个数{a[1], ..., a[2p-1]}，使得其中任意p个的和不是p的倍数。

对{1, ..., 2p-1}的任意p元子集I，令
S[I]=∑a[i]，i∈I
根据假设及Fermat小定理，S[I]^(p-1)=1 [mod p]。从而
∑S[I]^(p-1) = C(2p-1, p) [mod p]
容易验证，C(2p-1, p)不是p的倍数。

另一方面，每个S[I]^(p-1)由如下的项组成：
{(p-1)!/(e[1]!*...*e[r]!)}*a[i(1)]^(e[1])*...*a[i(r)]^(e[r])
其中i(1), ..., i(r)∈I，e[1]+...+e[r]=p-1。而每个这样的项会在包含{i(1), ..., i(r)}的p元指标集I所对应的S[I]中各出现一次。对每个固定的{i(1), ..., i(r)}，这样的I共有C(2p-1-r, p-r)个。注意到0<r<p，故
C(2p-1-r, p-r) = (2p-1-r)!/(p-r)!(p-1)!
是p的倍数（分子被p整除，分母则不然）。于是所有项的总和，即∑S[I]^(p-1)，是p的倍数，与前述论断矛盾。