组合数学复习资料(前两章).doc

《组合数学复习资料(前两章).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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、和第二天所下的总盘数，以此类推，是前n天所下的总盘数。由于每天至少要下一盘棋，故数值序列是一个严格递增的序列，即数列的每一项大于它前面的那一项。此外，，而且由于每周下棋最多12盘，。因为，我们有。同样，序列也是一个严格递增序列：于是，这个数中每一个都是[1，132+k]内的一个整数。区间内共有132+k个整数，故当132+k<154时，即k<22时，根据鸽巢原理的简单形式，这154个数中至少存在一对相等的数。若则无法断定至少存在一对相等的数。又因为数值序列和都是严格递增的，所以不存在相等的2个数，所以相等的2个数必然分别属于2个数

3、值序列。则存在，使得，也就是说从第i+1天至第j天，这位大师一共下了k盘棋。所以命题“对于每个k=1，2，…，21存在连续若干天，在此期间国际象棋大师将恰好下完k局棋”成立。对于k=22的情况，无法论断。课后题第4题题目：证明，如果从集合{1，2，...，2n}中选择n+1个整数，那么总存在两个整数，他们之间相差为1。解答：对于集合{1，2，...，2n}可以划分为n个互不相交的子集：{1，2}，{3，4}，...，{2n-1，n}，且这些子集包含了原集合的全部元素。故从原集合中选择n+1个整数，等价于从这n个子集中选择n+1个整

4、数。根据鸽巢原理的简单形式，必然存在2个选择出的整数属于同一个子集，它们之间相差为1。证毕。课后题第7题题目：证明，对任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除，要么两者的差能被100整除。解答：对于任意的一个整数，可以写成的形式，其中k为任意整数，a为的整数。则a有0，1，2，...，99这100种情况。对于这100种情况，我们可以划分为51个集合：{0}，{1，99}，{2，98}，...，{49，51}，{50}。根据鸽巢原理的简单形式，若52个整数对应的a值互不相等，则一定有2个是在同一个集合中。

5、这时两者相加的结果可以被100整除。若存在2个a值相等的整数，这两个整数的差能被100整除，证毕。课后题第15题题目：证明，对任意n+1个整数存在两个整数和，使得能够被n整除。解答：对任意，均为任意整数，，其中。易见，有n种可能取值。根据鸽巢原理的简单形式，对n+1个整数，必然存在两个整数和使得。课后题第19题题目：（1）证明，在边长为1的等边三角形内任意选择5个点，存在2个点，期间距离至多为1/2。（2）证明，在边长为1的等边三角形内任意选择10个点，存在2个点，期间距离至多为1/3。（3）确定一个整数，使得如果在边长为1的等边

6、三角形内任意选择个点，则存在2个点，其间距离至多为1/n。解答：（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

7、/3，当且仅当2点为小等边三角形的顶点时，距离恰好为1/2。（3）进一步来说，边长为1的等边三角形，可以划分为个边长为1/n的小等边三角形，根据鸽巢原理的简单形式，在其中任选个点，可以保证存在2个点，其间距离至多为1/n。2.2：鸽巢原理：加强形式略2.3：RAMSEY（拉姆西）定理（略）略