排列有偶数种.
?a1,a2,a3,a4?，其中 (20)、解：当M?{1,2,?,8}时，设其友谊排列为???b1,b2,b3,b4?ak?bk?k,k?1,2,3,4，则?ak??bk??k?10，
k?1k?1k?1444所以
?a??bkk?1k?144k?2?bk?10，即
k?141?2???8?2(b1?b2?b3?b4)?10，所以b1?b2?b3?b4?13 ??①
显然有 1?B而8?A，于是由①得，B?{b1,b2,b3,b4}只有三种情况：
B?{1,2,3,7},{1,2,4,6},{1,3,4,5}．
1,2,3,7}，则A?{4,5,6,8}，由于1?ai?bi?4，于是A中的元素8只能(10)、若B?{与B中的元素7搭配，而A中的元素6只能与B中的元素2或3搭配，因此只有两种排列：
?8,4,6,5??8,5,4,6?T1???， T2??7,3,1,2?；
7,2,3,1????1,2,4,6}(20)、若B?{配，也只有两种排列：
3,5,7,8}，则A?{，A中的元素7,8只能与B中的元素4或6搭
?3,8,7,5??7,3,5?,8； T3???， T4??6,1,2?2,6,4,1,????4(30)、若B?{1,3,4,5}，则A?{2,6,7,8}，A中的元素2只能与B中的元素1搭配，
8只能与4或5搭配，只有两种排列：
,7?2,7,6,8??2,6,8?， ； T5??T?6??1,4,5?1,5,3,4,????3因此，当M?{1,2,?,8}时，总共有6种友谊排列．
当M?{1,2,?,10}时，用类似的方法可得，此时共有10种友谊排列：
?4,10,9,5,7??9,5,4,10,7??10,7,4,6,8??10,4,8,7,6?T1???,T2??8,3,1,6,2?,T3??9,5,1,2,3?,T4??9,2,5,3,1?；
3,8,6,1,2?????????9,3,7,6,10??3,10,7,9,6??2,6,10,9,8??2,9,6,8,10? T5??,T?,T?,T?678????????8,1,4,2,5??2,8,4,5,1??1,4,7,5,3??1,7,3,4,5??8,3,5,10,9??3,8,10,5,9?． T9??,T?10????7,1,2,6,4??2,6,7,1,4?例15、12个赌徒每日聚赌一次，每次4人一桌，共设三桌；若其中任两人都至少同桌一次，问赌博至少持续了多少天？
解：至少持续了五天.
先说明，5天已够.记12个人为1,2,?,12，将其两两搭配，记
a??1,2?，b??3,4?, c??5,6?, d??7,8?, e??9,10?, f??11,12?.先作模式搭配，
安排如下：（一） ab cd ef ； （二） ac be df ； （三） ad bf ce； （四） ae bd cf ； （五） af bc de. 即： （一） ?1,2,3,4? ?5,6,7,8? ?9,10,11,12?； （二） ?1,2,5,6? ?3,4,9,10? ?7,8,11,12?； （三） ?1,2,7,8? ?3,4,11,12? ?5,6,9,10?； （四） ?1,2,9,10? ?3,4,7,8? ?5,6,11,12?； （五） ?1,2,11,12? ?3,4,5,6? ?7,8,9,10?。
其次说明至少需要五天，改记这12人为 A任取一人A他要与其他11人1,A2,?,A12，1，中的每个人分别同桌，每次同桌都有另外三人作陪，这样至少需要4天，但是11人不能等分成四个“三人组”，于是必有一人，例如A2，至少两次与A1同桌，设这两次为：
A1A2A3A4 , A1A2AA5. 6若只安排四天，在后续的两天中，其余6人 A7,A8,?,A12，分
别要与A为使A需将6人等分成两组，每组3人，1,A2同桌；1在这两天中能与这6人都同桌，设这两天A1A7A8A9与A1A10A11A12，为使A2在这两天中也能与这6人都同1所在的桌为：A12个赌徒每天都必需出场一桌，则这两天A2所在的桌为：A2A10A11A12与A2A7A8A9；由于
次，于是在这两天中，第三桌的人都是A3A4A5A6；但是A7,A8,?,A12中至多有三人在第二天与A3同桌，因此在这四天中，A7,A8,?,A12中至少有三人与A3仍不能同桌，矛盾！因此至少需要五天.
例16、试求最小的正整数n，使得对于满足条件
?ai?1ni?2009的任一具有n项的正整
数数列a1,a2,?,an， 其中必有连续的若干项之和等于30．
解：首先，我们可以构造一个具有1019项的整数数列a1,a2,?,a1017，使其中不存在和为30的连续项；为此，取 a1?a2???a29?1, a30?31，以及
a30m?i?ai , i??1,2,?,30?, m?N，即 ?ak?为：
1,1,?,1,31,1,1,?,1,31,??1,1,?,1,31,1,1,?,1, （共有34段，前33段中每段各有30个项，最后一段有29个项，共计1019个项），其次，当项数少于1019时，只须将某些
段中连续的若干个数合并成较大的数即可．
1020对于满足条件
?ai?1i我们来?2009的任一个具有1020项的正整数数列a1,a2,?,a1020，
k证明，其中必有连续的若干项之和等于30.为此，记Sk??a, k?1,2,?,1020，则
ii?11?S1?S2???S1020?2009．今考虑两组数：
A组；S1,S2,S3,??,S1020；
B组；S1?30,S2?30,S3?30,?,S1020?30．
两组共有2040个正整数，最大数S1020?30?2039，故其中必有两数相等，但A组中的任两数不相等，B组中的任两数也不相等，因此必定有A组中的某数等于B组中的某个数， 设Sm?Sk?30，则Sm?Sk?30，
即ak?1?ak?2???am?30.因此n的最小值为1020. 例17、对于正整数n，证明：
?2CCkknk?0n?n?k??2???n?kn（单身汉引理） ?C2n?1．
证：采用组合模型法，设想某社区共有n?1户人家，其中有n户夫妻家庭和一户单身汉
n家庭，共计2n?1人，今从中任选n人参加一项活动，则共有C2n?1种选择方案．
另一方面，该事件也可作如下分类：对任一数k，0?k?n，n户夫妻家庭中恰有k户家庭各派出了一人，其余n?k户夫妻家庭皆为两人同去，显然，当n?k为奇数时，单身汉必须参加；而当n?k为偶数时，则单身汉肯定不能参加．
k从n对夫妻中选取k对，有Cn种方法，再从选出的k对中各派出一人，有2种派法，
k?2??n?k???n?k剩下n?k人中，共含有?对夫妻，他们来自剩下的个家庭，选法种数为， Cn?k??2?n?n?k??2???n?kn?n?k??2???n?k?n?k?因此按这种分类，得选法种数
?2CCkknk?0，所以，
?2CCkknk?0n?C2n?1．
例18、集合组?由11个五元集A1,A2,?,A11组成，其中任意两个集合的交都不是空集，令A??A??x,x,?,x?，?x?A，?中含有元素x的集合数目为k，记
i12n11iiii?1m?max?k1,k2,?,kn?，求m的最小值．
解：易得
?ki?1ni?55 ?? ①
这一事实利用“算两次”原理可立即得到：作一张n?11的表，若xi?Aj，则在表中第i行、j列的交叉处填写一个“*”号；
A1 * ? * A2 * ? * A3 * ? ? ? ? A10 * ? A11 * ? * x1 x2 ? xn
于是若按行计算，第i行共有ki个“*”号，全表共有
?ki?1nni个“*”号，再按列计算，由
于每列恰有5个“*”号，全表的“*”号数是55个，因此
?ki?1i?55．
含有xi的ki个集合，共作成Cki?集，故和式
2ki(ki?1)个“集合对”，由于任两个集合的交不是空2?Ci?1n2ki包含了所有的“集合对”，其中含有重复（因为有些集合对可能不止一个
公共元，有些元素可能属于多个集合）．
2据条件，集合组?中的11个集A1,A2,?,A11两两的交不空，它们构成C11?55个不重
nn复的“集合对”，因此
?Ci?12ki?55，即 ?ki(ki?1)?110 ? ②，
i?1据maxki?m，则由②，110??k(k?1)??k(m?1)?55(m?1)，所以m?3．
iiii?1i?1nn再证m?3，反证法，若有m?maxki?3，即对任何i，皆有ki?3，这时将会导致所有ki?3；事实上，若有某个ki?2，即含有元素xi的集合不多于2个，于是集合组?中至少有9个集不含xi，设不含xi的集合是A1,A2,?,A9，而A10含xi，记A10??xi,a,b,c,d?，由于A10?Ai??，则A10?Ai??a,b,c,d?，i?1,2,?,9，因此a,b,c,d四个元素中，必有一个元素，例如a，要属于?中至少三个集合，即属于A1,A2,?,A9,A10中至少四个集合，这与maxki?3矛盾！于是所有ki?3；但这又导致55?所以m?3，即m?4．
再说明，m?4是可以取到的，为此，采用几何构造法，
考虑如图的五角星，它的10个结点以及各边中点，共得15个点，分别标志为1,2,?,15，今构造集合由五角星的外A??1,2,?,15?的11个五元集如下：接圆上5个点，五条边上的各5个点，
五个形如(1,4,8,6,11)的“十字架”上的5个点，
?ki?1ni?3n，矛盾！
111276891015431521314分别作为一个集，这样共得11个集，它们分别是：?11,12,13,14,15?，
?1,2,3,13,15?,?3,4,5,11,14?,?5,6,7,12,15?,?7,8,9,11,13?,?9,10,1,12,14?， ?1,4,8,6,11?,?3,6,10,8,12?,?5,2,8,10,13?,?7,4,10,2,14?,?9,2,6,4,15?，
因此，m的最小值为4．（注意，也可将集合?11,12,13,14,15?换成集合?1,3,5,7,9?，同样可以确保任两个集的交不空．）
例19、某选区有1000个选民，分别持有编号为000,001,002,?,999的选票，选区共设有100个投票站，编号分别是00,01,02,?,99．选区制定了一条法律：规定选民z如果要