《组合问题------陶平生.doc》由会员分享,可在线阅读,更多相关《组合问题------陶平生.doc(40页珍藏版)》请在文库网上搜索。
1、组合问题-A解答(陶平生)1、将数集中所有元素的算术平均值记为,(). 若是的非空子集,且,则称是 的一个“均衡子集”试求数集的所有“均衡子集”的个数解:由于,令,则, 依照此平移关系,和的均衡子集可一一对应用表示的元均衡子集的个数,显然有(的元均衡子集只有,一元均衡子集只有) 的二元均衡子集共四个,为, 因此 的三元均衡子集有两种情况:(1)含有元素的为, 共四个;(2)不含元素的,由于等式可表示为以及,得到个均衡子集,因此 的四元均衡子集有三种情况:(1)每两个二元均衡子集之并:, 共个集;(2)不含元素的三元均衡子集与的并集,共个集;(3)以上两种情况之外者,由于等式可表为以及得个均衡子
2、集与,因此又注意到,除本身外,若是的均衡子集,当且仅当其补集也是的均衡子集,二者一一对应. 因此从而的均衡子集个数为即的均衡子集有个2、若集合的子集中的每个元素都可表为两个自然数(允许相同)的平方和,求这种集中元素个数的最大值.解:不超过的平方数是 .显然,中的每个数可表为形式,这种数共有个;而中的每一对数(允许相同)的和在中,这种数有个,(其中,形式的数个,形式的数个).其次,形式的数个;形式的数个;形式的数个;形式的数个;共得个,再考虑重复情况,利用如下事实:若则不超过且能表为两个不同正整数的平方和的数有,该组中的每个数与的积,以及都在集中,且都可用两种方式表为平方和,故各被计算了两次,累
3、计有次重复(与的积已包含在以上乘积组中);因此,集中元素个数的最大值为.3、将前九个正整数分成三组,每组三个数,使得每组中的三数之和皆为质数;求出所有不同分法的种数证:、由于在中,三个不同的数之和介于和之间,其中的质数有这六个数,今将这六数按被除的余数情况分为两类:,其中每个数被除余;,其中每个数被除余;假若所分成的三组数对应的和为互异质数,则因被整除,故三个和数必为同一类数,因为类三数和,类三数和,矛盾!故三个和数中必有两个相等、据知,将表成中的三数和(其中有两数相等),只有四种情况:;由于在中有个奇数,故分成的三组中必有一组,三数全为奇数,另两组各有一个奇数对于情形,和为的组只有,剩下六数
4、,分为和为的两组,且其中一组全为奇数,只有唯一的分法:与;对于情形,若三奇数的组为,则另两组为 ;或;若三奇数的组为,则另两组为 ,或;若三奇数的组为,则另两组为 ;共得分法种;对于情形,若三奇数的组为,则另两组为 ;若三奇数的组为,则另两组为 或;若三奇数的组为,则另两组为 或;共得分法种;对于情形,和为的组只有,则另两组为 ;据以上,共计得到种分法4、设,若有四个互异数,使得,就称与是集的一个“平衡对”,求集中“平衡对”的个数解:将圆周等分,其分点按顺时针方向顺次记为,则当且仅当弦 注意如下事实:圆周等分点的任一对分点连线都不是直径,因此全部弦共有个方向(分别与过的切线平行,)与过的切线平
5、行的弦有条,共形成个“平行弦对”,若考虑所有个方向,共得 个“平行弦对”即中有个平衡对5、某校有名新生,每人至少认识其中人,试求的最小值,使得其中必存在彼此认识的个人.解:记这个人的集合为,所认识的人的集合记为,则,且,若是中相识的两人,则有,当,则有,且两两相识,而.当,则有,且两两相识,而,如此继续,得两两相识,而.当,则有且两两相识,而由,得,为整数,则.再说明是最小的;若,我们可构造一种情形,使得中不存在相互认识的个人为此,将个人均分为等组,每组个人,令同组的人互不相识,而异组的任两人皆相识,则中任一人所认识的人的个数皆为,从中任取个人,必有两个人属于这组中的同一个组,于是这两人互不相
6、识,因此中不存在相互认识的个人.从而的最小值为.6、个赌徒每日聚赌一次,每次人一桌,共设三桌;若其中任两人都至少同桌一次,问赌博至少持续了多少天?解:至少持续了五天.先说明,天已够.记个人为,将其两两搭配,记,.先作模式搭配,安排如下:(一) ; (二) ; (三) ; (四) ; (五) .即: (一) ; (二) ; (三) ; (四) ; (五) 。其次说明至少需要五天,改记这人为 ,任取一人,他要与其他人中的每个人分别同桌,每次同桌都有另外三人作陪,这样至少需要天,但是人不能等分成四个“三人组”,于是必有一人,例如,至少两次与同桌,设这两次为:. 若只安排四天,在后续的两天中,其余人
7、,分别要与同桌;为使在这两天中能与这人都同桌,需将人等分成两组,每组人,设这两天所在的桌为:与,为使在这两天中也能与这人都同桌,则这两天所在的桌为:与;由于个赌徒每天都必需出场一次,于是在这两天中,第三桌的人都是;但是中至多有三人在第二天与同桌,因此在这四天中,中至少有三人与仍不能同桌,矛盾!因此至少需要五天.7、若四元集中的四个数能够分成和相等的两组,则称为“平衡集”.试求集的平衡子集的个数. 引理:对于给定的正整数与集合,用表示不定方程 (其中) 的解 的个数,则有 证: 当时,由,而当取定后,的值便唯一确定,故此时.当时,如在集中添加元素,则可得个解, 但是下列个解中皆含有添加元,不合条
8、件.于是此时的解数为 .又因集中的任两数之和,故当时, .引理证完.回到本题, 对于集中的平衡子集 , 如果中某两数之和等于另两数之和, 则称为型集;如果中某一数等于另三数之和,则称为型集.一、 先求型集的个数(记为). (i)当,其个数为 为奇数时,记,则当通过集中的奇数时, 通过集,所以 .为偶数时,记,则当通过集中的偶数时, 通过集,所以 .于是. 当其个数为 ,令 则 通过 于是当为奇数时,令. 当跑遍中奇数时,跑遍,所以 .当为偶数时,令. 当跑遍中偶数时,跑遍,.所以,因此,A型集的个数为.二再求型集的个数(记为).对于,不定方程(其中, 的解数记为. 显然,当时,且由, 可知 .
9、一般有, 当, 证明如下:对于的全体元分拆 将其分作两类:凡是含的分拆,其中,将左边诸元各减,化为,即形式,归入引理,即式中的第一情形,其解数为.凡是不含的分拆 ,其中,将左边诸元各减,化为 即形式,其中,其解数为.因此 , 即成立.进而有 + 并注意,对任何, 有 所以利用递推得: 于是 ,.从而 故中的平衡子集个数为 .8、设集合互质,求和:.讲解:由于所给的数值较大,于是一般化,将换成任一不小于的整数为此取 互质,并记 ,分析的变化趋势,易知,进而猜想,对于每个都有. 转而考虑证明,对每个都有.其中 ,.先分解求和区间(和式展布集):互质,,互质,.于是 (右端最后一个和式的求和范围是由
10、于 则 ).由于当 时,则.且由 以及 知, 不会被取到.从而式右端可合并为 .据,即有 .于是 ,因此 .9、设是一个元集,它的个子集组成的集簇记为,而是的非空子集簇,并且对于并、交、补运算是封闭的(即则也都属于).令k表示中的集的个数,试求k的取值范围.解:对于非空的集簇F,我们定义其中的“素集”如下:如果集簇中的一个非空集合满足,则或有,或有,就称是中的一个“素集”.显然,中的每个单元素集都是“素集”,若中没有单元集,则进而考察其中的2元素集、3元素集、等等. 又若,则本身即为中的素集.由于中只有有限个集合,故其中的素集也只有有限个,设为中的全部素集,共计个,则它们两两不交(否则,如有,
11、则由的“素性”,可推出,矛盾.)再证,. 即需证,事实上,若,而则一方面,另一方面,由于异于,故不是素集,因此又有某个素集含于它,设,则矛盾,从而其次说明,中的任一个集,都是若干个素集的并,则,而由的“素性”,每个或为空集或等于,即为若干个素集的并反之,据的封闭性,每个这类素集之并也是的一个元因此,中的全体集合(包括空集)的个数是即其中再说明,对于中的每个,都可能被取到将中的个元任意拆分成组,每组至少一个元,即,则每个都是素集,令F为由这些“素集”生成的簇,这时故k的取值范围是10、设为元集,若有个不同的子集,满足:对于每个,求正整数的最大值解:正整数的最大值为、先证明,存在的个子集,两两之交
12、不空;设,而为集合的全部个子集,令,则的个子集,两两之交不空;、再证,对于的任何个子集,其中必有两个子集不相交设是的个不同子集,其中每个皆含;用表示子集在中的补集,则对于任意,并且,(因前者含而后者不含),故,为的全部个不同子集,现将上述集合搭配成为对:;任取的个子集,必有两个子集属于同一对,则这两个子集不相交11、在一次晚会上,9位舞星共上演个“三人舞”节目,若在这些节目中,任二人都曾合作过一次,且仅合作一次,求的值.解:将9个人看成9个点,若两人同组演出过,则相应两点间连一条线段,于是两两间都要连线,共得36条线段,而每个三人舞对应于一个三角形,每个三角形有三条边,当所有的边都出现,且不重
13、复使用,共得个三角形,即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、如果数集满足条件:中的全体元素可以组成一个等差数列,则称集为算术集. 类似地,当集的子集满足上述条件时,则称为的算术子集.试证:对于元算术集,其算术子集的个数满足等式:.(其中,为正整数的真因数个数,即小于的正因数个数).证:不妨设,中的元素按顺序组成等差数列,则对于其中任一组数,它们组成等差数列的充要条件是其下标也组成等差数列.于是我
14、们只要讨论算术集的算术子集的个数.将中以为最大元的算术子集个数记为,则 ,显然有 ,今证明,一般地有 .为此,设是任一个以为最大元的算术子集,若它有个元,由,得,若该等差数列的公差为,得的最小元为.因 ,得,而为整数,则,从而对于固定的,这种子集的个数就是适合的正整数的个数,即个.今让依次取,(实际上,仅当时,才不为).则 ,同理,当时,又有,所以, 由于 故式右端的和数等于集合中属于的因数个数,也即等于集合中属于的因数个数,从而 ,据及立即得到,由、得.13、对于元集合,若元集,满足:,且,则称是集的一个“等和划分”(与算是同一个划分)试确定集共有多少个“等和划分”解一:不妨设,由于当集确定
15、后,集便唯一确定,故只须考虑集的个数,设,为最大数,由,则,于是 ,故中有奇数个奇数、若中有个奇数,因中的六个奇数之和为,而,则,这时得到唯一的;、若中有个奇数、两个偶数;用表示中这两个偶数之和;表示中这三个奇数之和,则,于是共得的种情形其中,、当,则,;可搭配成的个情形;、当,则,;可搭配成的个情形;、当,则,可搭配成的个情形;、当,则,可搭配成的个情形;、当,则,可搭配成的个情形;、当,则,;可搭配成的个情形;、当,则,;可搭配成的个情形、若中有一个奇数、四个偶数,由于中除外,其余的五个偶数和,从中去掉一个偶数,补加一个奇数,使中五数之和为,分别得到的个情形:综合以上三步讨论,可知集有种情
16、形,即有种“等和划分” 解二:元素交换法,显然,恒设;、首先注意极端情况的一个分划:,显然数组与中,若有一组数全在中,则另一组数必全在中;以下考虑两数至少一个不在中的情况,为此,考虑中个数相同且和数相等的元素交换:、;共得到个对换;、;共得到个对换;、;共得到个对换每个对换都得到一个新的划分,因此,本题共得种等和划分14、设正整数的各位数字全由和组成,由其中任意个连续数位上的数字所组成的位数,称为数的一个“段”. 若数的任两个“段”都不相同,证明:对于具有这种性质的最大正整数,其开初的一个“段”和最后的一个“段”必定相同.证:设是一个具有这种性质的最大正整数,由的最大性,在其后面无论添加或,所
17、得到的位数以及中,都有两个相同的“段”. 设在中有 ;在中有. 显然,(因),且,如果或,则直接去掉相应“段”中的末位数,可知结论成立;如果且,因,考虑各自的前一位数字,它们只取和两个值,其中必有两数相同,于是数中有两个相同的“段”,矛盾. 因此中必有一个为,故结论得证.15、设,问是否能将集合分拆成三个这样的元子集,使得对于每个子集,其中任两个数之和被除得的余数,既不为零,也不等于该集合中的另一个数?试就 分别讨论上述问题.解:时,对于集合,存在这种分划, 例如分成; (它已穷尽所有分法,其中分法与对偶; 即,若将一个式子中的每个元素换为,便得另一式.)时,对于集合,存在这种分划,例如分成,
18、(只有这一对分法;若将一个式子中的每个元素换为,便得另一式.)时,对于集合,不存在这样的分划. 为此,考虑适合条件的所有元子集,称题中条件为性质,若元子集 ,令,则,称这种子集为“相伴集”,显然,这两种子集一一对应. 为此,考虑数对以及,由于每对数的和为16,故不能同在一集,记含1的五元子集类为,含的五元子集类为,其余五元子集类为,显然,的集与的集一一对应,且的集与的集中都不能含有相邻的数。今求中的所有集合:为此, 先证明,类中的任一集合不含元素. 采用反证:类中如存在集合,使,因为.(这是由于皆与相邻,且,以下的同余记号中均省略),于是另三数将取自,且与中的任两数不能共存,这是由于,若取因则
19、皆不能取;若取因则也不能取。反之,如取或,据以上四式知,与也不能取。若三数取自,若,则因,故不能取,因此另三数将取自,显然,否则不能取,也不能同取3,13,矛盾. 于是中的数是,或,但前组中有,后组中有,矛盾。若三数取自,同样知不能取,即另三数在中选取,进而知不能取,否则不能取,也不能同取于是中的数为或,而前组中有,后组中有,矛盾。所以.类中如存在集合,使,因为,(与相邻,),因此另三数将取自,且由 ,知,中的任两数不能并存, 若另三数取自,则,故中的数是,而其中有,矛盾. 若另三数取自,则而,矛盾.因此.类中如存在集合,使,因为,(, ),且据前述,因此另三数将取自,若取,则(因与相邻,而)
20、,故中的数只有,而其中,矛盾.故不取,中另三数取自因,故不能同取,必取,且中必取一数,若取则不能取,(因),矛盾,若取因,也得矛盾.故,从而.所以中除外的另四数取自,(括号中的每对数不能同取),若取,则不能取(因与相邻,),余下的数为,每组恰取一数,且不能取(否则皆不能取),于是得两组解:;若不取,如果取,则不能取(因与相邻,),余下三数从中取出,每组恰取一数,得两组解:;如果与都不取,即要从中取出四数,每组恰取一数,则只有一解:.(这是由于,若有 如果,矛盾;如果,因,矛盾。故,如果因,则,矛盾,故,因,故得一解 ) 由此知,类共有五个集:;据相伴性得,类也恰有五个集:,.用表示类集合,考虑
21、集的分划:,注意其中中不能同时含有及任何相同元素,这种搭配只有三种:,对于这三种搭配,分别有,;显然,中有,中有,中有,即都不具有性质,因此,不存在合于题意的分划.15、奥运会排球预选赛有支球队参加,其中每两队比赛一场,每场比赛必决出胜负,如果其中有()支球队,满足:胜,胜,胜,胜,则称这支球队组成一个阶连环套;证明:若全部支球队组成一个阶连环套,则对于每个()及每支球队,必另外某些球队组成一个阶连环套.证明:以为顶点,如球队胜,则在两点间连一有向边:,如此得阶竞赛图据条件,的个顶点可以排成一个阶有向圈,设为:,于是的任两点可沿箭头方向相互到达先证明,任一球队必在某个三阶连环套中,用分别表示被
22、击败了的球队集合和击败了的所有球队集合,由于双向连通,必有,使,于是组成三阶连环套;假若已证得,对于,图中存在以为一顶点的阶连环套,圈之外的点的集合为;若中有一点,它所表示的球队既击败了圈中的某个队,又被圈中的另一个队所击败,点把圈分成两条有向路,其中一条,例如,它与有向路组成有向圈,如图所示依次考虑路:上各点与点间的邻接情况,必有相邻的两点,满足而,今去掉边,而将路插入其间,便得到一个含有顶点的阶连环套;若中的任一点,它所表示的球队要么击败了圈中的每个队,要么被圈中的每个队所击败,则集可分为两个不交的子集与,其中中的任一队,战胜了圈中所有的队,而中的任一队,负于圈中所有的队;由于图双向连通,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 问题 平生