计算机应用数学-(组合数学)-答案哈工大.doc

计算机应用数学-(组合数学)-答案哈工大.doc

《计算机应用数学-(组合数学)-答案哈工大.doc》由会员分享，可在线阅读，更多相关《计算机应用数学-(组合数学)-答案哈工大.doc（10页珍藏版）》请在冰点文库上搜索。

1，证明，如果从集合{1，2，...，2n}中选择n+1整数，那么总存在两个整数，它们之间相差为1.

2，用鸽巢原理证明，有理数m/n展开的十进制小数最终是要循环的。

例如，34478/99900=0.34512512512512512...

3，一间屋内有10个人，他们当中没有人超过60岁（年龄只能以整数给出）但又至少不低于1岁。

证明，总能够找出两组人（两组不含相同人），各组人的年龄和是相同的。

题中的数10能换成更小的数吗？

4，一只袋子装了100个苹果、100个香蕉、100个橘子和100个梨。

如果我每分钟从袋子里了出1种水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？

5，

i）证明，在边长为1的等边三角形内任意选择5个点，存在2个点，其间距离至多为1/2。

ii）证明，在边长为1的等边三角形内任意选择10个点，存在2个点，其间距离至多为1/3。

iii）确定一个整数m小n，使得如果在边长为1的等边三角形内任意选择的m小n个点，则存在2个点，其间距离至多为1/n.

6，下列各数各有多少互异正因子？

i）3的4次方X5的2次方X7的6次方X11

ii）620

iii）10的10次方

7，确定下列类型的一手牌（5张牌）的数目。

i）fullhouses（3张一样大小的牌及2张相同点数的另外大小的牌）。

ii）顺牌（5张点数相连的牌）。

iii）同花（5张一样花色的牌）。

iv）同花顺（5张点数相连的同样花色的牌）。

v）恰好两个对（一对同样大小，另一对另外点数同样大小，再有一张另外大小的5张牌）。

vi）恰好一个对（一对同样大小，另外三张另外大小且互异点数的牌）。

8，从拥有10名男会员和12名女会员的一个俱乐部选出一个5人委员会。

如果至少要包含2位女士，能够有多少种方法形成这个委员会？

此外，如果俱乐部还有一位特定的男士和一们特定的女士拒绝进入该委员会一起工作，形成委员会的方式又有多少？

9，学校有100名学生和3个宿舍A，B和C，它们分别容纳25，35和40人。

i）为学生安排宿舍有多少种方法？

ii）设100个学生中有50名男生和50名女生，而宿舍A是全男生宿舍，宿舍B是全女生宿舍，宿舍C男妇兼收。

有多少种方法可为学生安排宿舍？

1，将1，…，2n这2n个数分为如下n组，（1,2）,（3,4）,（5,6）,…,（2n-1,2n），由鸽巢原理，任选择n+1整数必有两数同在一组。

2，用n作除数去除m，在除法的演算过程中，余数必是0，1，2，…,n-1中的一个，而余数无穷多，因此由鸽巢原理在作除法时一定会出现相同的余数，后面的计算将会重复，于上所得的商也必然重复。

3，10个人，最多可形成2^10-1=1023个组,组的年龄总和介于1*10=10和10*60=600之间.600-10=590，1203>590,故必有两组年龄之和相等。

2^9-1=511，511不大于590，故题中的数10不能换成更小的数。

4，取11*4+1=45个水果，必然有一种水果不少于12个，否则取的水果总数不会超过11*4=44个，即需要45分钟即可拿出了1打相同种类的水果。

5，i）连结三角形的三条边上的中点，将该三角形分为4个小三角形，必有两点在同一个小三角形内，这个小三角形的边长为1/2，故这两点其间距离至多为1/2。

ii）将三角形一条边分为三等份，将分点互相连结起来得9个边长为1/3的小三角形，

此时必有两点在同一个小三角形内，故这两点其间距离至多为1/3。

iii）确定一个整数m小n，使得如果在边长为1的等边三角形内任意选择的m小n个点，则存在2个点，其间距离至多为1/n.?

?

?

?

6，i）3的4次方*5的2次方*7的6次方*11

有互异正因子个数为（4+1）*（2+1）*（6+1）*（1+1）=5*3*7*2=210

ii）620=31*2^2*5，故有互异正因子个数为（1+1）（2+1）（1+1）=12

iii）10的10次方，故有互异正因子个数为（1+10）=11

7，确定下列类型的一手牌（5张牌）的数目。

i）fullhouses（3张一样大小的牌及2张相同点数的另外大小的牌）。

3张一样大小的牌有4*13种选法，2张相同点数的另外大小的牌有4*3*12种选法，故共有4*13*4*3*12=7488种选法。

ii）顺牌（5张点数相连的牌）。

1-5，2-6,…,9-13共9种情况，每种情况均有5^4种选取，共有9*5^4=5625。

iii）同花（5张一样花色的牌）。

每一种花色有C（13,5）种，故共有（13*12*11*10*9/1*2*3*4*5）*4=1287*4=5148种。

iv）同花顺（5张点数相连的同样花色的牌）。

每一种花色有9种，4种花色共有9*4=36种。

v）恰好两个对（一对同样大小，另一对另外点数同样大小，再有一张另外大小的5张牌）。

一对同样大小的有C（4,2）*13种选法,另一对另外点数同样大小C（4,2）*12种选法,再有一张另外大小的第5张牌有11*4种选法，共计有

（4*3/2*1）*13*（4*3/2*1）*12*11*4

vi）恰好一个对（一对同样大小，另外三张另外大小且互异点数的牌）。

一个对子的选法有C（4,2）*13种选法，另外三张牌的选法有C（12,3）*4，共计C（4,2）*13*C（12,3）*4

8，首先选2位女士有C（12,2）种选法，其他剩余的20人可选可不选共有20^2种选法，如果至少要包含2位女士共计有（12*11/2）*20^2,如果俱乐部还有一位特定的男士和一们特定的女士拒绝进入该委员会一起工作，2位女士有C（11,2）种选法，其他剩余的9男9女可选可不选有9^2*9^2种选法，共计有（11*10/2）*9^2*9^2种选法。

9，学校有100名学生和3个宿舍A，B和C，它们分别容纳25，35和40人。

i）A宿舍有方案C（100,25），B宿舍有方案C（75,35），C宿舍有方案C（40,40），共计（（100*99*…*76）/（1*2*3*…25））*（（75*76*…*41）/（1*2*3*…*35））

ii）50名男生和50名女生分别住进宿舍A，宿舍B共有2^50*2^50种方法，这也是全部方法。

鸽巢原理也叫抽屉原理，是Ramsey定理的特例。

也是编程爱好者必须掌握的研究离散问题中存在性问题的方法。

它的简单形式是：

把ｎ＋１个物体放入n个盒子里，则至少有一个盒子里含有两个或两个以上的物体。

做题之前，先贴几个小问题：

（1）月黑风高穿袜子

　　有一个晚上你的房间的电灯忽然间坏了，伸手不见五指，而你又要出去，于是你就摸床底下的袜子。

你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜就乱丢，在黑暗中不能知道哪一双是颜色相同的。

　　你想拿最少数目的袜子出去，在外面借街灯配成同颜色的一双。

这最少数目应该是多少？

　　如果你懂得鸽笼原理，你就会知道只需拿出去四只袜子就行了。

　　为什么呢？

因为如果我们有三个涂上红、白、蓝的盒子，里面各放进相对颜色的袜子，只要我们抽出4只袜子一定有一个盒子是空的，那么这空的盒子取出的袜子是可以拿来穿。

（2）手指纹和头发

　　据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很重视手指纹，希望通过手指纹来破案或检定犯人。

　　可是你知道不知道：

在12亿中国人当中，最少有两个人的头发是一样的多？

　　道理是很简单，人的头发数目是不会超过12亿这么大的数目字！

假定人最多有N根头发。

现在我们想像有编上号码1，2，3，4，…一直到N的房子。

　　谁有多少头发，谁就进入那编号和他的头发数相同的房子去。

因此张乐平先生的“三毛”应该进入“3号房子”。

　　现在假定每间房巳进入一个人，那么还剩下“九亿减N”个人，这数目不会等于零，我们现在随便挑一个放进一间和他头发数相同的房子，他就会在里面遇到和他有相同头发数目的同志了。

　（3）戏院观众的生日

　　在一间能容纳1500个座位的戏院里，证明如果戏院坐满人时，一定最少有五个观众是同月同日生。

　　现在假定一年有三百六十五天。

想像有一个很大的鸽子笼，这笼有编上“一月一日”，“一月二日”，至到“十二月三十一日”为止的标志的间隔。

　　假定现在每个间隔都塞进四个人，那么4×365=1460个是进去鸽子笼子里去，还剩下1500-1460=40人。

只要任何一人进入鸽子笼，就有五个人是有相同的生日了。

解题的关键是：

弄清题目中，谁是鸽子谁是巢

题1：

证明，如果从{1,2,3,....3n}中选择n+1个整数，那么总存在两个整数，他们之间的差最多为2。

解：

分组化简。

将这3n个整数分组，{1,2,3}，{4,5,6}.....{3n-2,3n-1,3n}共n组。

这样题目等价于：

将n+1个整数放在n个盒子里。

则根据原理，至少存在一个盒子里有两个数，这两个数之差最多为2。

题2：

证明，对于任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除。

要么两者的差能被100整除。

解：

还是分组化简！

将数这样进行分组：

将所有整数的后两位尾数分组。

{+0,-0,+100,-100,+200,-200....}，{+1,-1,+99,-99,+101,-101,+199,-199,+201,-201......}，......，{+49,-49,+51,-51,+149,-149,+151,......}{+50,-50,+150,-150,+250,-250......}   这样。

将所有的能被100整数的数分为51组（鸽子）。

而从中取52个，（巢）。

必有两个在同一组。

得证。

题3：

一个学生有37天来准备考试，她知道她需要不超过60小时的学习时间，她还希望每天至少学习1小时。

证明，无论如何安排学习时间（每天都是整数小时），都存在连续的若干天，在此期间她恰好学习了13个小时。

证明：

令a1为她第一天学习的小时数，a2为第二天的学习时数。

这样。

存在这样一个递增数列a1,a2,a3,......a37。

满足：

1<=a1

同时，将这个数列每个数都加上13。

则存在数列：

14<=a1+13

而这两个数列共有37+37=74个成员。

这样。

鸽子和巢终于出现^_^必然存在一个ai,和一个aj.使得ai=aj+13.就是说这两个数列中必然有两个差为13的数。

得证。

 题4：

一个袋子装了100个苹果，100个香蕉，100个橘子，100个梨子。

如果我们每分钟从袋子里取出1种水果，那么需要多少时间我就能肯定至少已经拿出1打相同种类的水果。

解：

根据鸽巢原理加强形式：

如果q1,q2,,,,,qn为正整数，将q1+q2+.....qn-n+1个物体放入n个盒子里。

那么，至少存在一个盒子含有qn个物体。

对于此题：

我们需要取12个水果。

设已经取出了11个水果，还剩下一个。

那么需要11×4+1分钟。

题5：

证明对于任意n+1个整数a1,a2,.....a（n+1）存在两个整数ai和aj，i≠j，使得ai-aj能够被n整除。

解：

由于任一整数被n整除的余数有0,1,2,......n-1。

 共n种，对于n+1个数，由鸽巢原理可得证。

即存在ai,aj。

ai=bn+r,aj=cn+r（b>c）。

ai-aj=（b-c）n。

所以n|ai-aj。

至少两个整数被n整除的余数相等。

题6：

证明，边长为2的正方形中取5个点，当中存在2个点，这2点的距离至多为√2

解：

将正方形分成四等分即可

第二章:

5、证明：

如果从{1,2,3，…，3n}中选择n+1个整数，那么总存在两个整数，他们之间最多差2。

答：

取鸽巢为{1,2,3},{4,5,6},….,{3n-2,3n-1,3n}共n个，当从中选取n+1个数时，必然有至少两个属于同一鸽巢，即他们的差最多为2

14、一只袋子装了100个苹果、100个香蕉、100个橘子和100个梨子。

如果我每分钟从袋子里取出1个水果，那么需要多长时间我就能肯定至少已拿出了一打相同种类的水果？

答：

根据鸽巢原理的加强形式可得：

故需45分钟。

16、证明在一群n>1个人中，存在两个人，他们在这群人中有相同数目的熟人。

答：

已知，每个人认识的人数为0,1,…n-1。

而这一群人中不可能同时存在认识0人和n-1人的情况，因此，所有人所认识人数范围为1,2,3,…,n-1或0,1,2…,n-2，均为n-1个，现在有n个人，由鸽巢原理可知，必然存在至少两个人认识的人数相等。

18、证明，从边长为2的正方形中任选5个点，他们当中存在2个点，这两个点的距离最多为。

答：

如图所示，将图分割成四个小正方形，可知小正方形内的两点之间的最大距离为，而由鸽巢原理可知，从图中任选5个点则必有至少两个点在同一小正方形内，即他们的距离最多为

第三章：

4、问620有多少个互异正因子。

答：

将620因式分解可得：

620=，所以互异正因子的个数为3*2*2=12

8、有15个人围坐一个圆桌。

其中，如果B拒绝挨着A坐，有多少种围坐方式？

如果B只拒绝坐在A的右边，又有多少种围坐方式？

答：

这15个人围坐的方法一共有14!

种，

（1）A和B在一起的情况，则围坐方法有13!

*2种，因此，B拒绝挨着A坐的情况一共有14!

-13!

*2=12*13!

。

（2）考虑B只在A一侧的情况，则，相当于AB相对位置固定，则围坐的方法一共有13!

种，所以，B只拒绝坐在A的右侧的方法数为14!

-13!

=13*13!

。

17、将2个红车4个蓝车放在8*8的棋盘上，使没有两个车可以互相攻击的摆放方式有多少种？

答：

27、确定多重集S={3a,3b,3c,3d}的11排列的个数。

答：

由11排列我们可知：

S={2a,3b,3c,3d}U{3a,2b,3c,3d}U{3a,3b,2c,3d}U{3a,3b,3c,2d}，即对这些11元素集合进行排列计数，即得S的11排列个数为：

第四章：

15、对于{}通过使用基为2的生成算法确定其直接后继组合。

答：

用2进制表示为：

（1011111），+1后为1100000，所以，后继组合为{}

31、生成{1,2,3,4,5}的3排列。

答：

首先写出它的3-组合：

123,124,125,134,135,145,234,235,245,345

然后分别进行排列：

123132231213312321

124142241214412421

125152251215512521

134143341314413431

135153351315513531

145154451415514541

234243342324423432

235253352325523532

245254452425524542

345354453435534543

第六章：

3、求出从1到10000既不是完全平方数又不是完全立方数的整数个数。

答：

设S={1,2,…,10000}，为S中的完全平方数的集合，为S中完全立方数的集合，则问题是求||，由于=10000,>10000,所以||=100，由于，所以||=21。

为既是完全平方数，又是完全立方数的集合，亦即：

，由于=4096，=15625>10000，故，。

所以：

||=10000-（100+21）+4=9883

13、确定{1,2,3,4,5,6,7,8,9,}的至少一个奇数在他的自然位置上的排列数

答：

设S为{1,2,3,…,9}的排列的全体，，，，则问题变成求||。

，，，

所以：

||=5*8！

-10*7！

+10*6！

-5*5！

+4！

15、在一次聚会上，7位绅士检查他们的帽子。

有多少种方法是的这些帽子返还时满足：

1）没有绅士收到他自己的帽子

2）至少一位绅士收到他自己的帽子

3）至少两位绅士收到他们自己的帽子

答：

1）这是一个错位排列问题，有种方法。

2）设S为7位男士收到帽子结果的全体，A为S中至少一位男士收到自己帽子的集合，则就是S中没有人收到自己帽子的集合，所以：

|A|=|S|-||=

3）无人收到自己帽子的情况数为，恰有一人收到自己帽子的情况数为C（7,1）。

所以，至少有两人收到自己帽子的情况数为

第九章：

9、考虑带有禁止位的n*n棋盘，其中一个正整数p，使每一行和每一列恰有p个放个允许放车，证明，在棋盘上能够放置n个非攻击车

答：

可写出这个棋盘对应的车-二分图G，显然G是p阶正则的，故由定理P>=1阶正则的二分图G=（X,∆,Y）总有完美匹配。

可知，存在完美匹配。

因此，在棋盘上能够放置n个非攻击车。

12、令$=（），其中

问$有SDR么？

如果没有，具有SDR的族中集合的最大个数是多少？

答：

因为||=5<6

故由定理集族A=（）有SDR的充要条件是：

对于任意k（1<=k<=n）以及从（1,2,…,n）中任意k个互异指标的选择，都有||>=k。

知$不存在SDR。

由于||+6-4=5

根据定理令A=（）为集Y的子集族，A中有SDR的最大子集个数等于表达式||+n-k对于任意k（1<=k<=n）以及从（1,2,…,n）中任意k个互异指标的选择的最小值。

可知，族中有SDR的集合的最大个数是5。

26、应用延迟认可算法得出下列评定矩阵的稳定婚姻。

答：

（1）女士优先：

1）A选a，B选a，C选b，D选c；a拒绝B。

2）B选b，b拒绝C。

3）C选c，c拒绝D。

4）D选a；a拒绝A。

5）A选b；b拒绝B。

6）B选c，c拒绝C。

7）C选a，a拒绝D。

8）D选b，b拒绝A。

9）A选c，c拒绝B。

10）B选d，没有拒绝发生。

故：

稳定婚姻为：

Aßàc,Bßàd,Cßàa,Dßàb

（2）男士优先：

1）a选C，b选D，c选A，d选D；D拒绝b。

2）d选C，C拒绝d。

3）d选A，A拒绝d。

4）d选B，没有拒绝发生。

故：

稳定婚姻为：

aßàC,bßàD,CßàA,bßàD

附加题：