组合数学复习资料前两章(共4页)

1、精选优质文档-倾情为你奉上专心-专注-专业组合数学复习资料第一章 什么是组合数学略第二章鸽巢原理2.1 鸽巢原理：简单形式鸽巢原理的简单形式：若在 n 个盒子中放有 n+1 个物件，则至少有一个盒子中放有两个或更多的物体。应用 1，应用 2（对应第 4 题），应用 3（略），应用 4（对应第 1 题），应用 5（对应第7 题），应用 6（略）。课后题第 1 题题目：关于本节中的应用 4，证明对于每个 k=1，2，21 存在连续若干天，在此期间国际象棋大师将恰好下完 k 局棋（情形 k=21 是在应用 4 中处理的情况）。能否论断：存在连续若干天，在此期间国际象棋大师将恰好下完 22 局棋？解答

2、：令是在第一天所下的盘数，是第一天和第二天所下的总盘数，以此类推，是12前 n 天所下的总盘数。由于每天至少要下一盘棋，故数值序列是一个严格1，2，77精选优质文档-倾情为你奉上专心-专注-专业递增的序列，即数列的每一项大于它前面的那一项。此外，而且由于每周下棋最1 1多 12 盘，。因为，我们有。77 12 11 = 1321 1 2 77 132同样，序列也是一个严格递增序列：1+ ，2+ ，77+ 1 + 1+ 2+ 77+ 132 + 。于是，这个数中每一个都是77 2 = 1541，2，77，1+ ，2+ ，77+ 1，132+k内的一个整数。区间内共有 132+k 个整数，故当 1

3、32+k154 时，即 k22 时，根据鸽巢原理的简单形式，这 154 个数中至少存在一对相等的数。若则无法断定至 22少存在一对相等的数。又因为数值序列和都是严格递增的，所以不存1，2，771+ ，2+ ，77+ 在相等的 2 个数，所以相等的 2 个数必然分别属于 2 个数值序列。则存在，1 77使得，也就是说从第 i+1 天至第 j 天，这位大师一共下了 k 盘棋。= + 即 = 所以命题“对于每个 k=1，2，21 存在连续若干天，在此期间国际象棋大师将恰好下完k 局棋”成立。对于 k=22 的情况，无法论断。课后题第 4 题题目：证明，如果从集合1，2，.，2n中选择 n+1 个整数

4、，那么总存在两个整数，他们之间相差为 1。解答：对于集合1，2，.，2n可以划分为 n 个互不相交的子集：1，2，3，4，.，2n-1，n，且这些子集包含了原集合的全部元素。故从原集合中选择 n+1 个整数，等精选优质文档-倾情为你奉上专心-专注-专业价于从这 n 个子集中选择 n+1 个整数。根据鸽巢原理的简单形式，必然存在 2 个选择出的整数属于同一个子集，它们之间相差为 1。证毕。课后题第 7 题题目：证明，对任意给定的 52 个整数，存在其中的两个整数，要么两者的和能被 100 整除，要么两者的差能被 100 整除。解答：对于任意的一个整数，可以写成的形式，其中 k 为任意整数，a 为

5、100k+ a的整数。则 a 有 0，1，2，.，99 这 100 种情况。对于这 100 种情况，我们可以0，99划分为 51 个集合：0，1，99，2，98，.，49，51，50。根据鸽巢原理的简单形式，若 52 个整数对应的 a 值互不相等，则一定有 2 个是在同一个集合中。这时两者相加的结果可以被 100 整除。若存在 2 个 a 值相等的整数，这两个整数的差能被 100 整除，证毕。课后题第 15 题题目：证明，对任意 n+1 个整数存在两个整数 和，使得1，2， + 1， 能够被 n 整除。 解答：对任意，均为任意整数，其中 1， + 1ai，pi，qi= + 。易见， 有 n 种

6、可能取值。根据鸽巢原理的简单形式，对 n+1 个pi1，0pin - 1i整数，必然存在两个整数和使得。= pin + qiaj= pjn + qjqi= qjai- aj=(pi- pj)n -(qi- qj)=(pi- qj)n可以被n整除。证毕。课后题第 19 题精选优质文档-倾情为你奉上专心-专注-专业题目：（1）证明，在边长为 1 的等边三角形内任意选择 5 个点，存在 2 个点，期间距离至多为 1/2。（2）证明，在边长为 1 的等边三角形内任意选择 10 个点，存在 2 个点，期间距离至多为 1/3。（3）确定一个整数，使得如果在边长为 1 的等边三角形内任意选mn择个点，则存在

7、 2 个点，其间距离至多为 1/n。mn解答：（1）如图，边长为 1 的等边三角形可以划分为 4 个边长为 1/2 的小等边三角形。在其中任意选择 5 个点，根据鸽巢原理的简单形式，必然存在 2 个点位于同一个边长为1/2 的小等边三角形中，易见这 2 点的距离至多为 1/2，当且仅当 2 点为小等边三角形的顶点时，距离恰好为 1/2。（2）按照类似的划分方法，边长为 1 的等边三角形可以划分为9 个边长为 1/3 的小等边三角形。在其中任意选择 10 个点，根据鸽巢原理的简单形式，必然存在 2 个点位于同一个边长为 1/3 的小等边三角形中，易见这 2 点的距离至多为 1/3，当且仅当 2 点为小等边三角形的顶点时，距离恰好为 1/2。（3）进一步来说，边长为 1 的等边三角形，可以划分为个边长为 1/n 的小等边三角形，根