组合数学引论课后答案部分.doc

《组合数学引论课后答案部分.doc》由会员分享，可在线阅读，更多相关《组合数学引论课后答案部分.doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学引论课后答案习题一1.1 任何一组人中都有两个人，它们在该组内认识的人数相等。1.2 任取11个整数，求证其中至少有两个数，它们的差是10的倍数1.3 任取n+1个整数，求证其中至少有两个数，它们的差是n的倍数1.4 在1.1节例4中证明存在连续的一些天，棋手恰好下了k盘棋(k=1,2,，21).问是否可能存在连续的一些天，棋手恰好下了22盘棋1.5 将1.1节例5推广成从1,2，2n中任选n+1个数的问题1.6 从1,2,200中任取100个整数，其中之一小于16，那么必有两个数，一个能被另一个整除1.7 从1,2,200中取100个整数，使得其中任意两个数之间互相不能整除1.8 任

2、意给定52个数，它们之中有两个数，其和或差是100的倍数1.9 在坐标平面上任意给定13个整点（即两个坐标均为整数的点），则必有一个以它们中的三个点为顶点的三角形，其重心也是整点。1.10 上题中若改成9个整点，问是否有相同的结论？试证明你的结论1.11 证明：一个有理数的十进制数展开式自某一位后必是循环的。1.12 证明：对任意的整数N，存在着N的一个倍数，使得它仅有数字0和7组成。（例如，N=3,我们有;N=4,有;N=5,有;）(1) 在一边长为1的等边三角形中任取5个点，则其中必有两个点，该两点的距离至多为；(2) 在一边长为1的等边三角形中任取10个点，则其中必有两个点，该两点的距离

3、至多为；(3) 确定，使得在一边长为1的等边三角形中任取个点，则其中必有两个点，该两点的距离至多为；1.13 一位学生有37天时间准备考试，根据以往的经验，她知道至多只需要60个小时的复习时间，她决定每天至少复习1小时，证明：无论她的复习计划怎样，在此期间都存在一些天，她正好复习了13个小时。1.14 从1,2,2n中任选n+1个整数，则其中必有两个数，它们的最大公约数为1出的数属于同一个鸽巢，即它们的最大公约数为11.15 针对1.1节的例6，当m,n不是互素的两个整数时，举例说明例中的结论不一定成立习题二2.1 证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明

4、：假设没有人谁都不认识：那么每个人认识的人数都为1,n-1，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为1,n-2，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。第 18 页2.2 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。2.3 证明：平面上任取5个

5、坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。2.4 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1

6、=298个人得到3种结果，必有100人得到相同结果。2.5 一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。2.6 证明：在任意选取的n+2个正整数中存在两个正整数，其差或和能被2n整除。（书上例题2.1.3）证明：对于任意一个整数，它除以2n的余数显然只有2n种情况，即：0，1，2，2n-2，2n-1。而现在有任意给定的n+2个整数，我们需要构造n+1个盒子，即对上面2n个余数进行分组，共n+1组：0,1，2n-1

7、,2，2n-2,3,2n-3,，n-1,n+1，n。根据鸽巢原理，n+2个整数，必有两个整数除以2n落入上面n+1个盒子里中的一个，若是0或n则说明它们的和及差都能被2n整除；若是剩下n-1组，因为一组有两个余数，余数相同则它们的差能被2n整除，不同则它们的和能被2n整除。证明成立。2.7 一个网站在9天中被访问了1800次，证明：存在连续的3天，这个网站的访问量超多600次。证明：设网站在9天中访问数分别为a1，a2，.，a9 其中a1+a2+.+a9 = 1800，令a1+a2+a3 = b1，a4+a5+a6 = b2，a7+a8+a9 = b3因为（b1+b2+b3）/3 = 600

8、由推论2.2.2知，b1，b2，b3中至少有一个数大于等于600。所以存在有连续的三天，访问量大于等于600次。2.8 将一个矩形分成5行41列的网格，每个格子涂1种颜色，有4种颜色可以选择，证明：无论怎样涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。证明：首先对一列而言，因为有5行，只有4只颜色选择，根据鸽巢原理，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有=10种，这样一列中两个同色单元格的位置组合共有10*4=40种情况。而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。2.

9、9 将一个矩形分成(m+1)行列的网格每个格子涂1种颜色，有m种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。证明：（1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。（2）每列中两个单元格的不同位置组合有种，这样一列中两个同色单元格的位置组合共有 种情况（3）现在有列，根据鸽巢原理，必有两列相同。证明结论成立。2.10 一名实验员在50天里每天至少做一次实验，而实验总次数不超过75。证明一定存在连续的若干天，她正好做了24次实验。证明：令b1，b2，.，b50 分别为这50天中他每天的实验数，并做部分和a1 =

10、 b1，a2 = b1+b2 ，。a50 = b1+b2+.+b50 .由题，bi=1(1=i=50)且a50=75所以 1=a1a2a3a50=75 (*)考虑数列 a1，a2，.，a50，a1+24，a2+24，a50+24，它们都在1及75+24=99之间。由鸽巢原理知，其中必有两项相等。由（*）知，a1，a2，.，a50互不相等，从而a1+24，.a50+24 也互不相等，所以一定存在1=ij1,f(1)=2，f(n)可以由f(n)来生成，当在f(n)个大圆的基础上，在球面上再加上第n+1个大圆时，它同前n个大圆共得到2n个交点(因无三个大圆相交于一点)，而每增加一个交点就增加一个新的

11、面，故共增加2n个面。所以有f(n+1)= f(n)+2n。设P是平面上n个连通区域D1,D2,Dn的公共交界点，如下图所示。现用k种颜色对其着色，要求有公共边界的相邻区域着以不同的颜色，令f(n)表示不同的着色方案。求它所满足的递推关系。有： f(n)= (k-1)f(n-2)+(k-2)f(n-1)（n4）f(2)=k(k-1) f(3)=k(k-1)(k-2)(1) 有D1及Dn-1同色，此时Dn有k-1种方案，可将D1及D n-2看成相邻区域，则D1,D2, , Dn-2的着色方案为f(n-2)。(2) D1及Dn-1异色，此时Dn有k-2种方案，可将，则D1,D2, , Dn-1的着色方案为f(n-1)。(k-1)f(n-2)+(k-2)f(n-1)另有：f(n)=k(k-1)n-1-f(n-1)第七章例n种颜色涂色装有7颗珠子的手镯，如果只考虑手镯的旋转，求有多少种涂色方案？解 对象集D1,2,3,4,5,6,7，颜色集是R(1,2,3,n)，D上的置换群Gg0,g1,g2,g6，其中gi表示旋转360*i/7，因7是质数，所以除(g0)7外，其它(gi)1，(i=1,2,3,4,5,6)，代入Polya公式，得L1/7*n7+6n而四边形：转180时P22 6,8,9