组合数学与图论复习题及答案
1.Show that if n+1 integers are chosen form the set {1,2,…,2n},then there are
always two which differ by at most 2.
从{1,2,…,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。
任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中, 所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k 大的另一个数。
2.Show that for any given 52 integers there are exist two of them whose sum, or
else difference, is divisible 100.
设52个整数a1，a2，…，a52被100除的余数分别是n,r2,…”2，而任意一个数被100除余数为0, 1, 2，…，99, 一共100个。他们可以分为51个类
{0},{1,99},{2,98},…,{49,51},{50}。将这51 个集合视为鸽笼，则将r1,r2,…,r52 放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri = rj，要么有ri + rj =100，也就是说ai—aj|100或者ai+ aj|100。
3.从1，2，3,…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互
质。
鸽子洞原理，必有两个数相邻，相邻的两个数互质
4.Prove that Ramsey number R(p,辱R(p,q-1)+R(p-1,q).
令N= R；p,q-1)+R(p-1,q),从N个人中中随意选取一个a, F表示与a相识的人，S表示与a不相识的人。
在剩下的R(p,q-1)+R(p-1,q) —2+ 1个人中，由鸽子洞原理有，或者F中有
R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p 个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)w R(p,q-
1)+R(p-1,q)
5.There are 10 people, either there are 3 each pair of whom are
acquainted, or there are 4 each pair of whom are unacquainted 。
从10人中随意选一个人p, F表示与p相识的人，S表示与p不相识的人
若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p 有 3 人相识，也满足题设。
若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相
识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6.In how manyways can six menand six ladies be seated at round table
if the men and ladies to sit in alternate seats?
6 个男的先进行圆排列，然后 6 个女的插入空位。
7.In how manyways can 15 people be seated at round table if B refuses to sit next
to A? What if B only refuses to sit on A right?
A. 15个人进行圆排列，减去ab组成一个元素的14人的圆排列，然后减
去ba 组成一个元素的14 人的圆排列。
B. 15 个人进行圆排列，减去ab 组成一个元素的14 人的圆排列。
8. Determine the number of 10-combinations of the multiset
S={ *a,4.b,5*c,7*d} 。
(1+x+x2+x3+…)(1+x+x2+…+X4) ( 1+x+x2+ …+X5) ( 1+x+x2+…+X7)展开
9. 把n 个有编号的球放入m 个有编号的盒子中，不允许有空盒子，有多少种放
法。
先假设，盒子没有编号，然后乘上组合与排列的关系：m!* S2 (n, m)
10. 证明在n(n 2)个人中总有两个人，他们在这群人中所认识的人数目相同。
当n=2时，如果两个人相互认识，则每个人认识的人只有一个；如果不认
识，则每个人认识的人为0 个。
当n>2时，设x i (x=1,2,…,n)表示，第i个人认识的人的数目。(每个人最多
只能认识n-1 个人。)
A. 如果每个人都有熟人
那么由鸽子洞原理知道至少有两个人i和j认识的人数相同即x= x j
B. 如果只有一个人没有认识的人
那么对于剩下的n－1 个人来说能认识的人对多只有n－2 个，由鸽子
洞原理知道，这n－1 个人中至少有两个人i 和j 认识的人数一样即x i
= x j
C. 如果至少有两个人都没有熟人，则满足题设。
11 . 一个剧团演出11 周，为保证收入和不至于太累，规定每天至少演出一场，每
周不超过12 场。证明存在连续的若干天，恰好演出21 场。
设a i为第一天该剧团的演出的次数，a i表示前i天一共的演出次数。可知道
a是单调递增的。且有a i>=1,a77<=132。于是有a+ 21(i=1,2,…,77)，也是
单调递增的。而a77+ 21<=153。则有154个在1到153之间，所以由鸽子
洞原理知道，至少存在两个数a i和a有a= a + 21即a i —a j = 21 12. 在边长为1 的正三角形中任选5 个点，证明必有两个点的距离不超过1/2
如上图所示，将这个正三角形分割成4个小的正三角形，有每个小正三角
形的边长为1/2。将5个点放入这4个小三角形，由鸽子洞原理有一个三角
形部有2个点，因为小三角形的边长为1/2,所以这两个点的最大距离为
1/2。
13. 设a i，a2，a3，，an是1，2，3，，n的一个排列，证明当n是奇数时，
乘积(a1-1) (a2-2) (a3-3) (a n-n)是偶数。
假设，当n为奇数时A =( a1-1) (a2-2) (a3-3) (a n-n)是奇数，贝U：
(a -i)均为奇数，否则A为偶数。也就是说当i为奇数时a必须为偶
数；因为n为奇数，所以从1到n的偶数数目为(n-1) /2，奇数数目为
(n+1) /2,所以由鸽子洞原理可以知道当i为奇数时，至少有一个(a i -i) 为偶
数，所以 A =( a1-1) (a2-2) (a3-3) (a n-n)是奇数。
14. 有100个人的舞会，每个人的舞伴数都是偶数，证明必有3个人有相同的
舞伴数。
由于每个人的舞伴数是偶数个，所以可能有的舞伴数为0, 2, 4, 6, 8,…,
98。共有50种可能。
A. 如果每个人都有舞伴，可能的舞伴数为2, 4,…，98。共49种可能，
相当于把100个球放入49个篮子中，由鸽子洞原理知道至少有一个篮子有
3个球以上，也就是说有3个人有相同的舞伴数。
B. 如果只有一个人没有舞伴，剩下的人可能的舞伴数为2, 4, (98)
共49种可能，相当于把99个球放入49个篮子中，由鸽子洞原理知道至少
有一个篮子有3个球，也就是说有3个人有相同的舞伴数。
C. 如果有两个人没有舞伴，剩下的人可能的舞伴数为2, 4, 6, (96)
共48中可能。相当于把98个球放入48个篮子中，由鸽子洞原理知道至少
6有一个篮子有3个球以上，也就是说有3个人有相同的舞伴数。
D. 如果有至少3个人没有舞伴，则有3个人的舞伴数为0
15. N个质点排成一列，涂以红、白、黑三种色，每点涂一色，要求同色的点为偶
数，有多少种？
(1+x2+x4+…)3=( —)3= C(3 r 1, r)x2r
1 X r 0
16. 有两堆石块，每一石块的重量都小于n kg(Z)，每一堆中的石块重量互不相同
(规定石块重量为整数)。证明，如果两堆石块的总数不少于n,那么总可以从两堆中分别选出一块，使两者的总重量是nkg。
石块按重量可以分成这样几类：
{1,n-1},{2,n-2},{3,n-3},…,{ n/2 , n/2 }，共n/2 个集合。
假定第一堆石头有p块，第二堆有q块，由题意有p+q>=n。两堆石头关系
等价，所以下面以第一堆为参照。
A . 考虑第一堆石头都集中在k 类集合里面 (除去单出来的石头外，其他石头都两两在
一起)。此时如果第二堆石头里面有分布在k 类集合中的元素，则肯定有满足题意的
来自两堆石头的两块石头；如果先让第二堆石头分布满在其他的
n/2 —k个集合，因为每堆中石块重量不同，那么现在一共有n—1或n —2
块石头分布在集合中，第二堆就多出了1或2个石头，那么这1或2个石头肯定是在
前面的k 个集合中，所以这也有满足题意的两块石头。
B.如果第一堆石头分布在i (i从k到p)个集合中，同样，显然第二堆
石头分布满剩下的n/2 —i 个集合，由于每堆中石块重量都不一样，所以
第二堆将会多出q＋2*i—2* n/2 块石头，那么这些多出来的石头，肯定会分布在第
一堆石头所在的i 个集合中，所以有满足题意的两块石头。
17. 在9 个人中，或者有3人相互认识，或者有4 人相互不认识。
N(3,4) <= N(2,4)+N(3,3)因为N(2,4)和N(3,3)都为偶数，所以有：
N(3,4) <= N(2,4)+N(3,3)-1 = 4+6-1=9
18. 证明当R(p，q-1)和R(p-1，q)都是偶数时，R(p，q) R(p，q-1)+R(p-1，q)-1。
19. 把n 个球放入k 个盒子，分别考虑球有无编号，盒子有无编号，以及盒子可
否空 3 种情况下的配置数。
A. n 个球无编号，k 个盒子也没有编号，允许为空
F(k,n)/K! 首先认为盒子是有编号的，然后去掉盒子的编号
B. n 个球无编号，k 个盒子也没有编号，不允许为空：在每个盒子中先放
一个球，剩下n-k个球，任意放。
F(k,n-k)/K! 首先认为盒子是有编号的，然后去掉盒子的编号。
D. n个球无编号，k个盒子有编号，允许空
F(k,n)=C(k+n-1, n)
E. n个球无编号，k个盒子有编号，不允许空
在每个盒子中先放一个球，剩下n- k个球，任意放。
F(k,n-k)=C( n-1, n-k)
F. n个球有编号，k个盒子无编号，允许空
k
S2( n,i)
i 1
F. n个球有编号，k个盒有无编号，不允许空
S2( n,k)
G. n个球有编号，k个盒有有编号，允许空
先认为盒子没有编号，然后再乘上每次取盒子的方法数。
k
C(k,i)S2( n,i)
i 1
H. n个球有编号，k个盒有有编号，不允许空
先认为盒子没有编号，然后再乘上给盒子编号的方法数。
K!S2( n,k)
20. 将n个元素的集合划分为非空子集，有多少种？可能的划分成的集合数有：
1，2，3，…，n。
相当于将n个球，分别放入以上数字的篮子中的放法，然后求和。有:
n
S
2(n,k)(球有编号的时候)
k 1
F(k,n)
k!(球无序的时候)
21. 设有重量分别为1克，2克，3克，5克，7克的5个砝码，可以称多少种不同
重量的物体。
(1+x)(1+x2)(1+x3)(1+x5)(1+x7)展开看有多少项。
22. 有A，B，C，D四位教师和1，2，3，4四门课程，已知A和D不能教1 和4,
B不能教3, C不能教2和3。为每位教师恰好安排一门课程的方式有多少
种。
1
2 3 4 A
B
C
D
N = 4!-7*3!+15*2!-10*1!+2*0!=4
23. 设有多重集B={ ? 0, ? 1, ? 2, ? 3},可以组成长为r , 0出现偶
数次的数字串有多少个。(限制排列问题)
2’ 4 2’ 3 3 1
r (r 2)(r r (1+x +x + …)(1+x +x + …)= 4
(( 1) )x
(1 x) (1 x) r 0 2 24. 10个人圆桌会议，休会后重新入座，每个人都不与原先的人相邻的坐法有
多少种。
题目得条件时每个人都不与原先的人相邻，即是说新的圆排列中不出现
123, 234, 345,…，(n-2)(n-1)n , (n-1)n1, n12,这些情况。
设pi 表示圆排列具有i(i+1)(i+2)这一性质的，Ai 表示具有pi 这一性质的 圆排
列的集合。
n-2个元素进行圆排列|A1| = (n-3)!,…，|Ai| = (n-3)! 对于 |A1 n A2| = (n-
4)!,…，|Ai n Ai+1| = (n-4)!
N=(n-1)! -C(n,1)(n-3)! + C(n,2)(n-5)! + … 一直到 C(n,n)
25. 求解递推方程
①-f(n)=2f(n/2)+C
n>1 .f(1)=C
)+R(
r ar = ( 1)
(r 2)(r 1) 2
n=1
xR(
4
设n=2k,C为常数
f(n )=2f( n/2)+C
2f(n /2)=4f( n/4)+2C
4f(n /4)=8f( n/8)+4C
2k-1(n/2k-1)=2k f(n/2 k)+2k-1C
将上面的各等式，左右相加得：
f(n)=C+2C+ …+2k-1 C+2f(n/2 k)= C+2C+…+2k-1 C+2C
二C* k 2i=C*(2K+ 1-1)
i 0
② H( n)=4H( n-1)-4H( n-2) n>1
-H(0)=0 , H(1)=1
特征方程为x2-4x+4=0
解为二重根：q i=q2=2
通解表示为：H F C*2n+C* n2n
由H(0)=0, H(1)=1 有：
I' C i+0*C2=0
C i*2+Q*2=1
解得:C i=0 C 2=1/2
H F n*2n-1
26. 在r位二进制序列里，使数字0不相邻的序列有多少个(用递推方程)？
前一位的0和1都会允许后一位为1，前一位为1后一位允许为0。所以设
f(x)表示x位的满足条件的序列的个数，有：
f(x) = f(x-1)+f(x-2) //f(x-1) 表示f(x)中第x 位为1 的序列数
//f(x-2) 表示f(x)中第x位为0的序列数f(1) = 2 f(2) = 3
"5 3 5(1 5)n 5 3 5(1 5)n
10 2 10 2
27. KrF E=E U E2，E1G 吕=①。 ① 证明n>11, 若G1 是平面图，则G2 不是。
相关主题
文本预览