计算机应用数学-(组合数学)-答案哈工大
玛丽莲梦兔
749次浏览
2021年01月26日 14:10
最佳经验
本文由作者推荐
形容雪的诗句-
1
，证明，如果从集合
{1
，
2
，
...
，
2n}
中选择
n+1
整数，那么总存在两个整数，它们之间相差为
1.
2
，
用鸽巢原理证明，
有理数
m/n< br>展开的十进制小数最终是要循环的。
例如，
34 478/99 900=0.345 125 125
125 125 12...
3
，一间屋内有
10
个人，他们当中没有人超过
60
岁（年龄只能以整数给出）但又至少不低于
1
岁。证明，
总能够找出两组人（两组不含相同人），各组人的年龄和是相同的。题中的数< br>10
能换成更小的数吗？
4
，一只袋子装了< br>100
个苹果、
100
个香蕉、
100
个橘子和
10 0
个梨。如果我每分钟从袋子里了出
1
种水
果，那么需要多少时间我就能肯定 至少已拿出了
1
打相同种类的水果？
5
，
< br>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
，学校有
10 0
名学生和
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*1 0=10
和
10*60=600
之间
.600-10=590
，1203>590,
故必有两组年龄之和相等。
2^9-1=511
，
5 11
不大于
590
，故题中的数
10
不能换成更小的数。
4
，取
11*4+1=45
个水果，必然有一种水果不少于
12
个，否则取的水果总数不会超过
11*4=44
个，即需
要
4 5
分钟即可拿出了
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=748 8
种选法。
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
，< br>35
和
40
人。
i
）
A 宿舍有方案
C(100,25)
，
B
宿舍有方案
C(75,35 )
，
C
宿舍有方案
C(40,40)
，共计
((100*9 9
*…*76)/(1*2*3*…25))*((75*76*…*41)/(1*2*3*…*35 ))
ii
）
50
名男生和
50
名女生分别住进 宿舍
A
，宿舍
B
共有
2^50*2^50
种方法，这
也是全部方法。
鸽巢原理也叫抽屉原理，是
Ramsey< br>定理的特例。也是编程爱好者必须掌握的研
究离散问题中存在性问题的方法。
它的简单形式是
：
把ｎ＋１个物体放入
n
个盒 子里，
则至少有一个盒子里含有
两个或两个以上的物体
。
做题之前，先贴几个小问题：
（
1
）月黑风高穿袜子
有一个晚上你的房间的电灯忽然间坏了，
伸手不见五指，
而你又 要出去，
于
是你就摸床底下的袜子。你有三双分别为红、白、蓝颜色的袜子，可是你平时做事随便，一脱袜就乱丢，在黑暗中不能知道哪一双是颜色相同的。
你想拿最少数目的袜子出去，
在外面借街灯配成同颜色的一双。
这最少数目
应该是多少 ？
如果你懂得鸽笼原理，你就会知道只需拿出去四只袜子就行了。
为什么呢？因为如果我们有三个涂上红、
白、
蓝的盒子，
里面各放进相对颜
色的袜子，
只要我们抽出
4
只袜子一定有一个盒子是空的，
那么这空的盒子取 出
的袜子是可以拿来穿。
（
2
）手指纹和头发
据说世界上没有两个人的手指纹是一样的，
因此警方在处理犯罪问题时很重
视手指纹，希望通过手指纹来破案或检定犯人。
可是你知道不知道：< br>在
12
亿中国人当中，
最少有两个人的头发是一样的多？
道理是很简单，人的头发数目是不会超过
12
亿这么大的数目字！假定人最
多有
N
根头发。现在我们想像有编上号码
1
，
2
，
3
，
4
，…一直到
N
的房子。
谁有多少头发，
谁就进入那编号和他的头发数相同的房子去。
因此张乐平先
生的“三毛”应该进入“
3
号房子”。
现在 假定每间房巳进入一个人，那么还剩下“九亿减
N
”个人，这数目不会
等于零，
我们现在随便挑一个放进一间和他头发数相同的房子，
他就会在里面遇
到和他有相同头发数目 的同志了。
（
3
）戏院观众的生日
在一间能容纳
1500
个座位的戏院里，证明如果戏院坐满人时，一定最少 有
五个观众是同月同日生。
现在假定一年有三百六十五天。< br>想像有一个很大的鸽子笼，
这笼有编上
“一
月一日”，“一月二日”，至到“十 二月三十一日”为止的标志的间隔。
假定现在每个间隔都塞进四个人，那么
4
×
365=1460
个是 进去鸽子笼子里
去，还剩下
1500-1460=40
人。只要任何一人进入鸽子笼， 就有五个人是有相同
的生日了。
解题的关键是：弄清题目中，谁是鸽子谁是巢
题
1
：证明，如果从
{1,2,3,....3n}
中选择
n+1
个整数，那么总存在两
个整数，他们之间的差最多为
2
。
解：
分组化简。
将这< br>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
整数的数分为
5 1
组（鸽子）。而从中取
52
个，（巢）。必有两个在同一组。得证。
题
3
：一个学生有
37
天来准备考试，她知道她需要不超过
60
小时的学
习时间，
她还希望每天至少学习
1
小时。
证明，< br>无论如何安排学习时间
（每天都是整数小时），都存在连续的若干天，在此期间她恰好学习了13
个小时。
证明：令
a1
为她第一天学习的小时数，
a2
为第二天的学习时数。这样。存在这
样一个递增数列
a1,a2,a3,... ...a37
。满足：
1<=a1
13
。则存在数列：
14<=a1+13
37+37=74个成
员。这样。鸽子和巢终于出现
^_^
必然存在一个
ai,
和一个
aj.
使得
ai=aj+13.
就是说这两个数列中必然有两个差为< br>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< br>≠
j
，使得
ai-aj
能够被
n
整除。
< br>解：由于任一整数被
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< br>个数时，必
然有至少两个属于同一鸽巢，即他们的差最多为
2
14
、一只袋子装了
100
个苹果、
100
个香蕉、
100个橘子和
100
个梨子。如果我
每分钟从袋子里取出
1
个水果，
那么需要多长时间我就能肯定至少已拿出了一打
相同种类的水果？
答：根据鸽巢原理的加强形式可得：
,
故需
45
分
钟。
16
、证明在一群
n>1
个人中，存在两个人，他们在这群人中有 相同数目的熟人。
答：已知，每个人认识的人数为
0,1,
…< br>n-1
。而这一群人中不可能同时存在认识
0
人和
n-1
人的 情况，因此，所有人所认识人数范围为
1,2,3,
…
,n-1
或
0 ,1,2
…
,n-2
，