第十八章 组合
一、方法与例题
1．抽屉原理。
例1 设整数n≥4,a1,a2,…,an是区间(0,2n)内n个不同的整数，证明：存在集合{a1,a2,…,an}的一个子集，它的所有元素之和能被2n整除。
[证明] （1）若n {a1,a2,…,an},则n个不同的数属于n-1个集合{1,2n-1}，{2,2n-2},…,{n-1,n+1}。由抽屉原理知其中必存在两个数ai,aj(i≠j)属于同一集合，从而ai+aj=2n被2n整除；
（
2）若n∈{a1,a2,…,an}，不妨设a
n=n，从a
1,a
2,…
,an-1(n-1≥
3)中任意取3个数a
i, a
j, a
k(a
i,
j< ak)，则aj-ai与ak-ai中至少有一个不被n整除，否则ak-ai=(ak-aj)+(aj-ai)≥2n，这与ak∈(0,2n)矛盾，故a1,a2,…,an-1中必有两个数之差不被n整除；不妨设a1与a2之差(a2-a1>0)不被n整除，考虑n个数a1,a2,a1+a2,a1+a2+a3,…,a1+a2+…+an-1。
