1.某甲参加一种会议,会上有 6位朋友,
某甲和其中每人在会上各相遇 12次,每二人各相遇 6次,每三人各相遇 3次,每五人各相遇 2次,每六人各相遇一次,1人也没有遇见的有 5次,问某甲共参加了几次会议解,...
第三章习题解答
2.求从 1到 500的整数中被 3和 5整除但不被 7整除的数的个数,
解,...
第三章习题解答
3,n代表参加会议,试证其中至少有 2
人各自的朋友数相等。
解,...
第三章习题解答
4,试给出下列等式的组合意义
m
l
l mkn
k
ln
l
m
kn
mn
a
0
,)1( )(
mn
j
j
l
ljmn
j
mn
mn
l
b
0
,
1
)1(
1
1
)(
第三章习题解答
lm
lm
m
lm
m
lm
m
lm
m
lm
c
l
)1(
2
11
1
)(
解,...
第三章习题解答
5.设有 3个 7位的 2进制数解,...
7654321 aaaaaaa
7654321 bbbbbbb
7654321 ccccccc
试证存在整数 i和 j,使得下列之一必然成立。 71 ji
jiji
jijijiji
ccbb
ccaabbaa
,
第三章习题解答
6,在边长为 1的正方形内任取 5个点试证其中至少有两点,期间距离小于解,...
2
2
1
第三章习题解答
7.在边长为 1的等边三角形内任取 5个点试证其中至少有两点,期间距离小于
2
1
解,...
第三章习题解答
8,任取 11个整数,求证其中至少有两个数它们的差是 10的倍数。
解,...
第三章习题解答
9,把从 1到 326的 326个整数任意分为 5个部分,试证其中有一部分至少有一个数是某两个数之和,或是另一个数的两倍。
解,...
第三章习题解答
10,A,B,C三种材料用作产品 I,II、
III的原料,但要求 I禁止用 B,C作原料,
II不能用 B作原料,III不允许用 A作原料,
问有多少种安排方案?(假定每种材料只做一种产品的原料)
解,...
第三章习题解答
11,n个球放到 m个盒子中去,
试证其中必有两个盒子有相同的球数。
)1(2 mmn
解,...
第三章习题解答
12,n各单位各派两名代表去出席一会议。 位代表围一圆桌坐下。试问:
( 1)各单位代表并排坐着的方案是多少?
( 2)各单位的两人互不相邻的方案数又是多少?
解,...
n2
第三章习题解答
13,一书架有 m层,分别放置 m类不同种类的书,每层 n册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问
( 1) m类书全不在各自原来层次上的方案数有多少?
( 2)每层的 n本书都不在原来位置上的方案数等于多少?
( 3) m层书都不在原来层次,每层
n本书也不在原来位置上的方案数又有多少? 解,...
第三章习题解答
14,行 列 的格子同种颜色着色,每格赵一种颜色,其中必有一个 4角同色的矩形。
解,...
)1(?m?
1
2
1m
m m
第三章习题解答
15,两名教师分别对 6名学生同时进行两门课程的面试(每名教师各管一门课程)
每名学生每门面试的时间都是半个小时,
共有多少不同的面试顺序?
解,...
第三章习题解答
16,在平面直角坐标系中至少任去多少个整点(两个坐标系都是整数)才能保证其中存在 3个构成三角形(包含 3点在一条直线上)的面积是整数(可以为 0)
解,...
第三章习题解答
17,在平面直角坐标系中至少任去多少个整点才能保证存在 3个点构成的三角形的重心是整点?
解,...
第三章习题解答第三章习题解答
1,解 设 Ai为甲与第 i个朋友相遇的会议集,i= 1,…,6,则
| ∪ Ai|= 12 ( ) - 6 ( )+ 4 ( )
- 3 ( )+ 2 ( )- ( )
= 28
故甲参加会议数为
28+ 5= 33 ( 题目 )
6
1
6
2 63
6
4
6
5
6
6
第三章习题解答
2 解 设 A3,被 3整除的数的集合
A5,被 5整除的数的集合
A7,被 7整除的数的集合所以
| A7∩A5∩A3|
=| A3∩A5|- | A7∩A5∩A3|
=-= 33- 4= 29 ( 题目 )5003·5 5003·5·7
第三章习题解答
3 解 每个人的朋友数只能取 0,1,…,
n- 1,但若有人的朋友数为 0,即此人和其他人都不认识,则其他人的最大取数不超过 n- 2,故这 n个人的朋友数的实际取数只有 n- 1种可能,=2,所以至少有2人的朋友数相等,( 题目 )
n
n- 1
第三章习题解答
4 解 ( a ) 从 n个元素中取 k个元的组合,
总含指定的 m个元的组合数为 ( )=( )
设这 m个元为 a1,a2,…,am,Ai为不含 ai的组合 (子集 ),i=1,…,m.
| Ai| = ( )
| Ai1∩ Ai2∩···∩Ail|= ( )
( )=| ∩ Ai|
= ( ) + ∑ (- 1) ∑ | ∩ Aij |
= ∑(- 1) ( ) ( )
n- 1
k n- l
k
n- m
n- k
n
k
m
i=1m
l=1
l l
j=1{i1,…,i l}∈ ¢ (m,l)
l mk n- l
k
m
l=0
n- m
k- m
n- m
n- k
第三章习题解答
( b )令 k= n- m,l个相同的球放入 k个不同的盒子里.每盒不空的方案数为 ( ).
设 Ai为第 i个盒子为空的方案集,i=1,2,…,k.
| Ai |= ( ),| ∩ Ais | = ( )
( )= | ∩Ai |= ( )
+ ∑ (- 1) ∑ | ∩ Ais |
= ∑(- 1) ( ) ( )
l- 1
k- 1
k- 1+l- 1
l l- 1
k- 1
k- j+l- 1
l
k+l- 1
l
{i1,…,i j}∈ ¢ (k,j)
j
s=1
j
s=1k
i=1k
j=1
j
k
j=0
j k
j
k- j+l- 1
l
第三章习题解答
l个相同的球放入 n个不同的盒子里,指定的 m个盒子为空,其他盒子不空的方案数为 ( )l- 1n- m- 1
第三章习题解答
( c ) 设 Ai为 m+l个元中取 m+i个,含特定元素
a的方案集; Ni为 m+l个元中取 m+i个的方案数.则:
Ni= ( )
| Ai |=( ),| Ai |=( )
| Ai+1 |= | Ai |=( )
| Ai |= Ni- | Ai | i=0,1,…,l.
| A0 |=N0 - | A0 | =N0- | A1 |=N0- (N1- |A1|
=N0- N1+N2- …+( - 1) Nl (题目 )
m+l
m+ im+l- 1
m+ i- 1
m+l- 1
m+ im+l- 1
m+ i
l
第三章习题解答
5 证 显然,每列中必有两数字相同,共有 ( )种模式,有0或1两种选择.故共有 ( )·2种选择,( )·2=6.现有 7列,
-? = 2.即必有2列在相同的两行选择相同的数字,即有一矩形,四角的数字相等.
( 题目 )
3
23
2
3
27
6
第三章习题解答
6 证 把1×1正方形分成四个-×-的正方形.如下图:
1
2
1
2
则这5点中必有两点落在同一个小正方形内.而小正方形内的任两点的距离都小于
-?212
( 题目 )
第三章习题解答
7 证 把边长为1的三角形分成四个边长为-的三角形,如下图,12
则这5点中必有两点落在同一个小三角形中.
( 题目 )
第三章习题解答
8 证 整数的个位数的可能取值为0,1,
…,9.共10种可能,11个整数中必有
2个数的个位数相同,即这两个数之差能被10整除.
( 题目 )
第三章习题解答
9 证 用反证法。设存在划分
P1∪ P2∪ P3∪ P4∪ P5= [1,326],Pi中无数是两数只差.
= 66,则有一 Pi中至少有 66个数,
A= { a1,…,a 66},a1< a2< ···< a66,
以下按书上 174页的例题证明可得,(题目 )
326
5
第三章习题解答
10 解 按题意可得如下的带禁区的棋盘其中有阴影的表示禁区.
A B C
Ⅰ
Ⅱ
Ⅲ
禁区的棋子多项式为:
R( )
=R( ) R( )
=(1+x)(1+3x+x )
=1+4x+4x + x
故方案数= 3!- 4·2!+4 ·1!- 1 ·0!= 1
2
2 3
( 题目 )
第三章习题解答
11 证 设 m个盒子的球的个数是 a1,…,a m,
各不相等,且有 0≤a1< a2< ···< am,则有
a2≥1,am≥m- 1,故
∑ai≥1+2+…+m - 1=- m(m- 1)
与 n<- m(m- 1)相矛盾!
所以 必有两个盒子的球数相等.
1
2
1
2i=1
m
( 题目 )
第三章习题解答
12 解 ( 1 ) 方案数= (n- 1)! ·2 n
( 2 ) 设第 i个单位的代表相邻的方案集为
Ai,i= 1,2,…,n,
| ∩Ai |= ∑ (- 1 ) ∑ | ∩ Ai |
= ∑ (- 1) ( ) (2n- k- 1)! 2
n n
ni=1 k=0
k=0
I∈ ¢ ( n,k) i∈ I
n
k
k
k k
( 题目 )
第三章习题解答
13 解 令 Dn= n!(1-- + -- ···±- )
( 1 )方案数= Dm( n! )
1
1!
1
2!
1
n!m
( 2 ) ∑ ( ) Dk (n!) Dnmk k m- kk=0
m
( 3 ) Dm Dnm ( 题目 )
第三章习题解答
14 证 每列有 (m+1)行,只有 m种颜色,故一列中必有两格同色.同色的2个格子的行号有 ( )种取法.有 m种色,故有 m( )
种同色模式,现有 m( ) +1列,必有两列的同色模式相同.即由这两列的对应行上有
4个格子同色,正好是一个矩形的4个角上的格子.得证,(题目 )
m+1
2
m+1
2m+1
2
第三章习题解答
15 解 第一门课的顺序有 6!种第二门课的顺序有:
D6= 6! ( ---+---+- )= 265
古总顺序有 6!× 265种,( 题目 )
1
2!
1
3!
1
4!
1
5!
1
6!
第三章习题解答
16 解 任一点的坐标( a,b) 只有如下4
种可能,(奇数,偶数 ),(奇数,奇数 )、
(偶数,奇数 ),(偶数,偶数 )。因而 5个点中必有两个点模 2的格式一样.设
2| (x1- x2),2| (y1- y2)即 x1- x2= 2k
y1- y2=2 l,则三角形面积
S△ =- 1 1 1x1 x2 x3
y1 y2 y3
0 1 1
x1- x2 x2 x3
y1 - y2 y2 y3
1
2 =- 12
0 1 1
k x2 x3
l y2 y3
=
是整数,( 题目 )
第三章习题解答
17 解 设 (x,y)是整点,每个分量 模 3后有如下表的结果:
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
若有3个点模3后的结果落在上表中的同一格中,则这3个点的重心是整点.
第三章习题解答若有3点占满一行,则3点重心是整点;
有3点占满一列,则3点重心是整点;
若存在一组均匀分布,则有 3点重心是整点.
由上表可知,若只有 8个点,也不能保证有
3点的重心是整点.(因为若每个格子都有
2点,则只占有4个格子,无法保证上面的要求)
下面假设存在9个点,其中任3点的重心都不是整点.
第三章习题解答则这 9个点,至少占有?-?= 5个格子(因为每格中最多有 2个点,否则有 3个点的重心为整点),每行最多有2格,又?-?=3
所以每行都有点.
同理,每列都有点.
9
2
5
2
不妨设第一行 2点,第二行 2点,第三行 1点前 2 行有两种模式,或这样第三行的点无论在哪一列都构成占满第三章习题解答一列或构成一组均匀分布.满足前面说的三点重心是整点的情况.
故 9个点能保证其中存在3个点的重心是整点,( 题目 )
第三章习题解答
某甲和其中每人在会上各相遇 12次,每二人各相遇 6次,每三人各相遇 3次,每五人各相遇 2次,每六人各相遇一次,1人也没有遇见的有 5次,问某甲共参加了几次会议解,...
第三章习题解答
2.求从 1到 500的整数中被 3和 5整除但不被 7整除的数的个数,
解,...
第三章习题解答
3,n代表参加会议,试证其中至少有 2
人各自的朋友数相等。
解,...
第三章习题解答
4,试给出下列等式的组合意义
m
l
l mkn
k
ln
l
m
kn
mn
a
0
,)1( )(
mn
j
j
l
ljmn
j
mn
mn
l
b
0
,
1
)1(
1
1
)(
第三章习题解答
lm
lm
m
lm
m
lm
m
lm
m
lm
c
l
)1(
2
11
1
)(
解,...
第三章习题解答
5.设有 3个 7位的 2进制数解,...
7654321 aaaaaaa
7654321 bbbbbbb
7654321 ccccccc
试证存在整数 i和 j,使得下列之一必然成立。 71 ji
jiji
jijijiji
ccbb
ccaabbaa
,
第三章习题解答
6,在边长为 1的正方形内任取 5个点试证其中至少有两点,期间距离小于解,...
2
2
1
第三章习题解答
7.在边长为 1的等边三角形内任取 5个点试证其中至少有两点,期间距离小于
2
1
解,...
第三章习题解答
8,任取 11个整数,求证其中至少有两个数它们的差是 10的倍数。
解,...
第三章习题解答
9,把从 1到 326的 326个整数任意分为 5个部分,试证其中有一部分至少有一个数是某两个数之和,或是另一个数的两倍。
解,...
第三章习题解答
10,A,B,C三种材料用作产品 I,II、
III的原料,但要求 I禁止用 B,C作原料,
II不能用 B作原料,III不允许用 A作原料,
问有多少种安排方案?(假定每种材料只做一种产品的原料)
解,...
第三章习题解答
11,n个球放到 m个盒子中去,
试证其中必有两个盒子有相同的球数。
)1(2 mmn
解,...
第三章习题解答
12,n各单位各派两名代表去出席一会议。 位代表围一圆桌坐下。试问:
( 1)各单位代表并排坐着的方案是多少?
( 2)各单位的两人互不相邻的方案数又是多少?
解,...
n2
第三章习题解答
13,一书架有 m层,分别放置 m类不同种类的书,每层 n册。先将书架上的图书全部取出清理。清理过程要求不打乱所有的类别。试问
( 1) m类书全不在各自原来层次上的方案数有多少?
( 2)每层的 n本书都不在原来位置上的方案数等于多少?
( 3) m层书都不在原来层次,每层
n本书也不在原来位置上的方案数又有多少? 解,...
第三章习题解答
14,行 列 的格子同种颜色着色,每格赵一种颜色,其中必有一个 4角同色的矩形。
解,...
)1(?m?
1
2
1m
m m
第三章习题解答
15,两名教师分别对 6名学生同时进行两门课程的面试(每名教师各管一门课程)
每名学生每门面试的时间都是半个小时,
共有多少不同的面试顺序?
解,...
第三章习题解答
16,在平面直角坐标系中至少任去多少个整点(两个坐标系都是整数)才能保证其中存在 3个构成三角形(包含 3点在一条直线上)的面积是整数(可以为 0)
解,...
第三章习题解答
17,在平面直角坐标系中至少任去多少个整点才能保证存在 3个点构成的三角形的重心是整点?
解,...
第三章习题解答第三章习题解答
1,解 设 Ai为甲与第 i个朋友相遇的会议集,i= 1,…,6,则
| ∪ Ai|= 12 ( ) - 6 ( )+ 4 ( )
- 3 ( )+ 2 ( )- ( )
= 28
故甲参加会议数为
28+ 5= 33 ( 题目 )
6
1
6
2 63
6
4
6
5
6
6
第三章习题解答
2 解 设 A3,被 3整除的数的集合
A5,被 5整除的数的集合
A7,被 7整除的数的集合所以
| A7∩A5∩A3|
=| A3∩A5|- | A7∩A5∩A3|
=-= 33- 4= 29 ( 题目 )5003·5 5003·5·7
第三章习题解答
3 解 每个人的朋友数只能取 0,1,…,
n- 1,但若有人的朋友数为 0,即此人和其他人都不认识,则其他人的最大取数不超过 n- 2,故这 n个人的朋友数的实际取数只有 n- 1种可能,=2,所以至少有2人的朋友数相等,( 题目 )
n
n- 1
第三章习题解答
4 解 ( a ) 从 n个元素中取 k个元的组合,
总含指定的 m个元的组合数为 ( )=( )
设这 m个元为 a1,a2,…,am,Ai为不含 ai的组合 (子集 ),i=1,…,m.
| Ai| = ( )
| Ai1∩ Ai2∩···∩Ail|= ( )
( )=| ∩ Ai|
= ( ) + ∑ (- 1) ∑ | ∩ Aij |
= ∑(- 1) ( ) ( )
n- 1
k n- l
k
n- m
n- k
n
k
m
i=1m
l=1
l l
j=1{i1,…,i l}∈ ¢ (m,l)
l mk n- l
k
m
l=0
n- m
k- m
n- m
n- k
第三章习题解答
( b )令 k= n- m,l个相同的球放入 k个不同的盒子里.每盒不空的方案数为 ( ).
设 Ai为第 i个盒子为空的方案集,i=1,2,…,k.
| Ai |= ( ),| ∩ Ais | = ( )
( )= | ∩Ai |= ( )
+ ∑ (- 1) ∑ | ∩ Ais |
= ∑(- 1) ( ) ( )
l- 1
k- 1
k- 1+l- 1
l l- 1
k- 1
k- j+l- 1
l
k+l- 1
l
{i1,…,i j}∈ ¢ (k,j)
j
s=1
j
s=1k
i=1k
j=1
j
k
j=0
j k
j
k- j+l- 1
l
第三章习题解答
l个相同的球放入 n个不同的盒子里,指定的 m个盒子为空,其他盒子不空的方案数为 ( )l- 1n- m- 1
第三章习题解答
( c ) 设 Ai为 m+l个元中取 m+i个,含特定元素
a的方案集; Ni为 m+l个元中取 m+i个的方案数.则:
Ni= ( )
| Ai |=( ),| Ai |=( )
| Ai+1 |= | Ai |=( )
| Ai |= Ni- | Ai | i=0,1,…,l.
| A0 |=N0 - | A0 | =N0- | A1 |=N0- (N1- |A1|
=N0- N1+N2- …+( - 1) Nl (题目 )
m+l
m+ im+l- 1
m+ i- 1
m+l- 1
m+ im+l- 1
m+ i
l
第三章习题解答
5 证 显然,每列中必有两数字相同,共有 ( )种模式,有0或1两种选择.故共有 ( )·2种选择,( )·2=6.现有 7列,
-? = 2.即必有2列在相同的两行选择相同的数字,即有一矩形,四角的数字相等.
( 题目 )
3
23
2
3
27
6
第三章习题解答
6 证 把1×1正方形分成四个-×-的正方形.如下图:
1
2
1
2
则这5点中必有两点落在同一个小正方形内.而小正方形内的任两点的距离都小于
-?212
( 题目 )
第三章习题解答
7 证 把边长为1的三角形分成四个边长为-的三角形,如下图,12
则这5点中必有两点落在同一个小三角形中.
( 题目 )
第三章习题解答
8 证 整数的个位数的可能取值为0,1,
…,9.共10种可能,11个整数中必有
2个数的个位数相同,即这两个数之差能被10整除.
( 题目 )
第三章习题解答
9 证 用反证法。设存在划分
P1∪ P2∪ P3∪ P4∪ P5= [1,326],Pi中无数是两数只差.
= 66,则有一 Pi中至少有 66个数,
A= { a1,…,a 66},a1< a2< ···< a66,
以下按书上 174页的例题证明可得,(题目 )
326
5
第三章习题解答
10 解 按题意可得如下的带禁区的棋盘其中有阴影的表示禁区.
A B C
Ⅰ
Ⅱ
Ⅲ
禁区的棋子多项式为:
R( )
=R( ) R( )
=(1+x)(1+3x+x )
=1+4x+4x + x
故方案数= 3!- 4·2!+4 ·1!- 1 ·0!= 1
2
2 3
( 题目 )
第三章习题解答
11 证 设 m个盒子的球的个数是 a1,…,a m,
各不相等,且有 0≤a1< a2< ···< am,则有
a2≥1,am≥m- 1,故
∑ai≥1+2+…+m - 1=- m(m- 1)
与 n<- m(m- 1)相矛盾!
所以 必有两个盒子的球数相等.
1
2
1
2i=1
m
( 题目 )
第三章习题解答
12 解 ( 1 ) 方案数= (n- 1)! ·2 n
( 2 ) 设第 i个单位的代表相邻的方案集为
Ai,i= 1,2,…,n,
| ∩Ai |= ∑ (- 1 ) ∑ | ∩ Ai |
= ∑ (- 1) ( ) (2n- k- 1)! 2
n n
ni=1 k=0
k=0
I∈ ¢ ( n,k) i∈ I
n
k
k
k k
( 题目 )
第三章习题解答
13 解 令 Dn= n!(1-- + -- ···±- )
( 1 )方案数= Dm( n! )
1
1!
1
2!
1
n!m
( 2 ) ∑ ( ) Dk (n!) Dnmk k m- kk=0
m
( 3 ) Dm Dnm ( 题目 )
第三章习题解答
14 证 每列有 (m+1)行,只有 m种颜色,故一列中必有两格同色.同色的2个格子的行号有 ( )种取法.有 m种色,故有 m( )
种同色模式,现有 m( ) +1列,必有两列的同色模式相同.即由这两列的对应行上有
4个格子同色,正好是一个矩形的4个角上的格子.得证,(题目 )
m+1
2
m+1
2m+1
2
第三章习题解答
15 解 第一门课的顺序有 6!种第二门课的顺序有:
D6= 6! ( ---+---+- )= 265
古总顺序有 6!× 265种,( 题目 )
1
2!
1
3!
1
4!
1
5!
1
6!
第三章习题解答
16 解 任一点的坐标( a,b) 只有如下4
种可能,(奇数,偶数 ),(奇数,奇数 )、
(偶数,奇数 ),(偶数,偶数 )。因而 5个点中必有两个点模 2的格式一样.设
2| (x1- x2),2| (y1- y2)即 x1- x2= 2k
y1- y2=2 l,则三角形面积
S△ =- 1 1 1x1 x2 x3
y1 y2 y3
0 1 1
x1- x2 x2 x3
y1 - y2 y2 y3
1
2 =- 12
0 1 1
k x2 x3
l y2 y3
=
是整数,( 题目 )
第三章习题解答
17 解 设 (x,y)是整点,每个分量 模 3后有如下表的结果:
(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)
若有3个点模3后的结果落在上表中的同一格中,则这3个点的重心是整点.
第三章习题解答若有3点占满一行,则3点重心是整点;
有3点占满一列,则3点重心是整点;
若存在一组均匀分布,则有 3点重心是整点.
由上表可知,若只有 8个点,也不能保证有
3点的重心是整点.(因为若每个格子都有
2点,则只占有4个格子,无法保证上面的要求)
下面假设存在9个点,其中任3点的重心都不是整点.
第三章习题解答则这 9个点,至少占有?-?= 5个格子(因为每格中最多有 2个点,否则有 3个点的重心为整点),每行最多有2格,又?-?=3
所以每行都有点.
同理,每列都有点.
9
2
5
2
不妨设第一行 2点,第二行 2点,第三行 1点前 2 行有两种模式,或这样第三行的点无论在哪一列都构成占满第三章习题解答一列或构成一组均匀分布.满足前面说的三点重心是整点的情况.
故 9个点能保证其中存在3个点的重心是整点,( 题目 )
第三章习题解答