高二“自主招生、竞赛及高考”讲义一(集合与组合)

1、集合与组合基本内容与方法:集合的结构问题, 计数问题, 构造问题; 分类与染色法、 映射与对应、 容斥原理,补集与补形,归纳与递推;算两次原理, 极端原理,构造法,模型法例 1、集合 A 是集合 1, 2,3, , 2012M = 的 20元子集,且 A 中的任两个元素之差为12的倍数,求这种子集 A 的个数.解:对于 , x y M , 若 12( x y -, 则称 , x y 是同类的, 于是当 1,2,3,4,5,6,7,8n 时,n 的同类数有 168个,对于其中每个 n , 168元集合 =12, 0,1, 2, ,167n T x x n k k =+= 的任一个 20元子集皆合

2、条件, 共得 201688C 个子集; 当 9,10,11,12n 时, n 的同类数有 167个,对于其中每个 n , 167元集合 =12, 0,1, 2, ,166n T x x n k k =+= 的任一个 20元子 集也合条件,共得 201674C 个子集;因此所求集合个数为 202016816784C C +.例 2、试确定,有多少种不同的方法将集合 1, 2,3, 4,5M =中的元素归入 , , A B C 三 个 (有序 集合, 使得满足:每个元素至少含于其中一个集合之中, 这三个集合的交是空集,而其中任两个集合的交都不是空集?(即 A B C = , 而 , , A B B

3、 C C A (2012, 南昌市、 山西预赛解:如图考虑 Wenn 图所分成的七个部分,分别用 , . , , , , x u v w a b c , 表示,现将 M 的元素填入各个部分中,据题意知, x 处不能填数,而 , , u v w 处必须填有数字,且所填元素互不相同(否则相同元素将归入 x 区域中; , , a b c 处可以填写或不填数字, 不同的块中不再填有相同 元素, (否则又将归入 , , u v w 中 .今用 表示 u 处所填数字的个数,余类推.据对称性,不妨按 情况列举,则有四种情况:(1、 (, , (1,1,1=;(2、 (, , (1,1,2=; (3、 (,

4、, (1,2,2=; (4、 (, , (1,1,3=.对于 (1、从 M 中各取一数分别置于 , , u v w 格,有方法 54360=种,剩下两数各随意放 入 , , a b c 格,方法数为 23,于是得,对应于 (1的情况有 609540=种;对于 (2、 , , u v w 中,含两个数的格有 3种情况,对于其中任一情况, M 中取两数放入一 格,另外两格各放一数,有 21153260C C C =种,剩下一数放于 , , a b c 格之一,放法数为 3,c ba v CB A于是得,对应于 (2的情况有 3603540=种;对于 (3、 , , u v w 中, 含一个数的格有

5、 3种情况, 对于其中任一情况, M 中取一数放入一格, 另外取两数放于一格,剩下两数放于另一格,有 125430C C =种,共得 33090=种情况; 对于 (4、 , , u v w 中, 含三个数的格有 3种情况, 对于其中任一情况, M 中取 3个数放入一 格,另外的两格各放一个数,有 315220C C =种,共得 32060=种情况;合并得,总情况有 54054090601230+=种,每种情况都获得满足条件的三个集合, , A B C ,这样,本题答案为 1230.例 3、以任意方式,将 1,2, ,9M = 分拆成 , A B 两个子集,证明:其中必有一个集, 含有成等差数列

6、的三个数.证:反证法,若有某一分法,使得 , A B 两个子集之中任一个都不含等差的三数,为此, 考查 3,5,7三数,由于这三数成等差,故不能属于同一个集,必有一个集含有其中两数,设 为 A ,集 B 含有另一数;若 3,5A ,则 1,4,7B ,矛盾!若 5,7A ,则 3,6,9B ,矛 盾!若 3,7, 5A 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每一

7、情况中都有成等差的三数,矛盾!例 4、 设 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

8、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个不同子 集,现将上述集合搭配成为 12n

9、-对:(11122122, , , , , , n n B B B B B B - ; 任取 M 的 121n -+个子集,必有两个子集属于同一对,则这两个子集不相交.例 5、 将前九个正整数 1,2, ,9 分成三组,每组三个数,使得每组中的三数之和皆为 质数;求出所有不同分法的种数.解:(1、由于在 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 三

10、组数对应的和 , , a b c p p p 为互异质数,则因12945a b c p p p +=+= 被 3整除, 故三个和数 , , a b c p p p 必为同一类数, 因为 A 类三数和 713193945+=,矛盾! 故三个和数中必有两个相等.(02、据 (01知,将 45表成 7,11,13,17,19,23中的三数和(其中有两数相等,只有四 种情况:(119197+; (2171711+; (3131319+; (4111123+.由于在 1,2, ,9 中有 5个奇数, 故分成的三组中必有一组, 三数全为奇数, 另两组各有 一个奇数.对于情形 (1,和为 7的组只有 1,

11、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,

12、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+=种分法.例 6、 将数集 ,., , 21n a a a A =中所有元素的算术平均值记为 (A P , (其中 na a a A P n+=. (21 . 若 B 是 A 的非空子集, 且 ( (A P B P =, 则称 B 是 A的一个“均衡子集” .试求数集 9, 8, 7, 6, 5, 4, 3, 2, 1=M 的所有“均衡子集”的个数. 解 :

13、由 于 (5P M =, 令 54, 3, 2, 1, 0, 1, 2, 3, 4M x x M =-=-, 则 (0P M =, 依照此平移关系, M 和 M 的均衡子集可一一对应.用 ( f k 表示 M 的 k 元均衡子集的个数,显然有 (9(11f f =(M 的 9元均衡子集只有M ,一元均衡子集只有 0 .M 的二元均衡子集共四个,为 , ,1,2,3,4i B i i i =-=, 因此 (24f =. M 的三元均衡子集有两种情况:(1含有元素 0的为 0,0, ,1,2,3,4i B i i i =-= , 共四个;(2不含元素 0的,由于等式 312, 413=+=+可表示

14、为 3120, 3120-+=-=以及4130, 4130-+=-=,得到 4个均衡子集3,1,2,3,1, 2,4,1,3,4,1, 3-,因此 (3448f =+=.M 的四元均衡子集有三种情况:(1每两个二元均衡子集之并:,14i j B B i j ;若 , x y 分别取自相邻的两个 k C , 1k C +,设 33, 33(1 i j x k a y k a =+=+,假若12y x -=,即 33( 12j i a a +-=,得 21i j a a -=,这与 1215, , , a a a 的选择矛盾!若 21y x -=,得 12i j a a -=,也与 1215, ,

15、 , a a a 的选择矛盾;因此 C 中任两数之差既不 等于 12,也不等于 21;而 C 的任何子集当然也具有此性质. 因此最小的 n 值为 916.例 9、 设 1, 2, , 2013M = 是前 2013个正整数组成的集合, 1230, , , A a a a = 是M 的一个 30元子集,若 A 中的元素两两互质,证明 A 中至少有一半元素是质数.证:先证明, A 中 16个元素中必有一个是质数.为此,任取 16个元素,不妨设为1216, , , a a a , 若其 中没 有质 数, 则它 们中 至多 一 个 为 1, 其余 15个 皆 为合 数, 设 1215, , , a a

16、 a 都是合数,则每个数皆可分解成至少两个质因数的乘积,若 i p 是 i a 的最小质315276183092133122421426517298203211232210311972816425131因数,则 i p , 1,2, ,15i = ,由于 A 中的数两两互质,则 1215, , , p p p 互不相同, 而将全体质数自小到大排列,第 15个质数是 47,所以,若 1p 是 1215, , , p p p 中的最大数, 即有 147p ,于是 2211472011a p ,即 1a M ,矛盾 ! 因此 1215, , , a a a 中必有质 数.不妨设 1a 为质数;今从集

17、 A 中去掉 1a ,在剩下的 29个元素中,再次进行同样的讨论,可知其中的 16个 元素中也必有一个是质数,设为 2a ,如此下去,这样的手续可以连续进行 15次,每次都可 从 A 中取到一个新的质数,因此 A 中至少有 15个质数.例 10、 某班共有学生 33人,教师问每个学生,班上还有多少个人与其同名和还有多少 个人与其同姓,结果发现,答案是从 0到 10的所有整数. 证明:该班必有两名学生既同名且同姓.证:如果某个学生回答班上还有 i 个学生与之同名, j 个学生与之同姓,那么该班上采 用他这个名字的学生共有 1i +人,而采用他这个姓氏的学生共有 1j +人;现将班上的学生这样分类

18、:如果一个名字同时被 k 个人采用,则将这 k 个人一齐归入集 合 k A 1,2, ,11k = ;而当一个姓氏同时被 k 个人采用,则将这 k 个人一齐归入集合 k B , 1,2, ,11k = ;(注意:如果姓王的学生和姓李的学生都有 k 个人,那么他们都在 k B 中. 于是,对于每个 k , , k k A B 中的元素个数都是 k 的倍数;每个人恰属于两个集合(按名 字的集和按姓氏的集 ,并且对于每个 k , , k k A B 至少有一个不是空集(因为从 0到 10的所 有整数都有人回答 ; 所以,11111123366kkk k A B=+=.(这是因为, 33人,每人在 A

19、 集系列和 B 集系列各出现一次 .又因为 121166233+= ,这就表明,对于每个 1, 2, ,11k , k A 和 k B 当中 都有一个是空集, 而另一个恰有 k 个元素. (从而相应的集只含有一个 “姓” 或只含一个 “名” . 现对于 11k =,不妨设 11A 非空,而 11B 是空集, 11A 中的这 11个人(即同名字的 11个人 要分布于另外的 10个“姓氏”集合 1210, , , B B B 中,必有两个人在同一个集,于是这两个 人不仅同名,而且同姓.例 11、 求所有的正整数 n ,使得集合 1, 2, , 4M n = 可以分拆成 n 个四元子集:1nk k

20、M M = ,对于每个集合 , , , k k k k k M a b c d =, 1,2, , k n = , 而 , , , k k k k a b c d 四数,其中的一数等于另外三数的算术平均. (2010北大夏季解:不妨设,每个子集中, k d 是 , , k k k a b c 的算术平均, 3k k kk a b c d +=,则有4k k k k k a b c d d +=,所以, 124(414( 1242n n n d d d n +=+= ,因此, 2n .另一方面,当 2n 时,集 M 确有满足条件的划分, 为此,记 2n m =, 1, 2, ,8M m =11m

21、 k k A -= ,其中 81,82, ,88k k kA k k k M M =+= , 81,83,88,84, , , k k k k k M k k k k a b c d =+=, 82,86,87,85, , , kk k k k M k k k k a b c d =+=, 则在 k M 中有 (81 (83 (88 843k k k k +=,而在 k M 中有 (82 (86 (87853k k k k +=.例 12、 在 1,2, ,2012 中取一组数,使得任意两数之和不能被其差整除,最多能取多 少个数? (2012北京大学解:首先,可以取 671个数 1, 4,7,

22、 , 2008, 2011 (或者 2,5,8, , 2009, 2012 , 其中任两数之和不能被 3整除,而其差是 3的倍数;其次,将 M 中的数自小到大按每三数 一段,共分为 671段:1, 2,3, 4,5,6, 7,8,9, , 2008, 2009, 2010, 2011, 2012 ;从中任取 672个数,必有两数 , x y 取自同一段,则 1x y -=或 2,注意 x y -与 x y +同奇偶,于是 (x y x y -+.因此 k 的最大值为 671.(注 :(2008江西预赛填空题 从前 2008个正整数构成的集 1, 2, , 2008M = 中取 出一个 k 元子

23、集 A ,使得 A 中任两数之和不能被这两数之差整除,则 k 的最大值为 . (答案:670. 例 13、如果非负整数 m 及其各位数字之和均为 6的倍数,则称 m 为“六合数” .求小 于 2012的非负整数中“六合数”的个数. (2012东南赛解法一 易知, 一个非负整数为 “六合数” 当且仅当它末位数字是偶数且各位数字之和 是 6的倍数.为方便起见,将 0,1, , 2011M = 中每个数都写成四位数 abcd 的形式(当不足四 位数时,在最高数位前补上若干个数字“ 0” ,使之恰含有四个数字 ,并用 ( f k 表示 M 中 末位数字为 k 的“六合数”的个数,其中 0,2, 4,

24、6, 8k .对 N n ,将满足 x y n +=且 , 0,1, , 9x y 的 (, x y 的组数记为 n p ,显然1,0, 1, , 9; 19,10, 11, ,18; 0, 19.n n n p n n n +=-=先考虑一切小于 2000的“六合数” abck .若 0k =,则当 0a =时, 0, 6, 12, 18b c +=;当 1a =时, 5, 11, 17b c +=,故06121851117(0( ( 161632f p p p p p p p =+=+=.若 2k =,则当 0a =时, 4, 10, 16b c +=;当 1a =时, 3, 9, 15b

25、 c +=,故410163915(2( ( 171835f p p p p p p =+=+=.若 4k =,则当 0a =时, 2, 8, 14b c +=;当 1a =时, 1, 7, 13b c +=,故28141713(4( ( 171633f p p p p p p =+=+=.当 6, 8k =时,与 0, 2k =的情形类似,有(6(032, (8(235f f f f =.因此,小于 2000的“六合数”有 (0(2(4(6(8167f f f f f +=个.再注意 到 2000至 2011中恰好有一个 “六合数” 2004, 所以所求 “六合数” 的个数为 1671168+

26、=.解法二 对非负整数 n ,令 ( S n 为其各位数字之和.先将小于 2000的非负整数中所有 6的倍数(共 334个配成如下 167对:(0,1998, (6,1992, (12,1986, , (996,1002 .对上述每对数 (, x y ,设 12341234, x a a a a y bb b b =(约定当 x 或 y 不足四位数时,在 最高数位前补上若干个数字“ 0” ,使之恰含有四个数字 ,则112233441000( 100( 10( ( 1998a b a b a b a b x y +=+=.因 , x y 为 偶 数 , 故 44, 8a b , 因 此 4416

27、18a b +, 只 能 448a b +=; 又 由331819a b +知,只能 339a b +=;类似得 229a b +=;最后必有 111a b +=.故11223344( ( ( ( ( ( 199827S x S y a b a b a b a b +=+=+=,从而 (, ( S x S y 中有且仅有一个 6的倍数(这是因为 , x y 均被 3整除,所以 ( S x 与 ( S y 均被 3整除 ,故 , x y 有且仅有一个是“六合数” .从而,小于 2000的“六合数”共有 167个,又 2000至 2011中恰好有一个“六合数” 2004,所以所求“六合数”的个数为

28、 1671168+=.例 14、对于由前 2n 个正整数构成的集合 1,2, ,2M n = ,若能将其元素适当划分, 排成两个 n 项的数列:1212(, , , , (, , , n n A a a a B b b b = ,使得, 1,2, , k k a b k k n -= ,则称 M 为一个友谊集,而数列 , A B 称为 M 的一种友谊排列,例如 (3,10,7,9,6A =和(2,8,4,5,1B =便是集合 1,2, ,10M = 的一种友谊排列,或记为 3,10,7,9,62, 8, 4, 5,1; 0(1 、证明:若 1,2, ,2M n = 为一个友谊集,则存在偶数种友

29、谊排列; 0(2 、确定集合 11,2, ,8M = 及 21,2, ,10M = 的全体友谊排列.0(1 、证明:设 1212(, , , , (, , , n n A a a a B b b b = 是 M 的一种友谊排列,即有, 1,2, , k k a b k k n -= ,且 1212, , , , , , , 1,2, ,2n n a a a b b b n =,称数列 A 为甲型 的,而数列 B 为乙型的;作数列:12121212(, , (21, 21, , 21 (, , (21, 21, , 21 n n n n A a a a n b n b n b B b b b n

30、 a n a n a =+-+-+-=+-+-+-则 , 1,2, , k k a b k k n -= ,且 1212, , , , , , , 1,2, ,2n n a a a b b b n = ,因此,数列, A B 也是 M 的一种友谊排列;再证 A A , 事实上, 假若 A A =, 即 , 1, 2, , k k a a k n = , 则由 22221a a n b =+-,得 2221a b n +=+,而 222a b -=,相加得 2223a n =+,矛盾!故甲型数列 A 与甲型数列 A 一一对应; 并且当数列 A 跑遍 M 的所有甲型数列时, 数列 A 也跑遍 M

31、的所有甲型数列 .注意到数列 A 的第二项 2a 与数列 A 的第二项 2a 一奇一偶,现让 A 取遍使其第二项 2a 为奇 数的甲型数列,则 A 取遍使其第二项 2a 为偶数的甲型数列,且二者一一对应,因此 M 的 甲型数列有偶数个;由于当甲型数列确定后,相应的乙型数列便唯一确定,因此 M 的友谊排列有偶数种 .0(2 、解:当 1,2, ,8M = 时,设其友谊排列为 12341234, , , , , , a a a a b b b b ,其中 , 1, 2,3, 4k k a b k k -=,则 44411110k k k k k a b k =-=,所以444111210k kk

32、k k k a bb =+=+,即12341282( 10b b b b +=+ ,所以 123413b b b b += 显然有 1B 而 8A ,于是由得, 1234, , , B b b b b =只有三种情况:1,2,3,7,1,2,4,6,1,3,4,5B =.0(1 、若 1,2,3,7B =,则 4,5,6,8A =,由于 14i i a b -,于是 A 中的元素 8只能与 B 中的元素 7搭配,而 A 中的元素 6只能与 B 中的元素 2或 3搭配,因此只有两种排列:18, 4,6,57, 2,3,1T =, 28,5, 4,67,3,1, 2T =;0(2 、 若 1,2,

33、4,6B =, 则 3,5,7,8A =, A 中的元素 7, 8只能与 B 中的元素 4或 6搭配,也只有两种排列:33,8,7,52,6, 4,1T =, 47, 3, 5, 86, 1, 2, 4T =; 0(3 、若 1,3,4,5B =,则 2,6,7,8A =, A 中的元素 2只能与 B 中的元素 1搭配,8只能与 4或 5搭配,只有两种排列: 52,7,6,81,5, 3, 4T =, 62, 6, 8, 71, 4, 5, 3T =; 因此,当 1,2, ,8M = 时,总共有 6种友谊排列.当 1,2, ,10M = 时,用类似的方法可得,此时共有 10种友谊排列:1234

34、4,10,9,5,79,5, 4,10,710,7, 4,6,810, 4,8,7,6, , , 3, 8, 6,1, 28, 3,1, 6, 29, 5, 1, 2, 39, 2, 5, 3,1T T T T =;56789,3,7,6,103,10,7,9,62,6,10,9,82,9,6,8,10, , , 8,1, 4, 2, 52, 8, 4, 5,11, 4, 7, 5, 31, 7, 3, 4, 5T T T T =9108,3,5,10,93,8,10,5,9, 7,1, 2, 6, 42, 6, 7,1, 4T T =. 例 15、 12个赌徒每日聚赌一次,每次 4人一桌,共

35、设三桌;若其中任两人都至少同桌 一次,问赌博至少持续了多少天?解:至少持续了五天 .先说明, 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

36、,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 ,分别要与

37、 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 仍不能同桌,矛盾!因此 至

38、少需要五天 .例 16、 试求最小的正整数 n , 使得对于满足条件12009nii a=的任一具有 n 项的正整数数列 12, , , n a a a , 其中必有连续的若干项之和等于 30.解:首先, 我们可以构造一个具有 1019项的整数数列 121017, , , a a a , 使其中不存在和 为 30的连续项;为此,取 1229301, 31a a a a = ,以及30 , 1, 2, ,30, m i i a a i m N += ,即 k a 为:1,1, ,1,31, ,1,31, ,1,31, ,1, (共有 34段, 前 33段中每段各有30个项,最后一段有 29个项,

39、共计 1019个项 ,其次,当项数少于 1019时,只须将某些 段中连续的若干个数合并成较大的数即可.对于满足条件102012009ii a=的任一个具有 1020项的正整数数列 121020, , , a a a ,我们来 证明,其中必有连续的若干项之和等于 30. 为此,记 1, 1, 2, ,1020kk i i S a k = ,则 12102012009S S S ,反证法,若有 max 3i m k =,即对任何 i ,皆有 3i k ,这时将会导致所 有 3i k =; 事实上, 若有某个 2i k , 即含有元素 i x 的集合不多于 2个, 于是集合组 中至 少有 9个集不含

40、 i x , 设不含 i x 的集合是 129, , , A A A , 而 10A 含 i x , 记 10, , , , i A x a b c d =, 由于 10i A A ,则 10, , , i A A a b c d , 1,2, ,9i = ,因此 , , , a b c d 四个元素中, 必有一个元素,例如 a ,要属于 中至少三个集合,即属于 12910, , , , A A A A 中至少四个 集合,这与 max 3i k =矛盾!于是所有 3i k =;但这又导致 1553nii kn =,矛盾!所以 3m ,即 4m .再说明, 4m =是可以取到的,为此,采用几何

41、构造法, 考虑如图的五角星,它的 10个结点以及各边中点, 共得 15个点,分别标志为 1,2, ,15 ,今构造集合1, 2, ,15A = 的 11个五元集如下:由五角星的外接圆上 5个点,五条边上的各 5个点,五个形如 (1,4,8,6,11 的“十字架”上的 5个点,分别作为一个集,这样共得 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,1

42、4, 9, 2, 6, 4,15,因此, m 的最小值为 4. (注意,也可将集合 11,12,13,14,15换成集合 1,3,5,7,9, 同样可以确保任两个集的交不空. 例 19、某选区有 1000个选民,分别持有编号为 000,001,002, ,999 的选票,选区共设1215有 100 个投票站，编号分别是 00,01,02,L,99 选区制定了一条法律：规定选民 z 如果要 将选票投到票站 A ，只有当该选民所持有的选票号码中，若去掉其中某一数码后，剩下的 两位数恰好就是该票站的号码时方可进行， （例如，持 135 号票的选民，只能到 13,15,35 号 票站之一去投票） ；

43、问，在这一法规下，该选区最多可以关闭多少个投票站，使得剩下的投票站还能确保 选举照常进行？ 解：先考察其中一个选民，例如 888 号，无论去掉哪个数字，余下的都是 88 号，也就 是说，他必须到 88 号票站投票，因此 88 号票站不能关闭；同理可知， 00,11,L,99 号票站 都不能关闭 设想将需要开放的投票站按其编号的首位数字 0,1, 2,L,9 ，共分成十类（十个集合） ， 分别记为 M 0 , M1 ,L, M 9 ，据以上讨论可知每一类皆不是空集 现在设，在这十类中，以 M r 的元素个数为最少，它总共有 k 个元素，记这 k 个投票站 的编号为 rn1 , rn 2 ,L , rn k ， n1 , n2 ,L , nk 0,1,L ,9 ， 显然有 r n1 , n2 ,L , nk （因为 rr 号票站含在其中） ，并且 1 k 9 ，即 1 M r 9 ， （事 实上，除了上面列举的 10 个票站不能关闭外，其余的 90 个票站，我们可以随意关闭其中一 个而不会影响投票，例如 36 号，因为能够到 36 号票站投票的选民，只有三种情况： 对于第一、 二种情况， 他可去 6, 3 号票站， 对于第三种情况，3 6