第十章鸽笼原理 组合数学或组合论是一门历史悠久的应用数学 学科。 随着计算机的普及和发展,对计算机算法的研 究变得日益重要。 计算机算法可分为两大类: 解决数值计算(如方程组求解、积分计算等)的 计算方法, 解决非数值计算(如搜索、排序、组合优化等) 的非数值计算方法主要是组合算法)。 设计和分析组合算法的基础就是组合数学
第十章 鸽笼原理 组合数学或组合论是一门历史悠久的应用数学 学科。 随着计算机的普及和发展，对计算机算法的研 究变得日益重要。 计算机算法可分为两大类: 解决数值计算(如方程组求解、积分计算等)的 计算方法， 解决非数值计算(如搜索、排序、组合优化等) 的非数值计算方法(主要是组合算法)。 设计和分析组合算法的基础就是组合数学
组合数学一般可分为四个方面 判定所提出问题的解是否存在的存在性问题、 确定有解问题其不同解的个数的计数问题、 对可解问题去把解构造出来的构造性算法 从问题的多种构造性算法中择优改进的优化问 题。 组合数学的内容是很丰富的,只涉及组合数学 中的存在性问题和计数问题,为以后学习和研 究计算机算法的设计和分析打下基础。 鸽笼原理是解决组合数学中一些存在性问题的 基本工具。 最早是由狄利克雷 Dirichlet提出的,又称为 抽屉原理、鞋盒原理
组合数学一般可分为四个方面: 判定所提出问题的解是否存在的存在性问题、 确定有解问题其不同解的个数的计数问题、 对可解问题去把解构造出来的构造性算法 从问题的多种构造性算法中择优改进的优化问 题。 组合数学的内容是很丰富的，只涉及组合数学 中的存在性问题和计数问题，为以后学习和研 究计算机算法的设计和分析打下基础。 鸽笼原理是解决组合数学中一些存在性问题的 基本工具。 最早是由狄利克雷(Dirichlet)提出的，又称为 抽屉原理、鞋盒原理
10.1鸽笼原理的简单形式 定理10.1:n+1只鸽子飞回n个笼子,至 少有一个鸽笼含有不少于2只的鸽子。 这个定理的证明是非常简单的 抽去具体的“鸽子”、“鸽笼”等物理 属性 从数学上看,就是把s个元素分成t个组, 当不能均匀分放时,必有一个组其元素 个数要超出“平均数
10.1鸽笼原理的简单形式 定理10.1：n+1只鸽子飞回n个笼子，至 少有一个鸽笼含有不少于2只的鸽子。 这个定理的证明是非常简单的 抽去具体的“鸽子” 、 “鸽笼”等物理 属性 从数学上看，就是把s个元素分成t个组， 当不能均匀分放时，必有一个组其元素 个数要超出“平均数”
定理102:s(s1)个元素分成个组,那么 必存在一个组至少含有s这里「1为“上 整数”记号个元素。 证明:用反证法证明。 若每个组至多含有st+1)个元素,则t个 组最多有元素tst1 因为ss/tk(s/)+1 所以有1+1)<*(s/)+1)-1)s, 导致矛盾。故必存在一个组至少含有st 个元素。 任意13个人中,至少有二人生日在同一个月; 任意70个人中,至少有「sH70/1216人生日同 月;
定理10.2：s(s≥1)个元素分成t个组，那么 必存在一个组至少含有s/t(这里 为“上 整数”记号)个元素。 证明：用反证法证明。 若每个组至多含有(s/t-1)个元素，则t个 组最多有元素t*(s/t-1)， 因为s/t≤s/t<(s/t)+1， 所以有t*(s/t-1)<t*((s/t)+1)-1)<s， 导致矛盾。故必存在一个组至少含有s/t 个元素。 任意13个人中，至少有二人生日在同一个月; 任意70个人中，至少有s/t=70/12=6人生日同 月;
例:在n+1个小于或等于2n的互不相等的正整数 中,必存在两个互质的数。 证明:s=n+1,关键是如何构造鸽笼。 注意到这样的事实:任何相邻两数互质。 因此可以考虑把1,2,,2n这2n个数分成n个组: 1,2},{3,4}2…,{2n-1,2n} 例:在1,2,,2n中任取n+1个互不相同的数中, 必存在两个数,其中一个数是另一个数的倍数。 证明:因为任何正整数n都可表示成n=2ab(这里 a=0,1,2,,且b为奇数)。 设取出的n+1个数为k,k2,kn+1,则k=2ab
例：在n+1个小于或等于2n的互不相等的正整数 中，必存在两个互质的数。 证明：s=n+1,关键是如何构造鸽笼。 注意到这样的事实：任何相邻两数互质。 因此可以考虑把1,2,…,2n这2n个数分成n个组: {{1,2},{3,4},…,{2n-1,2n}}， 例：在1,2,…,2n中任取n+1个互不相同的数中， 必存在两个数，其中一个数是另一个数的倍数。 证明：因为任何正整数n都可表示成n=2a·b(这里 a=0,1,2,…，且b为奇数)。 设取出的n+1个数为k1 ,k2 ,…,kn+1，则ki=2aibi
设a1,a2,an为整数,则存在k和l(0≤k<Kn,使 得a1+ak+2+…+a被n整除。 证明:构造S=a1+a2+…+a1 则有S1S2,Sm, 余数有n个,但为0则表示被n整除,因此考虑分开 讨论
设a1 ,a2 ,…,an为整数，则存在k和l(0k<ln),使 得ak+1+ak+2+…+al被n整除。 证明:构造Si=a1+a2+…+ai , 则有S1 ,S2 ,…,Sn , 余数有n个,但为0则表示被n整除,因此考虑分开 讨论
例:一个国际象棋选手为参加国际比赛,突击练 习77天,要求每天至少下一盘棋,每周至多下12 盘棋。证明:无论如何安排总可使他在这7天里有 连续几天共下了21盘棋。 证明:用a:表示从第1天到第天下棋的总盘数 99···9 由于规定每天至少下一盘棋,且每周至多下12盘 棋,故有:1≤a1≤a2.,<a712×(77/7)=132 现构造一个新的序列a1+21<a2+21<.<a17+21。 现有这样的序列 a1…-;a7,a1+21y,a7+2l 如果要求证明无论如何安排总可使他在这77天里 有连续几天共下了22盘棋,怎样做?
例：一个国际象棋选手为参加国际比赛，突击练 习77天，要求每天至少下一盘棋，每周至多下12 盘棋。证明:无论如何安排总可使他在这77天里有 连续几天共下了21盘棋。 证明：用ai表示从第1天到第i天下棋的总盘数 (i=1,2,…,77)。 由于规定每天至少下一盘棋，且每周至多下12盘 棋，故有：1≤a1<a2<…<a77≤12×(77/7) =132 现构造一个新的序列:a1+21<a2+21<…<a77+21。 现有这样的序列: a1 ,…,a77,a1+21,…,a77+21， 如果要求证明无论如何安排总可使他在这77天里 有连续几天共下了22盘棋,怎样做?
10.2鸽笼原理的加强形式 定理10.3:设q1q2,q都是正整数,若把 q1+q12+…,+qn-n+1个元素分成n个组,则 必然发生:或者第一组中至少有q个元素; 或者第二组中至少有q2个元素;…;或 者第n组中至少有qn个元素。 证明:用反证法证明
10.2鸽笼原理的加强形式 定理10.3:设q1 ,q2 ,…,qn都是正整数，若把 q1+q2+…+qn -n+1个元素分成n个组，则 必然发生: 或者第一组中至少有q1个元素； 或者第二组中至少有q2个元素；…；或 者第n组中至少有qn个元素。 证明:用反证法证明
1)+1个 则至少有一个组中含有r个或者更多的元 素(这里n、r皆为正整数)。 推论102:若n个正整数m,m2…,mn的平 均数满足不等式: (m1+m2+,+mn)/m>r-1,则m1m2,…,mn 中至少有一个不小于r
推论10.1:若将n(r-1)+1个元素分成n个组， 则至少有一个组中含有r个或者更多的元 素(这里n、r皆为正整数)。 推论10.2:若n个正整数m1 ,m2 ,…,mn的平 均数满足不等式: (m1+m2+…+mn )/n>r-1 ， 则 m1 ,m2,…,mn 中至少有一个不小于r
例10.5:两个同心圆盘的每个圆周均分为200 段,从大盘上任选100段涂上红色,其余涂上 蓝色,而在小盘的每个小段上任意涂上红色或 蓝色。证明在旋转小盘时可以找到某个位置, 使得小盘上至少有100个小段与大盘上对应段 颜色相同。 证明:固定大盘,对小盘上任一段,每转一格, 因大盘不动,就与大盘某段组成一种颜色,旋转 一周200格,就与大盘上的所有段构成200种颜色 组合,其中同色的有100组。 小盘上共有200段,故小盘上的所有段在旋转一周 后,与大盘对应段构成的同色组共有20000个。 设转的同色组为m(这里i1,2,,20)
例10.5：两个同心圆盘的每个圆周均分为 200 段，从大盘上任选100段涂上红色，其余涂上 蓝色，而在小盘的每个小段上任意涂上红色或 蓝色。证明在旋转小盘时可以找到某个位置， 使得小盘上至少有100个小段与大盘上对应段 颜色相同。 证明：固定大盘，对小盘上任一段，每转一格， 因大盘不动，就与大盘某段组成一种颜色，旋转 一周200格，就与大盘上的所有段构成200种颜色 组合， 其中同色的有100组。 小盘上共有200段，故小盘上的所有段在旋转一周 后，与大盘对应段构成的同色组共有 20000个。 设转i格的同色组为mi (这里i=1,2,…,200)