《组合数学幻灯片2.2.》由会员分享，可在线阅读，更多相关《组合数学幻灯片2.2.（13页珍藏版）》请在金锄头文库上搜索。
1、鸽笼原理的一般形式 在定理2.1中，如果将n+1改写成 于是定理2.1就可以叙述为：如果把2+2+2-n+1个物体放入n个盒子中去，则至少存在一个 ( =1,2,n)，使得第 个盒子中至少放有两个物体。,2.2,我们设想，如果在2+2+2+ +2-n+1中的第 个2改为正整数 ( =1,2,，n)就得到鸽笼原理的一般形式： 定理2.2设 是正整数( =1,2,，n),q -n+1,如果把q个物体放入n个盒子中去，则存在一个 ，使得第 个盒子中至少有个物体。, 用反证法。假设结论不成立，即对每一个 ,第 个盒子至多放有 个物体( )，从而这n个盒子放入的物体的总数为 这与 矛盾，从而定理得证。
2、这样一来，定理2.1是定理2.2的特殊形式。 ,证明：,推论2 对于正整数 ，如果 ,至少存在一个i,使得mir。,推论1 如果把n(r-1)+1个物体放入n个盒子中，则至少存在一个盒子放有不少于r个物体。,设第 个盒子放有 个物体，由推论1知，把不少于n(r-1)+1的 个物体放入n个盒子里，至少存在一个i使得 。,推论2证明：,有,或 n(r-1)+1, 证明：在由每个包含 个不同的实数的序列中，存在一个长度为n+1的递增子序列，或者存在一个长度为n+1的递减子序列。(一个序列的长度是指该序列的元素个数)。,设 是一个实数序列，并假设在这个序列中没有长度为n+1的递增子序列，则要证明一定有
3、一个长度为n+1的递减子序列。,例1,证明：,令 表示以 为首项的最长递增子序列的长度， ，则对于每个 ，由假设知1 n。即是说有 个数 都在1到n之间。由推论1知，在 个数中必有r=n+1个数是相同的( )。,不妨设 其中 。下面指出，当 时，必有 ，若对某个i(i=1,2,n),有 ，则可把 放在以为首项的最长递增子序列的前面，就得到以 为首项的一个递增子序列，这样一来，就有 ，这与 相矛盾，因此对每个i=1,2,n都有 这样一个长度为n+1的递减子序列。 故本例结论成立。,将两个大小不一的圆盘分别分成200个相等的扇形。在大圆盘上任选取100个扇形染成红色，另外的100个扇形染成蓝色，并
4、将小圆盘上的扇形任意染成红色或蓝色，然后将小圆盘放大圆盘上且中心重合时，转动小圆盘可使其每一扇形都迭放于大圆盘的某一扇形内证明：当适当转动小圆盘可使迭放的扇形对中，同色者至少为100对。,例2,故由推论1知，至少有一种小圆盘与大圆盘的迭放可使迭放的扇形对中至少有100个同色的扇形对。,证明：,1.首先将大圆盘固定不动，则使小圆盘的每一扇形都迭放于大圆盘的一个扇形中有200种可能的位置(将这200种可能位置看作200个不同的盒子)。,2.由于在这200种可能位置中，小圆盘上的每一扇形都有100次配成同色的扇形对(将同色的扇形对看作放入盒子中的物体)。因此这样的扇形对一共有200100个。而200
5、100200(100-1)+1, 解： 设 表示该圈上相邻三数之和，这样的和共有十个。而1,2,10中的每一个都出现在 这十个和的三个之中。而 故由推论2知，存在一个 使 。,如果将1，2，10随机地摆成一圈，则必有某相邻三数之和至少是17,例3,解： 设 为第一天该棋手下棋的盘数， 是第一、二天该棋手下棋盘数的和， 是第一、二、j天该棋手下棋盘数的和，j=1,2,77，于是序列 是严格递增序列，且,一棋手为参加一次锦标赛要进行77天的训练，如果他每天至少下一盘棋，且每周至多下12盘棋，试证明不管他怎样安排，必存在相继的若干天，在这段时间中他恰好下棋21盘。,例4,于是序列 也是严格递增序列。而 ，故154个数 都在1和153两个整数之间，由鸽笼原理知，这154个数中必有两个是相等的。,故一定存在两个数i和j，使得 即 因此，在j+1天，j+2天，i天这些天中，这个棋手恰好下棋21盘。,
