(完整word版)组合数学课后答案1.pdf

《(完整word版)组合数学课后答案1.pdf》由会员分享，可在线阅读，更多相关《(完整word版)组合数学课后答案1.pdf（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、习题二 证明：证明：在一个至少有在一个至少有 2 2 人的小组中，人的小组中，总存在两个人，总存在两个人，他们在组内所认识的人数相同。他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为1,n-1，由鸽巢原理知，n个人认识的人数有 n-1种，那么至少有 2 个人认识的人数相同。假设有 1人谁都不认识：那么其他 n-1人认识的人数都为1,n-2，由鸽巢原理知，n-1个人认识的人数有 n-2种，那么至少有 2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为 0 的至少有两人。任取任取 1111 个整数，求证其中至少有两个数的差是个整数，求证其中至少有两个数的

2、差是 1010 的整数倍。的整数倍。证明：对于任意的一个整数，它除以 10的余数只能有 10 种情况：0，1，9。现在有有 11 个整数，由鸽巢原理知，至少有 2 个整数的余数相同，则这两个整数的差必是 10 的整数倍。证明：平面上任取证明：平面上任取 5 5 个坐标个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有5 个坐标，每个坐标只有 4 种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两

3、点连线的坐标之和为偶数。因为 奇数+奇数=偶数；偶数+偶数=偶数。因此只需找以上 2 个情况相同的点。而已证明：存在至少 2个坐标的情况相同。证明成立。一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有至少有多少人参加才能保证必有 100100 个人得到相同的结果个人得到相同的结果证明：根据推论 2.2.1，若将3*（100-1）+1=298个人得到 3种结果，必有 100 人得到相同结果。一个袋子里装了一个袋子里装了 100100个苹果、个苹果、100100 个香

4、蕉、个香蕉、100100 个橘子和个橘子和 100100 个梨。那么至少取出多少水果后能够保证已经拿个梨。那么至少取出多少水果后能够保证已经拿出出 2020 个相同种类的水果个相同种类的水果证明：根据推论 2.2.1，若将 4*（20-1）+1=77个水果取出，必有 20个相同种类的水果。证明：在任意选取的证明：在任意选取的 n n+2+2 个正整数中存在两个正整数，其差或和能被个正整数中存在两个正整数，其差或和能被 2 2n n 整除。（书上例题整除。（书上例题2.1.32.1.3）证明：对于任意一个整数，它除以 2n 的余数显然只有 2n种情况，即：0，1，2，2n-2，2n-1。而现在有

5、任意给定的n+2个整数，我们需要构造n+1个盒子，即对上面2n 个余数进行分组，共 n+1组：0,1，2n-1,2，2n-2,3,2n-3,，n-1,n+1，n。根据鸽巢原理，n+2 个整数，必有两个整数除以 2n 落入上面 n+1 个盒子里中的一个，若是0或n则说明它们的和及差都能被 2n整除；若是剩下 n-1组，因为一组有两个余数，余数相同则它们的差能被 2n 整除，不同则它们的和能被 2n整除。证明成立。一个网站在一个网站在 9 9 天中被访问了天中被访问了 18001800 次，证明：存在连续的次，证明：存在连续的 3 3 天，这个网站的访问量超多天，这个网站的访问量超多 600600

6、次。次。证明：设网站在 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 由推论 2.2.2知，b1，b2，b3 中至少有一个数大于等于 600。所以存在有连续的三天，访问量大于等于 600次。将一个矩形分成将一个矩形分成 5 5 行行 4141 列的网格，每个格子涂列的网格，每个格子涂 1 1 种颜色，有种颜色，有 4 4 种颜色可以选择，证明：种颜色可以选择，证明：无论怎样涂色，无论怎样涂色，其中必有一个由格子构成的矩形的其中必有一个由格子构成的矩

7、形的 4 4 个角上的格子被涂上同一种颜色。个角上的格子被涂上同一种颜色。证明：首先对一列而言，因为有 5 行，只有 4只颜色选择，根据鸽巢原理，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有5=10=10 种，这样一列中两个同色单元2格的位置组合共有 10*4=40种情况。而现在共有 41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格子是同一颜色。将一个将一个矩形分成矩形分成(m m+1)+1)行行mm121列的网格每个格子涂列的网格每个格子涂 1 1 种颜色，有种颜色，有 mm种颜色可以选择，证明：种颜色可以选择，证明：无论

8、怎么涂色，无论怎么涂色，其中必有一个由格子构成的矩形的其中必有一个由格子构成的矩形的 4 4 个角上的格子被涂上同一种颜色。个角上的格子被涂上同一种颜色。证明：（1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。（2）每列中两个单元格的不同位置组合有m1种，这样一列中两个同色单元格的位置组2合共有m1m种情况（3）现在有mm122结论成立。1列，根据鸽巢原理，必有两列相同。证明一名实验员在一名实验员在 5050 天里每天至少做一次实验，而实验总次数不超过天里每天至少做一次实验，而实验总次数不超过 7575。证明一定存在连续的。证明一定存在连续的若干天，她正好做

9、了若干天，她正好做了 2424 次实验。次实验。证明：令 b1，b2，.，b50 分别为这 50 天中他每天的实验数，并做部分和a1=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)个大圆

10、的基础上，在球面上再加上第n+1个大圆时，它同前n个大圆共得到 2n 个交点(因无三个大圆相交于一点)，而每增加一个交点就增加一个新的面，故共增加 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)有 D1D1 与与 Dn-1Dn-1 同色，同色，此时此时 DnDn 有有 k-1k-

11、1 种方案，种方案，可将可将 D1D1 与与 D n-2D n-2看成相邻区域，则看成相邻区域，则D1,D2,DnD1,D2,Dn-2-2 的着色方案为的着色方案为 f(n-2)f(n-2)。D1D1 与与Dn-1Dn-1异色，异色，此时此时 DnDn有有 k-2k-2种方案，种方案，可将，可将，则则 D1,D2,DnD1,D2,Dn-1-1的着色方案为的着色方案为 f(n-1)f(n-1)。(k-1)f(n-2)+(k-2)f(n-1)(k-1)f(n-2)+(k-2)f(n-1)另另有有：n-1n-1f(n)=k(k-1)f(n)=k(k-1)-f(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 时