集合的分划与子集族

1、集合的划分与子集族（即奥林匹克小丛书集合一册的第4、5讲）一、集合的划分例1、将集合1,2,L,1989分为117个互不相交的子集Ai1,2,L,117使得:（1）每个A都含有17个元素；（2）每个A中各元素之和都相同。例2、对一个由非负整数组成的集合S，定义rsn是满足下述条件的有序对S1,S2的对数：,S2S且s2,s1s2n,问能否将非负整数集分划为两个集合A和B,使得对任意n均有例3、设集合A1,2,L,m，求最小的正整数m,使得对A的任意一个14分划A,A2,L,A4,4一定存在某个集合A1i14,在A中由两个元素a,b，满足ba-b3例4、证明：可以把自然数集分划为100个非空子集

2、，使得对任何数a,b,c,都可以从中找出两个数属于同一子集3个满足关系式a99bc的自然例5、设集合A,A2,L,An和Bi,B2,L,Bn是集合M的两个n分划，已知对任意两个交集为空集的集合A&1i,jn,均有AUBNAuA2ULUAr,求证其中必有某个子集A,它具k,都能找到a1,a2,L,akA,满足m,1jk1aj例7、将正整数集拆分成两个不相交的子集元素，使它们的和形如2k2k0,1,2,LA,B，满足条件：(1)1A;(2)A中没有两个不同的;(3)B中也没有两个不同的元素，其和具有上述形式。证明：这种拆分可以以惟一的方式实现，并确定2007,2008,2009所属的子集例6、设自

3、然数分划成r个互不相交的子集：有如下性质P:存在mN,使对任何正整数1aj1例8、平面上横纵坐标均为有理数的点叫有理点，求证：平面上的全部有理点可以分成3个两两互不相交的集合，满足条件：(1)在以每个有理点为圆心的任一圆内一定包含3个点分属这3个集合；(2)下任何一条直线上都不可能有3个点分属这3个集合例9、设A1,2,L,2008,M1004,2009,3014,对A的任一非空子集B，当B中任意两数之和不属于M时，称B为M自由集，如果AA1UA2,A1IA2,且A1,A2均为M自由集，那么称有序对为A1,A2为A的一个M划分，试求A的所有M划分的个数二、C族例10、试证：任一有限集的全部子集

4、可以排定次序，使得任何相邻的两个子集都相差一个元素例11、在某次竞选中各政党作出nn0种不同的诺言，有些政党可以作某些相同的诺言，现知其中每两个政党都至少作了一个相同的诺言，但没有两个政党的诺言完全相同，求证:政党个数2n1例12、设正整数n5,n各不同的正整数a,a2,L,an有下列性质：对集合Sa1,a2,L,an的任何两个不同的非空子集A和B,A中所有数的和与B中所有数的和都不会相等，在上述条件下，,、111一.求一一L一的最大值a1a2an三、求解子集族例13、已知集合A1,2,L,10，求集合A的具有下列性质的子集个数：每个子集至少含有2各元素，且每个子集中的任何两个元素的差的绝对值

5、大于1例14、对于正整数n2,如果存在集合1,2,L,n的子集族A,A2,L,An满足（1）iA,1in；（2）若ij,i,j1,2,L,n,则iAjjA;（3）任意i,j1,2,L,n,AIAj，则称n是“和谐数”证明：（1）7是和谐数；（2）除2,3,4,5,6夕卜，其余的n都是和谐数例15、集合X1,2,L,6k,kN,试作出X的三元子集族A，满足：（1）X的任一二元子集至少被族A中的一个三元子集包含；（2）A6k2四、有关子集族的最值问题例16、集合A0,1,2,L,9,B（,B2,L,Bk是A的一族非空子集，当ij时，BiIBj至多有两个元素，求k的最大值例17、设A0,1,2,L,

6、29满足：对任何整数k及A中的任意数a,b（a,b可以相同），ab30k均不是两个相邻整数之积，试确定所含元素个数最多的A例18、设A1,2,L,1997，对A的任意一个999元子集X，若存在x,yX,使得xy且xy,则称X为好集，求最大自然数aaA,使得任一含有a的999元子集都为好集集合的分划与子集族1、已知集合A1,2,L,3n1,3n，可以分为n个互不相交的三元组x,y,z，其中xy3z,则满足上述要求的两个最小的正整数n2、设S是一个有6个元素的集合，选取S的两个子集（可以相同），使得它们的并集是S,选取的顺序无关紧要，如a,c,b,c,d,ef与b,c,d,ef,a,c表示同一种取

7、法，这样的取法有种3、设集合AUB1,2,L,9,AIB，求证：在A或B中含有三个元素x,y,z,使得xy2z4、已知集合M是A1,2,L,2008的子集，且M中任一两个元素之和均不能被3整除，求集合M中元素个数的最大值5、试证：对于每个整数r1,都能找到一个最小的整数hr1,使在集合1,2,L,hr分成r组的任何分划中，都存在整数a0,1xy,使数ax,ay,axy含于分划的同一组中6、已知这个空间被分成互不相交的5个非空集合，求证：必有一个平面，它至少与其中的四个集合有公共点7、X1,2,L,n,A,B,C是X的分划，即AUBUCX,并且A,B,C两两的交集都是空集,如果A,B,C中各取一

8、个元素，那么每两个的和都不等于第三个，求maxminA,B,C_,.、一ii一4.、“，d*.*8、（1）证明：正整数集N可以表示为三个彼此互不相交的集合的并集，使得：若m,nN,且mn2或5,则m,n属于不同的集合（2）证明：正整数集N可以表示为四个彼此互不相交的集合的并集，使得：若m,nN,且_.*.一mn2,3或5，则m,n属于不同的集合，并说明此时将N表示为三个彼此互不相交的集合的并集时，命题不成立9、确定所有的正整数n使得集合1,2,L,n可以分成5个互不相交的子集，每个子集中元素之和相等10、设k为正整数，Mk是2k2k与2k23k之间（包括这两个数在内）的所有整数组成的集合，能否

9、将Mk拆分为两个不相交的子集A,B，使得x2x2xAxB11、给定正整数n3,求具有下列性质的正整数m的最小值：把集合S1,2,L,m任意分成两个互不相交的非空子集的并集，其中必有一个子集内含有n个数（不要求它们互不相同）：x1,x2,L,xn,使得为x2Lxn1xn12、正整数n4具有下列性质：把集合Sn1,2,L,n任意分成两个互不相交的子集，总有某个子集，它含有三个数a,b,c（允许ab），使得abc,求这样的n的最小值13、设S为n个正实数组成的集合，对S的每个非空子集A,令fA为A中所有元素之和，求证:集合fAAS,A可以拆分成n个互不相交的子集，每个子集中的最大数与最小数之差为21

10、4、试求所有正整数k，使集合M1990,1991,L,1990k可以分解为两个互不相交的子集A,B,且使两个集合中的元素之和相等15、给定集合SZ1,Z2,L,乙993，其中Z1,Z2,L,Z1993为非零复数（可视为平面上非零向量）求证：可以把S中元素分成若干子集，使得（1）S中每个元素属于且仅属于一个子集；（2）每一子集中任一复数与该子集所有复数之和的夹角不超过90。；（3）将任二子集中复数分别作和，所得和数之间夹角大于90。.n2nr1n16、设r,s,n都是正整数，并且rsn,求证：集合A-,一,L,n2ns1nB；,?,L,一-一构成N1,2,L,n2的分划的充要条件是r和s都与n互

11、质17、设集合A1,2,L,2n1，求一个包含元素最多的集合A的子集B使得B中任意三个元素a,b,c都有abc18、集合A0,1,2,L,9的所有子集中，有这样一族不同的子集，它们两两的交集都不是空集，那么这族子集最多有个19、设集合A1,2,L,2008，现对A的任一非空子集X,令x表示X中最大数与最小数之和，则所有这样的x的算术平均数为20、集合1,2,L,n的所有子集中全部元素之和的总和是21、如果一个正整数集合中没有3个数是两两互质的，则称之为“和谐”的，问从1到16的整数集中“和谐”的子集的元素的最大数目是多少22、设S是集合1,2,L,9的子集，且S中任意两个不同的数作和，所得的数

12、两两不同，求maxS23、设A1,2,L,50,求最小正整数n使得A中的每个n元子集中都有三边长3个数能作为直角三角形的24、设p3为质数，考虑集合1,2,L,2p满足以下两个条件的子集A：A中所有元素之和可被p整除(1)A恰有p个元素；(2)25、设r2是一个固定的正整数，F是一个无限集族，且每个集合中含有r个元素，若F中的任意两个集合的交集非空，求证：存在一个具有r1个元素的集合与F中的每一个集合的交集非空26、设n2,nN,S是一个n元集合，求最小的正整数k,使得存在S的子集A1,AL,A具有如下性质：对S的任意两个不同元a,b,存在j1,2,L,k，使得气Ia,b为S的一元子集27、A

13、1,2,L,50，求最小的正整数k,使A的每个k元子集中都有两个数ab使得abab28、S是一个n元集合，S中最多有多少个这样的三元子集，使得其中任意两个三元子集都恰好有个公共元29、集合S1,2,L,15，从S中取出n个子集A1,A2,L,R满足下列条件：(1)A7;(2)AIAj3,1ijn；(3)对S的任意三元子集M，都存在某个Ak,1kn,使得MAk,求这样一组子集的个数n的最小值30、设A1,2,L,2002，对任意a,bA（a,b可以相同）总有abA,求A的最大值“如果2kA则2k1A且31、称子集AM1,2,L,11为好的，如果它具有下述性质:2k1A”（空集和M都是好的），M有多少个好子集32、n为给定的正整数，Dn为2n3n5n的所有正因数组成的集合，SDn，且S中任一数都不能整除S中另一数，求S的最大值33、A1,2,L,2008，且A具有如下性质：A中任两个不同元素之和不被7整除，求A的最大值34、AA,LA。1,2,L,2003的子集，且660,证明：存在1ij30,AIAj23035、A1,2,L,2000，且A中任意两数的差不等于4也不等于7,求A的最大值1,1ijn；(3)AIA2ILIAn36、已知A1,A2,L,An满足：(1)A30;(2)AIA求使这