组合数学幻灯片2.2

1、 鸽笼原理的一般形式鸽笼原理的一般形式 在定理在定理2.12.1中，如果将中，如果将n+1n+1改写成改写成 于是定理于是定理2.12.1就可以叙述为：如果把就可以叙述为：如果把2+2+2-n+12+2+2-n+1个物体放入个物体放入n n个盒子中去，个盒子中去，则至少存在一个则至少存在一个 ( =1,2,n)( =1,2,n)，使得第，使得第 个盒子中至少放有两个物体。个盒子中至少放有两个物体。i12221 nnni i我们设想，如果在我们设想，如果在2+2+2+ +2-n+12+2+2+ +2-n+1中中的第的第 个个2 2改为正整数改为正整数 ( =1,2,( =1,2,，n)n)就得到

2、鸽笼原理的一般形式：就得到鸽笼原理的一般形式：定理定理2.22.2设设 是正整数是正整数( =1,2,( =1,2,，n),q -n+1,n),q -n+1,如果把如果把q q个个物体放入物体放入n n个盒子中去，则存在一个个盒子中去，则存在一个 ，使得第使得第 个盒子中至少有个盒子中至少有个物体。个物体。 iqiiqinqqq 21iiiqi 用反证法。假设结论不成立，即用反证法。假设结论不成立，即对每一个对每一个 , ,第第 个盒子至多放有个盒子至多放有 个物个物体体( )( )，从而这，从而这n n个盒子放入的个盒子放入的物体的总数为物体的总数为这与这与 矛盾，从矛盾，从而定理得证。而定

3、理得证。这样一来，这样一来，定理定理2.12.1是是定理定理2.22.2的特殊的特殊形式。形式。in1iiqn1) 1(21111 nqqqnqqnqnniiininii121 nqqqqn证明：证明：ii推论推论2 2 对于正整数对于正整数 ，如果，如果 , ,至少存在一个至少存在一个i,i,使得使得m mi irr。),2 , 1(nimi1/1rnmnii 推论推论1 1 如果把如果把n(r-1)+1n(r-1)+1个物体放入个物体放入n n个盒个盒子中，则至少存在一个盒子放有不少于子中，则至少存在一个盒子放有不少于r r个个物体。物体。 设第设第 个盒子放有个盒子放有 个物体，由推个物

4、体，由推论论1 1知，把不少于知，把不少于n(r-1)+1n(r-1)+1的的 个个物体放入物体放入n n个盒子里，至少存在一个个盒子里，至少存在一个i i使得使得 。1/1rnmniiniim1iimniim1)1(1rnmniirmi推论推论2 2证明：证明：有或 n(r-1)+1 证明：在由每个包含证明：在由每个包含 个不同的实个不同的实数的序列中，存在一个长度为数的序列中，存在一个长度为n+1n+1的递增子序列，的递增子序列，或者存在一个长度为或者存在一个长度为n+1n+1的递减子序列。的递减子序列。( (一个一个序列的长度是指该序列的元素个数序列的长度是指该序列的元素个数) )。 设

5、 是一个实数序列，并假设在这个序列中没有长度为n+1的递增子序列，则要证明一定有一个长度为n+1的递减子序列。12n2121,na aa例例1 1证明：证明：令令 表示以表示以 为首项的最长递增子序列为首项的最长递增子序列的长度，的长度， ，则对于每，则对于每个个 ，由假设知，由假设知1 n1 n。即是说有即是说有 个数个数 都在都在1 1到到n n之间。由推论之间。由推论1 1知，在知，在 个数中必有个数中必有r=n+1r=n+1个数是个数是相同的相同的( ) )。kmka1,2 , 12nk112nkkkm12n1, 212, nmmm1, 212,nmmm1) 1(12rnn 不妨设不妨

6、设 其中其中 。下面指出，当。下面指出，当 时 ， 必 有时 ， 必 有 ， 若 对 某 个， 若 对 某 个i(i=1,2,n),i(i=1,2,n),有有 ，则可把，则可把 放放在以在以为首项的最长递增子序列的前面，为首项的最长递增子序列的前面，就得到以就得到以 为首项的一个递增子序列，这为首项的一个递增子序列，这样一来，就有样一来，就有 ，这与，这与 相矛相矛盾，因此对每个盾，因此对每个i=1,2,ni=1,2,n都有都有这样一个长度为这样一个长度为n+1n+1的递减子序列。的递减子序列。故本例结论成立。故本例结论成立。121,nkkkmmm212111nkkkn1iikk1iikkaa

7、1iikkaa1ikaikaika1ikikmm1ikikmm121nkkkaaa 将两个大小不一的圆盘分别分成将两个大小不一的圆盘分别分成200200个相等的扇形。在大圆盘上任选取个相等的扇形。在大圆盘上任选取100100个扇形个扇形染成红色，另外的染成红色，另外的100100个扇形染成蓝色，并将个扇形染成蓝色，并将小圆盘上的扇形任意染成红色或蓝色，然后小圆盘上的扇形任意染成红色或蓝色，然后将小圆盘放大圆盘上且中心重合时，转动小将小圆盘放大圆盘上且中心重合时，转动小圆盘可使其每一扇形都迭放于大圆盘的某一圆盘可使其每一扇形都迭放于大圆盘的某一扇形内证明：当适当转动小圆盘可使迭放的扇形内证明：当

8、适当转动小圆盘可使迭放的扇形对中，同色者至少为扇形对中，同色者至少为100100对。对。 例例2 2故由故由推论推论1 1知，至少有一种小圆盘与大圆盘的知，至少有一种小圆盘与大圆盘的迭放可使迭放的扇形对中迭放可使迭放的扇形对中至少至少有有100100个同色的个同色的扇形对。扇形对。证明： 1. 1.首先将大圆盘固定不动，则使小圆盘的首先将大圆盘固定不动，则使小圆盘的每一扇形都迭放于大圆盘的一个扇形中有每一扇形都迭放于大圆盘的一个扇形中有200200种可种可能的位置能的位置( (将这将这200200种可能位置看作种可能位置看作200200个不同的盒个不同的盒子子) )。2.2.由于在这由于在这2

9、00200种可能位置中，小圆盘上的每一种可能位置中，小圆盘上的每一扇形都有扇形都有100100次配成同色的扇形对次配成同色的扇形对( (将同色的扇形将同色的扇形对看作放入盒子中的物体对看作放入盒子中的物体) )。因此这样的扇形对一。因此这样的扇形对一共有共有200200100100个。而个。而200200100200100200(100-1)+1(100-1)+1 解：解：设设 表示该圈上相邻三数之和，这表示该圈上相邻三数之和，这样的和共有十个。而样的和共有十个。而1,2,101,2,10中的每一个都出现中的每一个都出现在在 这十个和的三个之中。而这十个和的三个之中。而故由推论故由推论2 2知

10、，存在一个知，存在一个 使使 。(1,2,10)im i 1210,m mm1013(1210)/1016.517 110iim(1,2,10)i i 17im 如果将如果将1 1，2 2，1010随机地摆成一随机地摆成一圈，则必有某相邻三数之和至少是圈，则必有某相邻三数之和至少是1717例例3 3 解：解： 设设 为第一天该棋手下棋的盘数，为第一天该棋手下棋的盘数， 是是第一、二天该棋手下棋盘数的和，第一、二天该棋手下棋盘数的和， 是第一是第一、二、二、j j天该棋手下棋盘数的和，天该棋手下棋盘数的和，j=1,2,j=1,2,77,77，于是序列于是序列是严格递增序列，且是严格递增序列，且1a2aja7712,a aa1771,132aa 一棋手为参加一次锦标赛要进行一棋手为参加一次锦标赛要进行7777天的天的训练，如果他每天至少下一盘棋，且每周至多下训练，如果他每天至少下一盘棋，且每周至多下1212盘棋，试证明不管他怎样安排，必存在相继的盘棋，试证明不管他怎样安排，必存在相继的若干天，在这段时间中他恰好下棋若干天，在这段时间中他恰好下棋2121盘。盘。例例4 4 于是序列于是序列 也是也是严格递增序列。而严格递增序列。而 ，故，故154154个数个数都在都在1 1和和153153两个整数之间，由鸽笼原理两个整数之间，由鸽笼原理知，这知，这154154个数中必有两个是相等的。