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

玛丽莲梦兔
807次浏览
2021年01月26日 14:10
最佳经验
本文由作者推荐

形容雪的诗句-

2021年1月26日发(作者:最长寒假)
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个物体放入
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

形容雪的诗句-


形容雪的诗句-


形容雪的诗句-


形容雪的诗句-


形容雪的诗句-


形容雪的诗句-


形容雪的诗句-


形容雪的诗句-