十章鸽笼原理十章鸽笼原理组合数学一般可分为四个方面组合数学一般可分为四个方面: 判定所提出问题的解是否存在的存在性问题、判定所提出问题的解是否存在的存在性问题、确定有解问题其不同解的个数的计数问题、确定有解问题其不同解的个数的计数问题、对可解问题去把解构造出来的构造性算法对可解问题去把解构造出来的构造性算法从从问问题题的的多多种种构构造造性性算算法法中中择择优优改改进进的的优优化化问问题。题。组组合合数数学学的的内内容容是是很很丰丰富富的的，只只涉涉及及组组合合数数学学中中的的存存在在性性问问题题和和计计数数问问题题，为为以以后后学学习习和和研研究计算机算法的设计和分析打下基础。究计算机算法的设计和分析打下基础。鸽鸽笼笼原原理理是是解解决决组组合合数数学学中中一一些些存存在在性性问问题题的的基本工具。基本工具。最最早早是是由由狄狄利利克克雷雷(Dirichlet)提提出出的的，又又称称为为抽屉原理、鞋盒原理。抽屉原理、鞋盒原理。推推论论10.1:若若将将n(r-1)+1个个元元素素分分成成n个个组组，则则至至少少有有一一个个组组中中含含有有r个个或或者者更更多多的的元元素素(这里这里n、r皆为正整数皆为正整数)。推推论论10.2:若若n个个正正整整数数m1,m2,mn的的平平均数满足不等式均数满足不等式: (m1+m2+mn)/nr-1， 则则 m1,m2,mn中至少有一个不小于中至少有一个不小于r。例例10.5：两两个个同同心心圆圆盘盘的的每每个个圆圆周周均均分分为为 200段段，从从大大盘盘上上任任选选100段段涂涂上上红红色色，其其余余涂涂上上蓝蓝色色，而而在在小小盘盘的的每每个个小小段段上上任任意意涂涂上上红红色色或或蓝蓝色色。证证明明在在旋旋转转小小盘盘时时可可以以找找到到某某个个位位置置，使使得得小小盘盘上上至至少少有有100个个小小段段与与大大盘盘上上对对应应段段颜色相同。颜色相同。证证明明：固固定定大大盘盘，对对小小盘盘上上任任一一段段，每每转转一一格格，因因大大盘盘不不动动，就就与与大大盘盘某某段段组组成成一一种种颜颜色色，旋旋转转一一周周200格格，就就与与大大盘盘上上的的所所有有段段构构成成200种种颜颜色色组合，组合， 其中同色的有其中同色的有100组。组。小小盘盘上上共共有有200段段，故故小小盘盘上上的的所所有有段段在在旋旋转转一一周周后，与大盘对应段构成的同色组共有后，与大盘对应段构成的同色组共有 20000个。个。设转设转i格的同色组为格的同色组为mi(这里这里i=1,2,200)，例例10.6：设设a1,a2,an2+1，是是n2+1个个不不同同实实数数的的序序列列，则则必必可可从从此此序序列列中中选选出出n+1个个数数的的子子序序列列，使使这这子子序序列列为为递递增增序序列列或递减序列。或递减序列。证证明明:若若存存在在长长度度为为n+1的的递递增增序序列列，结结论成立。论成立。若若不不存存在在长长度度为为n+1的的递递增增序序列列，目目标标证证明存在长度为明存在长度为n+1的递减序列。的递减序列。首首先先要要找找到到一一个个长长度度为为n+1的的子子序序列列，然然后证明是递减序列后证明是递减序列作业作业:P221 1,3,4,5,7课件地址：课件地址：ftp:/10.11.2.154集合与图论集合与图论