Question

证明：任给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