集合与组合讲稿
陶平生（2013镇江）
基本内容与方法：集合的结构问题，计数问题，构造问题；分类与染色法、映射与对应、容斥原理，补集与补形，归纳与递推；算两次原理， 极端原理，构造法，模型法
例1、集合A是集合M??1,2,3,?,2012?的20元子集，且A中的任两个元素之差为
12的倍数，求这种子集A的个数．
解：对于x,y?M，若1则称x,y是同类的，于是当n??1,2,3,4,5,6,7,8?时， 2(x?)y，
n的同类数有168个，对于其中每个n，168元集合Tn=?xx?n?12k,k?0,1,2,?,167?20的任一个20元子集皆合条件，共得8?C168个子集；当n??9,10,11,12?时，n的同类数有167个，对于其中每个n，167元集合Tn=xx?n?12k,k?0,1,2,?,166的任一个20元子
202020集也合条件，共得4?C167个子集；因此所求集合个数为8?C168． ?4?C167??例2、试确定，有多少种不同的方法将集合M??1,2,3,4,5?中的元素归入A,B,C三个（有序）集合，使得满足：每个元素至少含于其中一个集合之中，这三个集合的交是空集，而其中任两个集合的交都不是空集？
（即A?B?C??，而A?B??,B?C??,C?A??） （2012，南昌市、山西预赛）
解：如图考虑Wenn图所分成的七个部分，分别用x,u.v,w,a,b,c， 表示，现将M的元素填入各个部分中，据题意知，x处不能填数，而u,v,w处必须填有数字，且所填元素互不相同（否则相同元素将归入；a,b,c处可以填写或不填数字，不同的块中不再填有相同x区域中）
元素，（否则又将归入u,v,w中）．今用u表示u处所填数字的个数，
余类推．据对称性，不妨按u?v?w情况列举，则有四种情况：(1)、(u,v,w)?(1,1,1)；
BAauxwvcbC(2)、(u,v,w)?(1,1,2)；(3)、(u,v,w)?(1,2,2)；(4)、(u,v,w)?(1,1,3)．
对于(1)、从M中各取一数分别置于u,v,w格，有方法5?4?3?60种，剩下两数各随意放入a,b,c格，方法数为3，于是得，对应于(1)的情况有60?9?540种；
对于(2)、u,v,w中，含两个数的格有3种情况，对于其中任一情况，M中取两数放入一
211格，另外两格各放一数，有C5C3C2?60种，剩下一数放于a,b,c格之一，放法数为3，
2于是得，对应于(2)的情况有3?60?3?540种；
对于(3)、u,v,w中，含一个数的格有3种情况，对于其中任一情况，M中取一数放入一格，
12另外取两数放于一格，剩下两数放于另一格，有C5C4?30种，共得3?30?90种情况；
对于(4)、u,v,w中，含三个数的格有3种情况，对于其中任一情况，M中取3个数放入一
31格，另外的两格各放一个数，有C5C2?20种，共得3?20?60种情况；
合并得，总情况有540?540?90?60?1230种，每种情况都获得满足条件的三个集合
A,B,C，这样，本题答案为1230．
例3、以任意方式，将M?{1,2,?,9}分拆成A,B两个子集，证明：其中必有一个集，含有成等差数列的三个数．
证：反证法，若有某一分法，使得A,B两个子集之中任一个都不含等差的三数，为此，考查3,5,7三数，由于这三数成等差，故不能属于同一个集，必有一个集含有其中两数，设为A，集B含有另一数；若3,5?A，则1,4,7?B，矛盾！若5,7?A，则3,6,9?B，矛盾！若3,7?A,5?B，则(1,9),(2,8),(4,6)中，每一对数至少有一数属于A，这样得到A的八种情况：(1,2,4,3,7),(1,2,6,3,7),(1,8,4,3,7),(1,8,6,3,7)，
(9,2,4,3,7),(9,2,6,3,7),(9,8,4,3,7),(9,8,6,3,7)
每一情况中都有成等差的三数，矛盾！
例4、设M为n元集，若M有k个不同的子集A1,A2,?,Ak，满足：对于每个
i,j??1,2,?,k?，Ai?Aj??，求正整数k的最大值．
解：正整数k的最大值为2n?1．
?1?、先证明，存在M的20
n?1个子集，两两之交不空；
n?1设M??a1,a2,?,an?，而A为集合?a1,a2,?,an?1?的全部21,A2,?,A2n?1个子集，令
Bi?Ai??an?,i?1,2,?,2n?1，则M的2n?1个子集B1,B2,?,B2n?1，两两之交不空；
?2?、再证，对于M的任何20n?1?1个子集，其中必有两个子集不相交．
设B1,B2,?,B2n?1是M的2n?1个不同子集，其中每个皆含an；用Bi表示子集Bi在M中的
补集，(Bi?M\\Bi),i?1,2,?,2n?1，则对于任意i?j，Bi?Bj,Bi?Bj，并且Bi?Bj， （因前者含an而后者不含），故B1,B2,?,B2n?1，B1,B2,?,B2n?1为M的全部2个不同子集，现将上述集合搭配成为2任取M的2n?1n?1n对：B1,B1,B2,B2,?,B2n?1,B2n?1；
???????1个子集，必有两个子集属于同一对，则这两个子集不相交．
例5、将前九个正整数1,2,?,9分成三组，每组三个数，使得每组中的三数之和皆为质数；求出所有不同分法的种数．
0
解：1、由于在1,2,?,9中，三个不同的数之和介于6和24之间，其中的质数有
??7,11,13,17,19,23这六个数，今将这六数按被3除的余数情况分为两类：
A??7,13,19?，其中每个数被3除余1；B??11,17,23?，其中每个数被3除余2；
假若所分成的A,B,C三组数对应的和pa,pb,pc为互异质数，则因
故三个和数pa,pb,pc必为同一类数，因为A类pa?pb?pc?1?2???9?45被3整除，
三数和7?13?19?39?45，B类三数和11?17?23?51?45，矛盾！
故三个和数中必有两个相等．
，只有四?2?、据?1?知，将45表成7,11,13,17,19,23中的三数和（其中有两数相等）
00
种情况：?1?19?19?7；?2?17?17?11；?3?13?13?19；?4?11?11?23．
由于在1,2,?,9中有5个奇数，故分成的三组中必有一组，三数全为奇数，另两组各有一个奇数．
对于情形?1?，和为7的组只有?1,2,4?，剩下六数3,5,6,7,8,9，分为和为19的两组，且其中一组全为奇数，只有唯一的分法：?3,7,9?与?5,6,8?；
对于情形?2?，若三奇数的组为?1,7,9?，则另两组为 ?4,5,8?,?2,3,6?；或
?3,6,8?,?2,4,5?；
若三奇数的组为?3,5,9?，则另两组为 ?2,8,7?,?1,4,6?，或?4,6,7?,?1,2,8?； 若三奇数的组为?1,3,7?，则另两组为 ?2,6,9?,?4,5,8?；共得分法5种；
对于情形?3?，若三奇数的组为?3,7,9?，则另两组为 ?1,4,8?,?2,5,6?；
若三奇数的组为?1,3,9?，则另两组为 ?2,4,7?,?5,6,8?或?2,5,6?,?4,7,8?； 若三奇数的组为?1,5,7?，则另两组为 ?3,4,6?,?2,8,9?或?2,3,8?,?4,6,9?； 共得分法5种；
对于情形?4?，和为23的组只有?6,8,9?，则另两组为 ?1,3,7?,?2,4,5?； 据以上，共计得到1?5?5?1?12种分法．
例6、将数集A?{a1,a2,...,an}中所有元素的算术平均值记为P(A)， （其中P(A)?a1?a2?...?an）. 若B是A的非空子集，且P(B)?P(A)，则称B是A
n的一个“均衡子集”．
试求数集M?{1,2,3,4,5,6,7,8,9}的所有“均衡子集”的个数． 解：由于P?M??5，令M???x?5x?M?,?3,?2,?1,0,1?,，2,则3,4?4??P?M???0, 依照此平移关系，M和M?的均衡子集可一一对应．
用f(k)表示M?的k元均衡子集的个数，显然有f(9)?f(1)?1(M?的9元均衡子集只有
M?，一元均衡子集只有?0?)．
M?的二元均衡子集共四个，为Bi?{?i,i},i?1,2,3,4, 因此f(2)?4． M?的三元均衡子集有两种情况：
（1）含有元素0的为Bi?{0}?{?i,0,i},i?1,2,3,4, 共四个；
（2）不含元素0的，由于等式3?1?2,4?1?3可表示为?3?1?2?0,3?1?2?0以及
?4?1?3?0,4?1?3?0，得到4个均衡子集
{?3,1,2},{3,?1,?2},{?4,1,3},{4,?1,?3}，因此f(3)?4?4?8．
M?的四元均衡子集有三种情况：
（1）每两个二元均衡子集之并：Bi?Bj,1?i?j?4, 共6个集； （2）不含元素0的三元均衡子集与?0?的并集，共4个集；
（3）以上两种情况之外者，由于等式1?4?2?3可表为?1?4?2?3?0以及
1?4?2?3?得02个均衡子集{?1,?4,2,3}与{1,4,?2,?3}，因此f?4??6?4?2?12．
又注意到，除M?本身外，若B?是M?的均衡子集，当且仅当其补集CM'B'也是M?的
均衡子集，二者一一对应. 因此f(9?k)?f(k),k?1,2,3,4．
从而M?的均衡子集个数为
?f(k)?f(9)?2?f(k)?1?2(1?4?8?12)?51．即M的均衡子集有51个．
k?1k?194例7、某校有1200名新生，每人至少认识其中n人，试求n的最小值，使得其中必存在彼此认识的9个人.
解：记这1200个人的集合为M??v1,v2,?,v1200?，vi所认识的人的集合记为
Ai, i?1,2,?,1200，则Ai?n，且vi?Ai i?1,2,?,1200，
若v1,v2是M中相识的两人，则有A1?A2?A1?A2?A?B?2n?1200， 当2n?1200?1，则有v3?A1?A2，且v1,v2,v3两两相识，而
A1?A2?A3?A1?A2?A3??A1?A2??A3?3n?2?1200.
当3n?2?1200?1，则有v4?A1?A2?A3，且v1,v2,v3,v4两两相识，而
A1?A2?A3?A4?A1?A2?A3?A4??A1?A2?A3??A4?4n?3?1200，如此继续，
?7?得v1,v2,?,v8两两相识，而?Ai??Ai?A8???Ai??A8?8n?7?1200.
i?1i?1?i?1?当8n?7?1200?1，则有v9?87?A, 且v,v,?,v两两相识,而由
i8129i?18n?7?1200?1，得n?7?1200?1，n为整数，则n?1051. 8再说明n?1051是最小的；若n?1050，我们可构造一种情形，使得M中不存在相互
认识的9个人．为此，将1200个人均分为B1,B2,?,B8等8组，每组150个人，令同组的人互不相识，而异组的任两人皆相识，则M中任一人v所认识的人的个数皆为
d?v??7?150?1050，从M中任取9个人，必有两个人属于这8组中的同一个组，于是这
两人互不相识，因此M中不存在相互认识的9个人.从而n的最小值为1051.
例8、设M??2,12,013?求最小的正整数n，使得对于集合M的任一个n元子集A，?，
其中必有两数之差，或者为12，或者为21．
解：由于12?21?33，先考虑基本集E??1,2,?,33?，我们来证明，从E中取出一个
k元子集B，使得B中任两数之差，既不等于12，也不等于21，则k的最大值是15．