第十八章 组合一、方法与例题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，从而表中所有数的总和不小于(n-k)2+k2≥3.不变量原理。俗话说，变化的是现象，不变的是本质，某一事情反复地进行，寻找不变量是一种策略。例 3 设正整数 n 是奇数，在黑板上写下数 1，2，…，2n，然后取其中任意两个数 a,b,擦去这两个数，并写上|a-b|。证明：最后留下的是一个奇数。[证明] 设 S 是黑板上所有数的和，开始时和数是 S=1+2+…+2n=n(2n+1)，这是一个奇数，因为|a-b|与 a+b 有相同的奇偶性，故整个变化过程中 S 的奇偶性不变，故最后结果为奇数。例 4 数 a1, a2,…,an中每一个是 1 或-1，并且有...
