吉林大学组合数学习题答案.pdf

习题二习题二习题二习题二 2.12.12.12.1 证明：在一个至少有证明：在一个至少有 2 2 2 2 人的小组中，总存在两个人，他们在组内所认识的人数相同。人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为1,n-1，由鸽巢原理知，n 个人认识的人数有 n-1 种，那么至少 有 2 个人认识的人数相同。 假设有 1 人谁都不认识：那么其他 n-1 人认识的人数都为1,n-2，由鸽巢原理知，n-1 个人认识的人数有 n-2 种，那么至 少有 2 个人认识的人数相同。 假设至少有两人谁都不认识，则认识的人数为 0 的至少有两人。 2.22.22.22.2 任取任取 11111111 个整数，求证其中至少有两个数的差是个整数，求证其中至少有两个数的差是 10101010 的整数倍。的整数倍。 证明：对于任意的一个整数，它除以 10 的余数只能有 10 种情况：0，1，9。现在有有 11 个整数，由鸽巢原理知，至少 有 2 个整数的余数相同，则这两个整数的差必是 10 的整数倍。 2.32.32.32.3 证明：平面上任取证明：平面上任取 5 5 5 5 个坐标为整数个坐标为整数的的点，点，则则其中至少有两个点，由它们所连线段的中点其中至少有两个点，由它们所连线段的中点的坐标也是整数的坐标也是整数。 2.3 证明： 有 5 个坐标，每个坐标只有 4 种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由 鸽巢原理知，至少有 2 个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+ 奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上 2 个情况相同的点。而已证明：存在至少 2 个坐标的情况相同。证明 成立。 2.42.42.42.4 一次选秀活动一次选秀活动，每个人表演后可能得到的结果分别为每个人表演后可能得到的结果分别为“通过通过”、“淘汰淘汰”和和“待定待定”，至少有多少人参加才能保证必至少有多少人参加才能保证必 有有 100100100100 个人得到相同的结果？个人得到相同的结果？ 证明： 根据推论 2.2.1，若将 3*（100-1）+1=298 个人得到 3 种结果，必有 100 人得到相同结果。 2.52.52.52.5 一个袋子里装了一个袋子里装了 100100100100 个苹果个苹果、100100100100 个香蕉个香蕉、100100100100 个橘子和个橘子和 100100100100 个梨个梨。那么至少取出多少水果后能够保证已经拿出那么至少取出多少水果后能够保证已经拿出 2 2 2 20 0 0 0 个个 相同种类的水果？相同种类的水果？ 证明： 根据推论 2.2.1，若将 4*（20-1）+ 1 = 77 个水果取出，必有 20 个相同种类的水果。 2.62.62.62.6 证明：在任意选取的证明：在任意选取的n n n n+2+2+2+2 个正整数中存在两个正整数，其差或和能被个正整数中存在两个正整数，其差或和能被 2 2 2 2n n n n整除。整除。（书上例题（书上例题 2.1.32.1.32.1.32.1.3） 证明：对于任意一个整数，它除以 2n 的余数显然只有 2n 种情况，即：0，1，2，2n-2，2n-1。而现在有任意给定的 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 整 除。证明成立。 2.72.72.72.7 一个网站在一个网站在 9 9 9 9 天中被访问了天中被访问了 1800180018001800 次，证明：存在连续的次，证明：存在连续的 3 3 3 3 天，这个网站的访问量超多天，这个网站的访问量超多 600600600600 次。次。 证明： 设网站在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次。 2.82.82.82.8 将一个矩形分成将一个矩形分成 5 5 5 5 行行 41414141 列的网格，每个格子涂列的网格，每个格子涂 1 1 1 1 种颜色，有种颜色，有 4 4 4 4 种颜色可以选择，证明：无论怎样涂色，其中必有一种颜色可以选择，证明：无论怎样涂色，其中必有一 个由格子构成的矩形的个由格子构成的矩形的 4 4 4 4 个角上的格子被涂上同一种颜色。个角上的格子被涂上同一种颜色。 证明：首先对一列而言，因为有5行，只有4只颜色选择，根据鸽巢原理，则必有两个单元格的颜色相同。另外，每列中两 个单元格的不同位置组合有( ) 5 2 =10=10=10=10种，这样一列中两个同色单元格的位置组合共有10*4=40种情况。 而现在共有41列，根据鸽巢原理，无论怎样涂色，则必有两列相同，也就是必有一个由格子构成的矩形的4个角上的格 子是同一颜色。 2.92.92.92.9 将一个矩形分成将一个矩形分成( ( ( (m m m m+1)+1)+1)+1)行行 () 1 1 2 m m + +列的列的网格每个格子涂网格每个格子涂 1 1 1 1 种颜色种颜色，有有 mmmm 种颜色可以选择种颜色可以选择，证明证明：无论怎么涂色无论怎么涂色， ， 其中必有一个由格子构成的矩形的其中必有一个由格子构成的矩形的 4 4 4 4 个角上的格子被涂上同一种颜色。个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有( ) 1 2 m+ 种，这样一列中两个同色单元格的位置组合共有( ) 1 2 m m + 种情况 （3）现在有 () 1 1 2 m m + +列，根据鸽巢原理，必有两列相同。证明结论成立。 2.102.102.102.10 一名实验员在一名实验员在 50505050 天里每天至少做一次实验，而实验总次数不超过天里每天至少做一次实验，而实验总次数不超过 75757575。证明一定存在连续的若干天，她正好做了。证明一定存在连续的若干天，她正好做了 2 2 2 24 4 4 4 次实验。次实验。 证明：令b1，b2，.，b50 分别为这50天中他每天的实验数，并做部分和 a1 = b1，a2 = b1+b2 ，。 a50 = b1+b2+.+b50