第十八章 组合一、方法与例题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}，不妨设 an=n，从 a1,a2,…,an-1(n-1≥3)中任意取 3 个数 ai, aj, ak(ai,0)不被 n 整除，考虑 n 个数 a1,a2,a1+a2,a1+a2+a3,…,a1+a2+…+an-1
ⅰ）若这 n 个数中有一个被 n 整除，设此数等于 kn，若 k 为偶数，则结论成立；若 k 为奇数，则加上 an=n 知结论成立
ⅱ）若这 n 个数中没有一个被 n 整除，则它们除以 n 的余数只能取 1,2,…,n-1 这 n-1 个值，由抽屉原理知其中必有两个数除以 n 的余数相同，它们之差被 n 整除，而 a2-a1不被 n 整除，故这个差必为 ai, aj, ak-1中若干个数之和，同ⅰ）可知结论成立
2 极端原理
例 2 在 n×n 的方格表的每个小方格内写有一个非负整数，并且在某一行和某一列的交叉点处如果写有 0，那么该行与该列所填的所有数之和不小于 n
证明：表中所有数之和不小于
[证明] 计算各行的和、各列的和，这 2n 个和中必有最小的，不妨设第 m 行的和最小，记和为k，则该行中至少有 n-k 个 0，这 n-k 个 0 所在的各列的和都不小于 n-k，从而这 n-k 列的数的总和不小于(n-k)2，其余各列的数的总和不小于 k2，从而表中所有数的总和
