当前位置：首页 > 计算机应用数学-（组合数学）-答案哈工大
1，证明，如果从集合{1，2，...，2n}中选择n+1整数，那么总存在两个整数，它们之间相差为1.
2，用鸽巢原理证明，有理数m/n展开的十进制小数最终是要循环的。例如，34 478/99 900=0.345 125 125 125 125 12...
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次方 X 5的2次方 X 7的6次方 X 11 ii）620
iii）10的10次方
7，确定下列类型的一手牌（5张牌）的数目。
i）full houses （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）full houses （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 14<=a1+13 题4：一个袋子装了100个苹果，100个香蕉，100个橘子，100个梨子。如果我们每分钟从袋子里取出1种水果，那么需要多少时间我就能肯定至少已经拿出1打相同种类的水果。 搜索更多关于： 计算机应用数学-（组合数学）-答案哈工大 的文档
本文作者：...共分享92篇相关文档
