组合问题-A 解答(陶平生)
1、将数集},...,,{21n a a a A =中所有元素的算术平均值记为)(A P ，（n
a a a A P n +++=...)(21）. 若B 是A 的非空子集，且)()(A P B P =，则称B 是A 的一个“均衡子集”．
试求数集}9,8,7,6,5,4,3,2,1{=M 的所有“均衡子集”的个数．
解：由于()5P M =，令{}{}54,3,2,1,0,1,2,3,4M x x M '=-∈=
----，则()0P M '=, 依照此平移关系，M 和M '的均衡子集可一一对应．
用()f k 表示M '的k 元均衡子集的个数，显然有(9)(1)1f f ==(M '的9元均衡子集只有M '，一元均衡子集只有{}0)．
M '的二元均衡子集共四个，为{,},1,2,3,4i B i i i =-=, 因此(2)4f =．
M '的三元均衡子集有两种情况：
（1）含有元素0的为{0}{,0,},1,2,3,4i B i i i =-= , 共四个；
（2）不含元素0的，由于等式312,413=+=+可表示为3120,3120-++=--=以及4130,4130-++=--=，得到4个均衡子集{3,1,2},{3,1,2},{4,1,3},{4,1,3}------，因此(3)448f =+=．
M '的四元均衡子集有三种情况：
（1）每两个二元均衡子集之并：,14i j B B i j ≤<≤ , 共6个集；
（2）不含元素0的三元均衡子集与{}0的并集，共4个集；
（3）以上两种情况之外者，由于等式1423+=+可表为14230--++=以及14230+--=得2个均衡子集{1,4,2,3}--与{1,4,2,3}--，因此()464212f =++=．
又注意到，除M '本身外，若B '是M '的均衡子集，当且仅当其补集''M C B 也是M '的均衡子集，二者一一对应. 因此(9)(),1,2,3,4f k f k k -==．
从而M '的均衡子集个数为94
11()(9)2()12(14812)51k k f k f f k ===+=++++=∑∑．
即M 的均衡子集有51个．
2、若集合{}1,2,,200M = 的子集A 中的每个元素都可表为两个自然数（允许相同）的平方和，求这种集A 中元素个数的最大值.
解：不超过200的平方数是 22220,1,2,,14 .
显然，2221,2,,14 中的每个数2k 可表为22
0k +形式，这种数共有14个；
而2221,2,,10 中的每一对数（允许相同）的和在M 中，这种数有2101055C +=个，
（其中，22x x +形式的数10个，()22 x y x y +≠形式的数210C 个）. 其次，()2211 1,2,,8x x += 形式的数8个；()22
12 1,2,,7x x += 形式的数7个； ()2213 1,2,,5x x += 形式的数5个；()2214 1,2x x +=形式的数2个；共得22个，
再考虑重复情况，利用如下事实：若()2222
, ,, ,x a b y c d a b c d =+=+≠≠则 ()()()()2222
xy ac bd ad bc ac bd ad bc =++-=-++
不超过40且能表为两个不同正整数的平方和的数有 5,10,13,17,20,25,26,29,34,37,40，该组中的每个数与5的积，以及213都在集M 中，且都可用两种方式表为平方和，故各被计算了两次，累计有12次重复（10,13,17,20与10的积已包含在以上乘积组中）；因此，集A 中元素个数的最大值为
1455221279++-=.
3、将前九个正整数1,2,,9 分成三组，每组三个数，使得每组中的三数之和皆为质数；求出所有不同分法的种数．
证：()
01、由于在1,2,,9 中，三个不同的数之和介于6和24之间，其中的质数有7,11,13,17,19,23这六个数，今将这六数按被3除的余数情况分为两类：
{}7,13,19A =，其中每个数被3除余1；{}11,17,23B =，其中每个数被3除余2；
假若所分成的,,A B C 三组数对应的和,,a b c p p p 为互异质数，则因
12945a b c p p p ++=+++= 被3整除，
故三个和数,,a b c p p p 必为同一类数，因为A 类三数和713193945++=<，B 类三数和1117235145++=>，矛盾！
故三个和数中必有两个相等．
()02、据()0
1知，将45表成7,11,13,17,19,23中的三数和（其中有两数相等），只有四
种情况：()119197++；()2171711++；()3131319++；()4111123++．
由于在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；
据以上，共计得到155112+++=种分法．
4、设{}1,2,,17M = ，若有四个互异数,,,a b c d M ∈，使得()mod17a b c d +≡+，就称{},a b 与{},c d 是集M 的一个“平衡对”，求集M 中“平衡对”的个数．
解：将圆周17等分，其分点按顺时针方向顺次记为1217,,,A A A ，则
()mod17m n k l +≡+当且仅当弦m n A A ∥k l A A ．
注意如下事实：圆周17等分点的任一对分点连线都不是直径，因
此全部弦共有17个方向（分别与过i A 的切线平行，1,2,,17i = ）．
与过i A 的切线平行的弦有8条，共形成2828C =个“平行弦对”，若考虑所有17个方向，共得 2817476?=个“平行弦对”．即M 中
有476个平衡对．
5、某校有2009名新生，每人至少认识其中n 人，试求n 的最小值，使得其中必存在彼此认识的8个人.
解：记这2009个人的集合为{}122009,,,M v v v = ，i v 所认识的人的集合记为, 1,2,2009i A i = ，则i A n ≥，且 1,2,2009i i v A i ?= ，
若12,v v 是M 中相识的两人，则有121222009A A A A A B n =+-≥- ，
当220091n -≥，则有312v A A ∈ ，且123,,v v v 两两相识，而
()123123123322009A A A A A A A A A n =+-≥-? .
当3220091n -?≥，则有4123v A A A ∈ ，且1234,,,v v v v 两两相识，而
()123412341234432009A A A A A A A A A A A A n =+-≥-? ，如此继续，
得127,,,v v v 两两相识，而76677111762009i i i i i i A A A A A n ===??=+-≥-? ???
.
当7620091n -?≥，则有781
, i i v A =∈ 且128
,,,v v v 两两相识,而由7620091n -?≥，得6200917
n ?+≥，n 为整数，则1723n ≥. 再说明1723n =是最小的；若1722n =，我们可构造一种情形，使得M 中不存在相互认识的8个人．为此，将2009个人均分为127,,,B B B 等7组，每组287个人，令同组的人互不相识，而异组的任两人皆相识，则M 中任一人v 所认识的人的个数皆为()62871722d v =?=，从M 中任取8个人，必有两个人属于这7组中的同一个组，于是这两人互不相识，因此M 中不存在相互认识的8个人.从而n 的最小值为1723.
6、12个赌徒每日聚赌一次，每次4人一桌，共设三桌；若其中任两人都至少同桌一次，问赌博至少持续了多少天？
解：至少持续了五天.
先说明，5天已够.记12个人为1,2,,12 ，将其两两搭配，记
()1,2a =，()()()()()3,4, 5,6, 7,8, 9,10, 11,12b c d e f =====.先作模式搭配， 安排如下：（一） 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人为 1212,,,A A A ，任取一人1A ，
他要与其他11人中的每个人分别同桌，每次同桌都有另外三人作陪，这样至少需要4天，但是11人不能等分成四个“三人组”，于是必有一人，例如2A ，至少两次与1A 同桌，设这两次为：12341256 , A A A A A A A A . 若只安排四天，在后续的两天中，其余6人 7812,,,A A A ，分别要与12,A A 同桌；为使1A 在这两天中能与这6人都同桌，
需将6人等分成两组，每组3人，设这两天1A 所在的桌为：1789A
A A A 与1101112A A A A ，为使2A 在这两天中也能与这6人都同桌，则这两天2A 所在的桌为：2101112A A A A 与2789A A A A ；由于
12个赌徒每天都必需出场一次，于是在这两天中，第三桌的人都是3456A A A A ；但是7812,,,A A A 中至多有三人在第二天与3A 同桌，因此在这四天中，7812,,,A A A 中至少有三人与3A 仍不能同桌，矛盾！因此至少需要五天.
7、若四元集{,,,}E a b c d =中的四个数,,,a b c d 能够分成和相等的两组,则称E 为“平衡集”.试求集{1,2,,100}M = 的平衡子集的个数.
引理：对于给定的正整数k 与集合{1,2,,}N n = ,用(,)f n k 表示不定方程 x y k += (其中 ; ,x y x y N <∈) ……… ① 的解 (,)x y 的个数，
则有 ()1 1 21(,)1 22 1 20 2 1
k k n k f n k k n n k n k n ?-??≤+?????
??-??=---+≤≤-?????
???>-?当 当 当 ……② 证: 当1k n ≤+时,由x y k <<2x x y k ?<+=12k x -?≤12k x -???≤????
, 而当x 取定后,y 的值便唯一确定,故此时()1,2k f n k -??=?
???.
当221n k n +≤≤-时,如在集N 中添加元素1,2,,1n n k ++- ,则可得12k -??????
个解, 但是下列1k n --个解()()()(),1,1,2,2,,1,(1)x y k k k n k k n =-------
中皆含有添加元,不合条件.
于是此时①的解数为 ()()1,12k f n k k n -??=---????
. 又因集N 中的任两数之和21n ≤-,故当2 1 k n >-时, (),0f n k =.引理证完.
回到本题, 对于集M 中的平衡子集 {,,,}E a b c d =, 如果,,,a b c d 中某两数之和等于另两数之和, 则称E 为A -型集；如果,,,a b c d 中某一数等于另三数之和,则称E 为B -型集.
一、先求A -型集的个数(记为()A ?).
（i ）当101k ≤,其个数为
()101101
1012111100,115111()1()()222f k k k k k k k k A C
A A ???===-?-?????'''==-==++ ???????????∑∑∑∑∑ 为奇数为偶数 k 为奇数时,记21k m =+,则当k 通过集{}5,6,,101 中的奇数时, m 通过集{}2,3,,50 ，
所以 ()()50
1212m m m A ?=-'=∑. k 为偶数时，记22k m =+,则当k 通过集{}5,6,,101 中的偶数时, m 通过集{}2,3,,49 ，
所以 ()()49
1212m m m A ?=-''=∑. 于是()()()()491112504912m A A A m m ???=?'''=+=-+∑()481
12549j j j ==++?∑ 392001225=+40425=.
()11
. 当102199,k ≤≤其个数为 ()()()()199********,102102111101100222f k k k k k A C k k ?==?-??-?????=
=---- ???????????????
∑∑，
令101,k k '=- 则 1100.k k '-=+ k '通过 {}1,2,,98. 于是
()982115049222k k k A k k ?'=''????
????''=-+-+ ???????????????∑k k ''=+∑∑ 为奇数为偶数
()()22A A .??'''+
当k '为奇数时，令21k m '=+. 当k '跑遍{1,2,,98} 中奇数时，m 跑遍{}0,1,,48 ， 所以 48
48
4820011(1)(1)
()(49)(48)222m j j j j j j A m m ?===++'=--==∑∑∑.
当k '为偶数时，令2k m '=. 当k '跑遍{1,2,,98} 中偶数时，m 跑遍{}1,2,,48 ，
48482111(1)
()(50)(49)22m j j j A m m ?==+
''=--=∑∑.
所以，()48
2221
()()()139200j A A A j j ???='''=+=+=∑因A 型集的个数为
12()()()404253920079625A A A ???=+=+=.
二．再求B -型集的个数（记为()B ψ）.
对于100k ≤，不定方程x y z k ++=（其中x y z <<，,,x y z M ∈ …… ③
的解数记为()g k . 显然,当5k ≤时,()0,g k =
且由6123, 7124, 8125134=++=++=++=++, 可知
(6)1, (7)1, (8)2g g g ===.
一般有， 当6k ≥,()(3)22k g k g k ??
--=-???? ……… ④
证明如下：对于k 的全体3元分拆 , k x y z x y z =++<< 将其分作两类：
()1.凡是含1的分拆x y z k ++=，其中1x =,将左边诸元,,x y z 各减1，化为
(1)(1)3y z k -+-=-,即3y z k ''+=-形式，归入引理，即②式中的第一情形， 其解数为(3)1222k k --??
??
=-????????.
()2.凡是不含1的分拆 x y z k ++=，其中1x >，将左边诸元各减1，化为
(1)(1)(1)3,x y z k -+-+-=- 即3x y z k '''++=-形式，其中1x y z '''≤<<， 其解数为(3)g k -.
因此 ()(3)22
k g k g k ??=-+-???? ， 即④成立. 进而有 6(6)(3)2122k k g k g k +????+-+=-=+????????
⑤ 31(3)()2122k k g k g k ++????+-=-=-????????
⑥ ⑤+⑥ 并注意，对任何k N ∈， 有 1,22k k k +????
+=???????? 所以 (6)()g k g k k +=+ ⑦
利用⑦递推得:,(6)()3(1)n N g k n g k kn n n ?∈+=++- ⑧
于是 2(99)(3616)(3)316316(161)316768g g g =+?=+?+??-=?=，
(100)(4616)(4)416316(161)784g g g =+?=+?+??-=.
从而 ()()()()()()1001001581303991006m m n k B g m g m g g g k n ψ=====
==+++∑∑∑∑ ()()15880331552181n k k g k n k n n ===??=+++-????
∑∑∑()1501552433181n n n n ==+++-????∑
()15
201552641815n n n ==+++=∑15163115161616181525736.62
???+?
+?= 故M 中的平衡子集个数为 ()()7962525736105361A B ?ψ+=+=.
8、设集合(){,M m n =│,m n 互质，}2009,02009m n m n +><<≤，求和： (),1m n M mn
s ∈=
∑. 讲解：由于所给的数值2009较大，于是一般化，将2009换成任一不小于2的整数,k 为此取 (){,,k M m n m n =
互质，},0m n k m n k +><<≤，并记 (),1k k m n M s mn ∈=∑，
分析k s 的变化趋势，易知，
2311111,,12213232s s =
==+=???41111,1423342
s =++=??? ， 进而猜想，对于每个2,k ≥都有12k s =. 转而考虑证明，对每个2,k ≥都有10k k s s +-=.
其中 (),1k k m n M s mn ∈=
∑，()1
1,1k k m n M s mn ++∈=∑. 先分解求和区间（和式展布集）：
(){,,k M m n m n =互质，},0m n k m n k +><<≤
{}1,0m n k m n k =+=+<<≤ {}1,0*m n k m n k M M '+>+<<≤= ,
(){1,,k M m n m n +=互质，}1,01m n k m n k +>+<<≤+
{}{}1,011,0*m n k m n k m n k m n k M M ''=+>+<<=++>+<<≤= . 于是 ()()1211111 11k k k M M m k
m s s mn mn m k m k m ++'''≤<-=-=-++-∑∑∑∑ ○1 （右端最后一个和式的求和范围是由于 1,m n k m <=+- 则 12k m +<
）.由于 ()11221111111k k m m m k m k m k m ++<
∑∑ ○2 当 112k m +≤<时，112
k k m k +<+-≤，则 111222
1111k k k m t k m k k m t m +++<<≤<≤==+-∑∑∑. 且由 1m n k +=+ 以及 (),1m n =知，
12k + 不会被,m n 取到. 从而○2式右端可合并为 111m k k m
≤+∑. 据○1,即有 ()()
111011k k m k m k s s m k m k +≤≤-=-=++∑∑. 于是 1212k k s s s -==== ，因此 200912
s s ==.
9、设X 是一个n 元集，它的2n
个子集组成的集簇记为()E X ，而()F X 是()E X 的非空子集簇，并且F 对于并、交、补运算是封闭的（即,,A B F ?∈则,,,A B A B X A X B -- 也都属于F ）.
令k 表示F 中的集的个数，试求k 的取值范围.
解：对于非空的集簇F ，我们定义其中的“素集”如下：如果集簇F 中的一个非空集合A 满足，B F ?∈，则或有A B A = ，或有A B =? ，就称A 是F 中的一个“素集”.
显然，F 中的每个单元素集都是“素集”，若F 中没有单元集，则进而考察其中的2元素集、3元素集、等等. 又若{},F X =?，则X 本身即为F 中的素集.
由于F 中只有有限个集合，故其中的素集也只有有限个，设12,,,m B B B 为
F 中的全部素集，共计m 个，则它们两两不交（否则，如有i j B B B =≠? ，则由,i j B B 的“素性”，可推出i j B B B ==，矛盾.）
再证，1m i i B X == . 即需证，1.m
i
i X B =-=? 事实上，若01m i i X B
B =-= ，而0.B ≠?则一方面，00,,1,2,,i B F B B i m ∈=?= ，
另一方面，由于0B 异于12,,,m B B B ，故0B 不是素集，因此又有某个素集含于它，设0j B B ?，则0,j j B B B =≠? 矛盾，从而1m
i i B X == ．
其次说明，F 中的任一个集，都是若干个素集的并．
C F ?∈，则()11
m m
i i i i C C X C B C B ==??=== ??? ，而由i B 的“素性”，每个 i C B 或为空集或等于i B ，即C 为若干个素集的并．反之，据F 的封闭性，每个这类素集之并也是F 的一个元．
因此，F 中的全体集合（包括空集）的个数是
012,1.m m m m m C C C m n +++=≤≤ 即2.m k =其中1.m n ≤≤
再说明，对于1,2,,n 中的每个m ，2m
都可能被k 取到．
将X 中的n 个元任意拆分成m 组，每组至少一个元，即 12,,m i i j X D D D D D D =≠?=? ，则每个i D 都是素集，令F 为由这些“素
集”生成的簇，这时2m k =．故k 的取值范围是122,2,,2n ．
10、设M 为n 元集，若M 有k 个不同的子集12,,,k A A A ，满足：对于每个{},1,2,,i j k ∈ ，i j A A ≠? ，求正整数k 的最大值．
解：正整数k 的最大值为12n -．
()01、先证明，存在M 的12n -个子集，两两之交不空；
设{}12,,,n M a a a = ，而1122,,,n A A A - 为集合{}121,,,n a a a - 的全部12n -个子集，令
{}1,1,2,,2n i i n B A a i -== ，则M 的12n -个子集1122,,,n B B B - ，两两之交不空；
()02、再证，对于M 的任何121n -+个子集，其中必有两个子集不相交．
设1122,,,n B B B - 是M 的12n -个不同子集，其中每个皆含n a ；用i B 表示子集i B 在M 中的补集，1(\),1,2,,2n i i B M B i -== ，则对于任意i j ≠，,i j i j B B B B ≠≠，并且j i B B ≠， （因前者含n a 而后者不含），故1122,,,n B B B - ，1122,,,n B B B - 为M 的全部2n 个不同子集，现将上述集合搭配成为12
n -对：()()()11122122,,,,,,n n B B B B B B -- ； 任取M 的121n -+个子集，必有两个子集属于同一对，则这两个子集不相交．
11、在一次晚会上，9位舞星共上演n 个“三人舞”节目，若在这些节目中，任二人都曾合作过一次，且仅合作一次，求n 的值.
解：将9个人看成9个点，若两人同组演出过，则相应两点间连一条线段，于是两两 间都要连线，共得36条线段，而每个三人舞对应于一个三角形，每个三角形有三条边， 当所有的边都出现，且不重复使用，共得36123
n ==个三角形，即12个节目，另一方面， 这样的12个三人舞可以安排，例如：
（1，2，3）（4，5，6）（7，8，9）；（1，4，7）（2，5，8）（3，6，9）；
（1，5，9）（2，6，7）（3，4，8）；（1，6，8）（2，4，9）（3，5，7）.
12、如果数集{}12,,,n A a a a = 满足条件：()()1. 3 ; 2. n A ≥中的全体元素可以组成一个等差数列，则称集A 为算术集. 类似地，当集A 的子集B 满足上述条件时，则称B 为A 的算术子集.
试证：对于n 元算术集A ，其算术子集的个数()V n 满足等式：
()()()()()()()2233221V n n T n T T n T n =-+-++-+- .
（其中，()T k 为正整数k 的真因数个数，即小于k 的正因数个数）.
证：不妨设，A 中的元素按顺序组成等差数列，则对于其中任一组数
12,,,r i i i a a a ，
它们组成等差数列的充要条件是其下标12,,,r i i i 也组成等差数列.于是我们只要讨论算术集{}01,2,,A n = 的算术子集的个数.
将0A 中以k 为最大元的算术子集个数记为()(), 3w k k n ≤≤，则
()()()()34v n w w w n =+++ ……○
1，显然有 ()()312w T == ......○2， 今证明，一般地有 ()()()()231w k T T T k =+++- (3)
为此，设B 是任一个以k 为最大元的算术子集，若它有2m +个元，由23m +≥，得1m ≥，若该等差数列的公差为d ，得B 的最小元为()1k m d -+.
因 ()11k m d -+≥，得11k m d -+≤，而m 为整数，则11k m d -??≤-????
，从而对于固定的d ，这种子集的个数就是适合111k m d -??≤≤-????的正整数m 的个数，即11k d -??-????
个.今让d 依次取1,2,3,,1k - ，（实际上，仅当12k d -≤时，11k d -??-????才不为0）.则 ()111111111231k k k k w k k ?-??-??-??-?????????=-+-+-++- ? ? ? ?????????-????????????????
111231k k k k ---??????=+++??????-??????
，同理，当13k -≥时，又有， ()2221232k k k w k k ---??????-=+++??????-??????
，所以， ()()1w k w k --= 12121212233221k k k k k k k k k k ?--??--??--?-??????????????=-+-++-+ ? ? ???????????????---?????????
??????????? …○4 由于 1, 112 0, 1d k k k d d d k ?---?????-=?????-???????
故○4式右端的和数等于集合{}2,3,,1k - 中属于1k -的因数个数，也即等于集合{}1,2,3,,2k - 中属于1k -的因数个数()1T k -，从而
()()()11w k w k T k --=- ……○
5，据○2及○5立即得到
()()()()231, 3 w k T T T k k n =+++-≤≤ ○
6，由○1、○6得 ()()()()()()()2233221V n n T n T T n T n =-+-++-+- .
13、对于2n 元集合{}1,2,,2M n = ，若n 元集{}12,,,n A a a a = ，
{}12,,,n B b b b = 满足：,A B M A B ==? ，
且11n n
k k k k a b ===∑∑，则称A B 是集M 的一个“等和划分”（A B 与B A 算是同一个划分）．
试确定集{}1,2,,12M = 共有多少个“等和划分”．
解一：不妨设12A ∈，由于当集A 确定后，集B 便唯一确定，故只须考虑集A 的个数，设{}126,,,A a a a = ，6a 为最大数，由121278+++= ，则
12639a a a +++= ，612a =，于是 1234527a a a a a ++++=，
故{}112345,,,,A a a a a a =中有奇数个奇数．
()1、若1A 中有5个奇数，因M 中的六个奇数之和为36，而27369=-，则
{}11,3,5,7,11A =，这时得到唯一的{}1,3,5,7,11,12A =；
()2、若1A 中有3个奇数、两个偶数；用p 表示1A 中这两个偶数12,x x 之和；q 表示1A 中这三个奇数123,,y y y 之和，则6,9p q ≥≥，于是21,18q p ≤≤．共得1A 的24种情形．
其中，()
01、当6,21p q ==，则()()12,2,4x x =，()()()123,,1,9,11,3,7,11y y y =， ()5,7,9；可搭配成1A 的3个情形；
()0
2、当8,19p q ==，则()()12,2,6x x =，()()()()123
,,1,7,11,3,5,11,3,7,9y y y =；可搭配成1A 的3个情形；
()0
3、当10,17p q ==，则()()()12,2,8,4,6x x =，()()()123
,,1,5,11,1,7,9y y y =， ()3,5,9，可搭配成1A 的6个情形；
()0
4、当12,15p q ==，则()()()12,2,10,4,8x x =，()()()123
,,1,3,11,1,5,9y y y =，()3,5,7，可搭配成1A 的6个情形；
()0
5、当14,13p q ==，则()()()12,4,10,6,8x x =，()()()123
,,1,3,9,1,5,7y y y =，可
搭配成1A 的4个情形；
()0
6、当16,11p q ==，则()()12,6,10x x =，()()123
,,1,3,7y y y =； 可搭配成1A 的1个情形；
()0
7、当18,9p q ==，则()()12,8,10x x =，()()123
,,1,3,5y y y =； 可搭配成1A 的1个情形．
()3、若1A 中有一个奇数、四个偶数，由于M 中除12外，其余的五个偶数和24681030++++=，从中去掉一个偶数，补加一个奇数，使1A 中五数之和为27，分别得到1A 的4个情形：()()()()7,2,4,6,8,5,2,4,6,10,3,2,4,8,10,1,2,6,8,10．
综合以上三步讨论，可知集A 有124429++=种情形，即M 有29种“等和划分”． 解二：元素交换法，显然
661139i i i i a b ====∑∑，恒设12A ∈； ()01、首先注意极端情况的一个分划：{}{}00
1,2,3,10,11,12,4,5,6,7,8,9A B ==，显然数组{}1,2,3与{}10,11,12中，若有一组数全在A 中，则另一组数必全在A 中； 以下考虑10,11两数至少一个不在A 中的情况，为此，考虑00,A B 中个数相同且和数相等的元素交换：
()0
2、()()()10,15,6,4,7?；()()()10,25,7,4,8?；()()()()10,36,7,5,8,4,9?； ()()10,2,34,5,6?；共得到8个对换；
()0
3、()()()11,15,7,4,8?；()()()()11,26,7,5,8,4,9?；()()()11,36,8,5,9?； ()()11,1,34,5,6?；()()11,2,34,5,7?；共得到9个对换；
()0
4、()()()10,11,16,7,9,5,8,9?；()()10,11,26,8,9?；()()10,11,37,8,9?； ()()()10,11,1,24,5,7,8,4,5,6,9?；()()()10,11,1,34,6,7,8,4,5,7,9?；
()()()()10,11,2,35,6,7,8,4,6,7,9,4,5,8,9?；共得到11个对换．每个对换都得到一个新的划分，因此，本题共得1891129+++=种等和划分．
14、设正整数a 的各位数字全由1和2组成，由其中任意() 2k k ≥个连续数位上的数
字所组成的k 位数，称为数a 的一个“k 段”. 若数a 的任两个“k 段”都不相同，证明：对于具有这种性质的最大正整数a ，其开初的一个“1k -段”和最后的一个“1k -段”必定相同. 证：设12n a x x x = 是一个具有这种性质的最大正整数，由a 的最大性，在其后面无论添加1或2，所得到的1n +位数1121n a x x x = 以及2122n a x x x = 中，都有两个相同的“k 段”. 设在1a 中有 1121i i i k n k n x x x x x ++--+= ；在2a 中有
1122j j j k n k n x x x x x ++--+= . 显然i j ≠，
（因11i k j k x x +-+-≠），且11i n k ≤≤-+， 11j n k ≤≤-+，如果1i =或1j =，则直接去掉相应“k 段”中的末位数，可知结论成立；如果2i ≥且2j ≥，因12212i i i k n k n j j j k x x x x x x x x ++--+++-== ，考虑
各自的前一位数字111, , i j n k x x x ---+，它们只取1和2两个值，其中必有两数相同，于是数a 中有两个相同的“k 段”，矛盾. 因此,i j 中必有一个为1，故结论得证.
15、设3n ≥，问是否能将集合{}1,2,,3M n = 分拆成三个这样的n 元子集123,,A A A ，使得对于每个子集i A ，其中任两个数之和被31n +除得的余数，既不为零，也不等于该集合中的另一个数？
试就 3, 4, 5n =分别讨论上述问题.
解：()
01.3n =时，对于集合{}1,2,,9M = ，存在这种分划, 例如分成 {}{}{}11,2,45,6,73,8,9T = ； {}{}{}21,2,73,4,56,8,9;T =
{}{}{}31,2,46,7,83,5,9;T = {}{}{}41,5,72,3,46,8,9;T =
{}{}{}51,2,43,6,85,7,9;T = {}{}{}61,3,52,4,76,8,9;T =
{}{}{}71,2,53,6,84,7,9;T = {}{}{}81,3,62,4,75,8,9;T =
{}{}{}91,2,64,5,73,8,9;T = {}{}{}101,2,73,5,64,8,9;T =
{}{}{}111,2,63,4,85,7,9;T = {}{}{}121,3,52,6,74,8,9;T =
{}{}{}131,2,64,7,83,5,9;T = {}{}{}141,5,72,3,64,8,9;T =
{}{}{}151,3,54,7,82,6,9;T = {}{}{}161,4,82,3,65,7,9;T =
{}{}{}171,3,56,7,82,4,9;T = {}{}{}181,6,82,3,45,7,9;T =
{}{}{}191,3,64,7,82,5,9;T = {}{}{}201,5,82,3,64,7,9;T =
{}{}{}211,4,82,6,73,5,9;T = {}{}{}221,5,73,4,82,6,9;T =
{}{}{}231,5,73,6,82,4,9;T = {}{}{}241,6,82,4,73,5,9;T =
（它已穷尽所有分法，其中分法21k T -与2k T 对偶; 即，若将一个式子中的每个元素a 换为 10a -，便得另一式.)
()0
2.4n =时，对于集合{}1,2,,12M = ，存在这种分划，例如分成 {}1,2,,12= {}{}{}1,2,4,75,9,10,113,6,8,12 ，
{}1,2,,12= {}{}{}1,5,7,102,3,4,86,9,11,12
（只有这一对分法；若将一个式子中的每个元素a 换为13a -，便得另一式.) ()0
3.5n =时，对于集合{}1,2,,15M = ，不存在这样的分划. 为此，考虑适合条件的所有5元子集，称题中条件为性质P ，若5元子集{}12345,,,,A a a a a a P =∈ ，令16, 1,,5i i b a i =-= ，则{}12345,,,,B b b b b b P =∈， 称这种子集,A B 为“相伴集”，显然，这两种子集,A B 一一对应. 为此，考虑数对 ()11,15,α=()()()()()()2345672,14,3,13,4,12,5,11,6,10,7,9,
αααααα======以及8，由于每对数的和为16，故不能同在一集，记含1的五元子集类为1F ，含
15的五元子集类为1F -，其余五元子集类为0F ，显然，1F 的集与1F -的集一一对应，且1F 的集与1F -的集中都不能含有相邻的数。今求1F 中的所有集合：
为此, 先证明，1F 类中的任一集合不含元素5,7,13. 采用反证：
1F 类中如存在集合A ，使5A ∈，因为14,6,11,12A A ∈??.（这是由于4,6皆与5相邻，且()()1150mod16,1251mod16+≡+≡，以下的同余记号中均省略mod16））,于是另三数将取自()()()2,14,3,13,7,9,8,10，且()2,14与()3,13中的任两数不能共存，这是由于，若取2,因325,1352,+=+≡则3,13皆不能取；若取14,因1453,14113,+≡=+则3,13也不能取。反之，如取3或13，据以上四式知，2与14也不能取。
()1.若三数取自()()3,13,7,9,8,10，若7A ∈，则8,9,10A ?因718+=，790,7101+≡+≡，故7不能取，因此另三数将取自()3,13,8,9,10，显然9A ?，否则不能取8,10，也不能同取3，13，矛盾. 于是A 中的数是()1,3,5,8,10，或()1,5,8,10,13，但前组中有358+=，后组中有5813+=，矛盾。
()2.若三数取自()()2,14,7,9,8,10，同样知7不能取，即另三数在()2,14,8,9,10中选取，进而知9不能取，否则不能取8,10，也不能同取()2,14.于是A 中的数为()1,2,5,8,10或()1,5,8,10,14，而前组中有2810+=，后组中有10148+≡，矛盾。所以5A ?.
1F 类中如存在集合A ，
使7A ∈，因为16,8,9,10A A ∈??，（6,8与7相邻，790,+≡ 7101+≡），因此另三数将取自()()()2,14,3,13,4,12,11，且由 347,+=1273+≡， 1341,13121+≡=+知，()()3,13,4,12中的任两数不能并存，
()1. 若另三数取自()()2,14,3,13,11，则11313142A A A A A ∈???∈???∈，故A 中的数是()1,2,7,11,13，而其中有21113+=，矛盾.
()2. 若另三数取自()()2,14,4,12,11，则11124,A A A ∈???∈而7411+=，矛盾. 因此7.A ?.
1F 类中如存在集合A ，使13A ∈，因为13,4,12,14A A ∈??，（3130,+≡4131+≡，
12113,14113+==+），且据前述，5,7A ?，因此另三数将取自()6,10,2,8,9,11， 若取9，则6,8,10A ?（因8,10与9相邻，而9136+≡），故A 中的数只有1,2,9,11,13，而其中2911+=，矛盾.
故9不取，A 中另三数取自()6,10,2,8,11因21113+=，故2,11不能同取，8必取，且
()6,10中必取一数，若取2,则6,10不能取，
（因628,2810+=+=），矛盾，若取11,因 11138+≡，也得矛盾.故13A ?，从而5,7,13A ?.
所以A 中除1外的另四数取自()()()()2,14,4,12,6,10,8,9,3,11，（括号中的每对数不能同取），若取11，则6,10,12不能取（因10,12与11相邻，6111+≡），余下的数为()2,14，
()()3,4,8,9，每组恰取一数，且3不能取（否则2,4,8,14皆不能取）
，于是得两组解：
()()1,2,4,8,11,1,4,8,11,14；
若不取11，如果取3，则2,4,14不能取（因2,4与3相邻，1431+≡），余下三数从()()6,10,8,9,12中取出，每组恰取一数，得两组解：()1,3,6,8,12,()1,3,8,10,12； 如果11与3都不取，即要从()()()()2,14,4,12,6,10,8,9中取出四数，每组恰取一数，则只有一解：()1,6,9,12,14.
（这是由于，若有8,A ∈ 如果26,10A A ∈??，矛盾；如果
14610412A A A A A ∈???∈???∈，因12141010A +≡??，矛盾。
故8A ?9106A A A ?∈???∈，如果2,A ∈因426,1262+=+≡，则4
,12A ?，矛盾，故214A A ??∈，因1464412A A +≡???∈，故得一解 ()1,6,9,12,14） 由此知，1F 类共有五个集：()11
,2,4,8,11,A =()()231,4,8,11,14,1,3,6,8,12,A A == ()()451,3,8,10,12,1,6,9,12,14A A ==；据相伴性得，1F -类也恰有五个集：()()()12315,14,12,8,5,15,12,8,5,2,15,13,10,8,4B B B ===，
()()4515,13,8,6,4,15,10,7,4,2B B ==.
用k C 表示0F 类集合，考虑集M 的分划：i j k M A B C = ，注意其中,i j A B 中不能同时含有8及任何相同元素，这种搭配只有三种：()()()355355,,,,,A B A B A B ，对于这三种搭配，分别有，(){}1355,9,11,13,14C M A B =-= ，(){}2532,3,5,7,11C M A B =-= ， (){}3553,5,8,11,13C M A B =-= ；显然，1C 中有5914+=，2C 中有235+=，3C 中有358+=，即123,,C C C 都不具有性质P ，因此，不存在合于题意的分划.
15、奥运会排球预选赛有n 支球队参加，其中每两队比赛一场，每场比赛必决出胜负，如果其中有k （3k n ≤≤）支球队12,,,k A A A ，满足：1A 胜2A ，2A 胜3A ，…，1k A -胜k A ，k A 胜1A ，则称这k 支球队组成一个k 阶连环套；
证明：若全部n 支球队组成一个n 阶连环套，则对于每个k （3k n ≤≤）及每支球队i A ()1i n ≤≤，i A 必另外某些球队组成一个k 阶连环套.
证明：以12,,,k A A A 为顶点，如球队i A 胜j A ，则在两点间连一有向边：i j A A →，如此得n 阶竞赛图G ．据条件，G 的n 个顶点可以排成一个n 阶有向圈，设为： 121n A A A A →→→→ ，于是G 的任两点可沿箭头方向相互到达．
先证明，任一球队i A 必在某个三阶连环套中，用,i i S T 分别表示被i A 击败了的球队集合和击败了i A 的所有球队集合，由于G 双向连通，必有,j i k i A S A T ∈∈，使j k A A →，于是,,i j k A A A 组成三阶连环套；
假若已证得，对于()3k k n ≤<，图中存在以i A 为一顶点的k 阶连环套
()121i k C A A A A A = ，圈C 之外的点的集合为M ；
若M 中有一点P ，它所表示的球队既击败了圈C 中的某个队k A ，又被圈C 中的另一个队j A 所击败，点,k j A A 把圈C 分成两条有向路12,C C ，其中一条，
例如1C ，它与有向路j k A P A →→组成有向圈，如图所示．
依次考虑路2C ：12,,,,j j j k A A A A ++ 上各点与点P 间的邻接情况，必有相邻的两点1,j r j r A A +++，满足j r A P +→而1j r P A ++→，今去掉边1j r j r A A +++→，而将路1j r j r A P A +++→→插入其间，便得到一个含有顶点i A 的1k +阶连环套；
若M 中的任一点P ，它所表示的球队要么击败了圈C 中的每个队，要么被圈C 中的每个 队所击败，则集M 可分为两个不交的子集S 与T ，其中S 中的任一队，战胜了圈C 中所有的队，而T 中的任一队，负于圈C 中所有的队；由于图G 双向连通，故在集T 中必有点u ，集S 有点v ，使v u →，今在圈C 中任意去掉一个点j A ，()
j i A A ≠，而用路v u →代替，便得到一个含有顶点i A 的1k +阶连环套；故结论对于1k +成立，由归纳法，结论成立．
16、矩形玻璃台板碎裂成一些小玻璃片，每块碎片都是凸多边形，将其重新粘合成原矩形后，有交结点30个，其中20个点在原矩形的周界上（包括原矩形的四个顶点），其余10点在矩形内部.在矩形的内部有44条粘缝（两个结点之间的线段算是一条粘缝，如图所示）. 试求该矩形台板所碎裂成的每种类型（指三角形、四边形、五边形等等）的碎片块数. （若凸多边形的周界上有n 个点，就将其算作n 边形）.
解：设全部碎片中，共有三角形3a 个，四边形4a 个，
… …，k 边形k a 个（34,,,k a a a 为非负整数）.
一个多边形，若其周界上有n 个顶点，就将其看成是n 边形，
j
（例如图中的多边形ABCDE 要看成五边形）.于是这些多边形的内角和S 角为： S 角()3422k a a a k πππ=?+?++?- .
从另一方面看，矩形内部有10个结点，对于每个点，围绕它的多边形顶角和为2,π 10个内结点共获得102π?弧度；矩形边界线段内共有16个结点，在每个这种结点处，各多边形的顶角在此汇合成一个平角，16个这种结点共获得16π弧度；而原矩形的四个顶点处，共收集到多边形碎片的2π弧度.因此，
S 角2016238ππππ=++=，于是，()342238k a a k a +++-= ……○
1. 再计算边数和S 边：由于每个n 边形有n 条边，则
S 边3434k a a ka =+++ .
另一方面，在矩形的内部的44条粘缝，每条都是两个多边形的公共边，故都计算了两遍，矩形周界上的20条线段各被计算了一遍，因此，S 边24420108=?+=，则
3434108k a a ka +++= ……○
2. ○
2-○1得，()34270k a a a +++= ，因此碎片的块数为: 3435k a a a +++= ……○
3. ○
1—○3得，()4562333k a a a k a ++++-= …… ○4. 注意所有i a 为非负整数，故780k a a a ==== ，456233a a a ++= ……○5. 由○5得，4563, 0a a a ===；或者4561, 0a a a ===；或者4560, 1a a a ===……○6. 因此由○3、○5、○6得，本题的解共有三种情况：
即全部碎片总共有35块；其中，或者含有32个三角形，3个四边形；或者含有33个三角形，1个四边形，1个五边形；或者含有34个三角形，1个六边形.
17、对于周长为n *
()n N ∈的圆，称满足如下条件的最小的正整数n P 为“圆剖分数”
： 如果在圆周上有n P 个点12,,,n p A A A ，对于1,2,,1n - 中的每一个整数m ，都存在
两个点 ,i j A A (1,)n i j P ≤≤，以i j A A 和为端点的一条弧长等于m ；圆周上每相邻两点间的弧长顺次构成的序列12(,,,)n n P T a a a = 称为“圆剖分序列”．例如：当13n =时，圆剖
分数为134P =，如图所示，图中所标数字为相邻两点之间的弧长.