武大计院组合数学PPT容斥原理和鸽巢原理省公共课一等奖全国赛课获奖课件.pptx

第第3章章 容斥原理和鸽巢原理容斥原理和鸽巢原理第1页例例 对对 1,2,n 排列排列 计数，其中计数，其中 。解解 直接计数：直接计数：(1)：有：有 个；个；(n-1):有有 个；个；共有共有 个个 间接计数：间接计数：有：有 个个 所以共有所以共有 个个 容斥原理容斥原理10/10/2第2页例例 计算计算1到到600中不能被中不能被6整除整数个数。整除整数个数。证证 能被能被6整除整数个数为整除整数个数为 所求数个数为所求数个数为 普通，若普通，若 ，则，则 或或容斥原理容斥原理10/10/3第3页作作为为上上述述法法则则第第一一个个推推广广：令令S S是是一一个个有有限限集集合合，P1,P2是是S中中每每个个元元素素可可能能含含有有两两个个性性质质。，分别表示分别表示S中含有性质中含有性质P1，P2元素集合，那么有元素集合，那么有更更普普通通地地，设设P1,P2，Pn是是S中中每每个个元元素素可可能能含含有有n个个性性质质。令令Ai(i=1,2,n)是是S中中含含有有性性质质Pi元素集合，则有元素集合，则有 容斥原理容斥原理10/10/4第4页定理定理3.2 证证 任取任取S中一个元素中一个元素a，(1)若若a不不含含有有这这n个个性性质质中中任任何何一一个个，则则a对对方方程程左端贡献为左端贡献为1，而对方程右端贡献为，而对方程右端贡献为 容斥原理容斥原理10/10/5第5页(2)若若a含含有有这这n个个性性质质中中m个个，则则a对对方方程程左左端端贡贡献为献为0，而对方程右端贡献为，而对方程右端贡献为 容斥原理容斥原理10/10/6第6页推论推论 证证容斥原理容斥原理10/10/7第7页n例例3.2 一个学校只有三门课程：数学、物理、化学。一个学校只有三门课程：数学、物理、化学。已知修这三门课学生分别有已知修这三门课学生分别有170、130、120人；同时人；同时修数学、物理两门课学生修数学、物理两门课学生45人；同时修数学、化学人；同时修数学、化学20人；同时修物理、化学人；同时修物理、化学22人；同时修三门课学生人；同时修三门课学生3人，问这学校共有多少人？人，问这学校共有多少人？解解 设设M为修数学课学生集合为修数学课学生集合 P为修物理课学生集合为修物理课学生集合 C为修化学课学生集合为修化学课学生集合容斥原理容斥原理10/10/8第8页 由题意知，由题意知，所求人数为所求人数为容斥原理容斥原理10/10/9第9页例例3.3 求求a,b,c,d,e,f 六六个个字字母母全全排排列列中中不不允允许许出出现现 ace 和和 df 图象排列数。图象排列数。解解 A1为为出出现现ace图图象象排排列列集集合合，A2为为出出现现df图图象象排排列集合，那么有列集合，那么有 所求排列数为所求排列数为容斥原理容斥原理10/10/10第10页例例3.4 N=1,2,500，求求N中中能能被被2，3，5整整除除数数个数。个数。解解 设设 分分别别为为被被2、3、5整整除除数数集集合合。那那么么有有容斥原理容斥原理10/10/11第11页容斥原理容斥原理10/10/12第12页例例3.5 求求由由a,b,c,d四四个个字字符符组组成成n位位符符号号串串中中，a,b,c最少出现一次符号串数目。最少出现一次符号串数目。证证 设设 分分别别表表示示不不出出现现a,b,cn位位符符号号串串集集合。则合。则容斥原理容斥原理10/10/13第13页n另解：设另解：设 为所求为所求n位符号串数目，位符号串数目，则则an指数型母函数为指数型母函数为 容斥原理容斥原理10/10/14第14页例例3.6 求不超出求不超出120素数个数。素数个数。解解 若一个正整数若一个正整数n是一个合数，那么是一个合数，那么n必能被某个必能被某个素数素数 整除。由整除。由112=121知，不超出知，不超出120合数合数必能被必能被2,3,5,7之一整除。之一整除。设设 为不超出为不超出120,但被但被i整除数集合整除数集合,i=2,3,5,7容斥原理容斥原理10/10/15第15页容斥原理容斥原理10/10/16第16页所求素数个数为：所求素数个数为：27+4-1=30。容斥原理容斥原理10/10/17第17页n例例3.7 用用26个英文字母作不允许重复全排列，要求个英文字母作不允许重复全排列，要求排除排除dog,god,gum,depth,thing字样出现，求满字样出现，求满足这些条件排列数。足这些条件排列数。解解 设设A1为出现为出现dog排列集合；排列集合；A2为出现为出现god 排列集合；排列集合；A3为出现为出现gum排列集合；排列集合；A4为出现为出现depth 排列集合；排列集合；A5为出现为出现thing排列集合。排列集合。容斥原理容斥原理10/10/18第18页 所求排列数为所求排列数为 容斥原理容斥原理10/10/19第19页 例例3.8 求完全由求完全由n个布尔变量确定布尔函数个数。个布尔变量确定布尔函数个数。解解 设设n个个布布尔尔变变量量为为 ，自自变变量量可可能能取取值有值有 个，个，n个布尔变量布尔函数有个布尔变量布尔函数有 个。个。设设 是是 一个布尔函数，一个布尔函数，不依赖于变量不依赖于变量 是指对于每一是指对于每一 都有都有容斥原理容斥原理10/10/20第20页不依赖于某个布尔变量布尔函数有不依赖于某个布尔变量布尔函数有 个。个。不依赖于不依赖于k个布尔变量布尔函数有个布尔变量布尔函数有 个。个。设设 为为不不依依赖赖于于布布尔尔变变量量xi函函数数集集合，那么所求函数个数为合，那么所求函数个数为 当当n=2时时 容斥原理容斥原理10/10/21第21页例例3.9 欧欧拉拉函函数数 表表示示小小于于n，且且与与n互互素素正正整整数个数。数个数。设设 ，表表示示从从1到到n中中能被能被 整除数集合，那么有整除数集合，那么有 ,容斥原理容斥原理10/10/22第22页容斥原理容斥原理10/10/23第23页例例容斥原理容斥原理10/10/24第24页例例3.10 错排问题错排问题 设设 表示表示i在第在第i位排列集合，则有位排列集合，则有 ，容斥原理容斥原理10/10/25第25页n例例2.66 在在8个字母个字母A,B,C,D,E,F,G,H全排列中，求使全排列中，求使A,C,E,G四个字母不在原来位置上排列数目。四个字母不在原来位置上排列数目。解解 设设A1,A2,A3,A4分别表示分别表示A,C,E,G在原来位置上排列在原来位置上排列集合。所求数目为集合。所求数目为容斥原理容斥原理10/10/26第26页习题习题n3.1n3.2n3.16n3.6210/10/27第27页例例3.11 在在4个个x，3个个y，2个个z全全排排列列中中，求求不不出出现现xxxx、yyy、zz图象排列数。图象排列数。解解 设设 分分别别为为出出现现 xxxx、yyy、zz图图象象全全排列集合。则排列集合。则有限制排列有限制排列 10/10/28第28页全部全排列个数为：全部全排列个数为：有限制排列有限制排列10/10/29第29页nn个元素一个排列个元素一个排列 能够看作是能够看作是n个棋子在个棋子在 棋盘上一个布局，每行每列有且仅有一个棋子，其棋盘上一个布局，每行每列有且仅有一个棋子，其中中 是棋盘第是棋盘第 i 行棋子所在列数行棋子所在列数 比如比如 排列排列3 1 4 2所对应棋盘布局以下列图所表示所对应棋盘布局以下列图所表示 棋盘多项式棋盘多项式1234 1 2 3 410/10/30第30页能够把棋盘能够把棋盘C推广到任意形状。推广到任意形状。令令 表示表示k只棋子布到棋盘只棋子布到棋盘C不一样方案数，不一样方案数，规则是当一个棋子置于棋盘某一格子时，则这一规则是当一个棋子置于棋盘某一格子时，则这一格子所在行和列都不能再布任何棋子。格子所在行和列都不能再布任何棋子。棋盘多项式棋盘多项式10/10/31第31页对于给定棋盘对于给定棋盘C，称以下多项式，称以下多项式 为棋盘为棋盘C棋盘多项式，其中棋盘多项式，其中n为棋盘为棋盘C格子数，格子数，并定义并定义 。比如对右图所表示棋盘，其棋盘多项式为比如对右图所表示棋盘，其棋盘多项式为棋盘多项式棋盘多项式10/10/32第32页n在棋盘在棋盘C上选定一个格子，将上选定一个格子，将 分为两类：分为两类：(1)该格子放置棋子该格子放置棋子：有有 种放法；种放法；(2)该格子不放置棋子该格子不放置棋子:有有 种放法种放法.故有故有 其中其中 表示从棋盘表示从棋盘C中删除所选定格子所在行和中删除所选定格子所在行和列后所得到棋盘，而列后所得到棋盘，而 表示从棋盘表示从棋盘C中删除所选中删除所选定格子后所得到棋盘。定格子后所得到棋盘。棋盘多项式棋盘多项式10/10/33第33页由上述关系得由上述关系得棋盘多项式棋盘多项式10/10/34第34页棋盘多项式棋盘多项式10/10/35第35页棋盘多项式棋盘多项式10/10/36第36页棋盘多项式棋盘多项式10/10/37第37页若若棋棋盘盘是是由由两两个个部部分分棋棋盘盘C1和和C2组组成成，其其没没有有C1中格子与中格子与C2中格子在同一行或同一列中，那么中格子在同一行或同一列中，那么有有 这时有这时有 棋盘多项式棋盘多项式10/10/38第38页棋盘多项式棋盘多项式10/10/39第39页有禁区排列有禁区排列 n例例 考虑考虑1，2，3，4排列，排列，要求要求 不能为不能为3，不能为不能为1和和4，不能为不能为2和和4，不能为不能为2。p1p2p3p4 1 2 3 410/10/40第40页定理定理3.3 有禁区排列数为有禁区排列数为 其中其中 是有是有 个棋子布置到禁区部分方案数。个棋子布置到禁区部分方案数。证证 设设Ai(i=1,2,n)为为第第i行行棋棋子子落落在在禁禁区区内内方方案数，那么有案数，那么有有禁区排列有禁区排列 10/10/41第41页有禁区排列有禁区排列 例例3.12 有有G,L,W,Y 4位位工工作作人人员员，A,B,C,D为为四四项项任任务务，但但G不不能能从从事事任任务务B；L不不能能从从事事任任务务B，C；W不不能能从从事事任任务务C，D；Y不不能能从从事事任任务务D。若若要要求求每每人人从从事事各各自自力力所所能能及及一一项项工工作作，试试问问有有多少种不一样方案？多少种不一样方案？解解ABCDGLWYG L W YC D B A10/10/42第42页有禁区排列有禁区排列 图中禁区棋盘多项式为图中禁区棋盘多项式为 所求方案数为所求方案数为 10/10/43第43页n例例3.13 错排问题。错排问题。错排个数为错排个数为 有禁区排列有禁区排列 10/10/44第44页有禁区排列有禁区排列 例例3.14 设设4种种材材料料A,B,C,D拟拟分分配配去去做做1,2,3,4这这4种种产产品品。若若A不不宜宜于于1产产品品；B不不宜宜于于3,4产产品品；C不不宜宜于于1,3产产品品；D不不宜宜于于4产产品品。试试问问有有多多少少种种分配方案，使每种产品有一个其适宜材料。分配方案，使每种产品有一个其适宜材料。1234ABCDA B C D2 1 4 310/10/45第45页有禁区排列有禁区排列*10/10/46第46页有禁区排列有禁区排列所求分配方案数为所求分配方案数为10/10/47第47页广义容斥原理广义容斥原理n设设P1,P2，Pn是是S中中每每个个元元素素可可能能含含有有n个个性性质质。令令Ai(i=1,2,n)是是S中含有性质中含有性质Pi元素集合元素集合.记记10/10/48第48页广义容斥原理广义容斥原理 10/10/49第49页广义容斥原理广义容斥原理定理定理 3.410/10/50第50页n证证 任取一个元素任取一个元素a。若若a有少于有少于m个性质，那么个性质，那么a对方程左端和右端贡献对方程左端和右端贡献都为都为0。若若a恰有恰有m个性质，那么个性质，那么a对方程左端和右端贡献都对方程左端和右端贡献都为为1。若若a恰有恰有 个性质，那么个性质，那么a对等式左端贡献为对等式左端贡献为0，而对等式右端贡献为，而对等式右端贡献为 广义容斥原理广义容斥原理10/10/51第51页广义容斥原理广义容斥原理10/10/52第52页n例例3.15 某学校有某学校有12位教师，已知教数学、物理、位教师，已知教数学、物理、化学课教师分别有化学课教师分别有8位，位，6位，位，5位，其中有位，其中有5位既位既教数学又教物理，有教数学又教物理，有4位兼教数学和化学，兼教物位兼教数学和化学，兼教物理和化学有理和化学有3位；有位；有3位教师教位教师教3门课，试问教数、门课，试问教数、理、化以外课教师有几位？只教一门课教师有几理、化以外课教师有几位？只教一门课教师有几位？恰好教两门课教师有几位？位？恰好教两门课教师有几位？解解 设设A1,A2,A3分别表示教数学、物理、化学课分别表示教数学、物理、化学课教师集合。则教师集合。则广义容斥原理广义容斥原理10/10/53第53页广义容斥原理广义容斥原理教数、理、化以外课教师人数为教数、理、化以外课教师人数为 只教一门课教师人数为只教一门课教师人数为 恰好教两门课教师人数为恰好教两门课教师人数为10/10/54第54页n问题：求满足线性方程问题：求满足线性方程 非负整数解数目。非负整数解数目。上述方程非负整数解与上述方程非负整数解与 r 个无区分球放进个无区分球放进n个有标个有标志盒子志盒子 方案一一对应。方案一一对应。故上述方程非负解个数为故上述方程非负解个数为若干应用若干应用10/10/55第55页n考虑以下问题：求方程考虑以下问题：求方程 整数解数目。整数解数目。若无上界条件，方程若无上界条件，方程 非负整数解数目为非负整数解数目为 若干应用若干应用10/10/56第56页令令A1,A2,A3分分别别为为全全部部非非负负整整数数解解中中满满足足 ,解集合。则所求解个数为解集合。则所求解个数为若干应用若干应用10/10/57第57页若干应用若干应用 考虑以下问题：以下列图所表示，求从考虑以下问题：以下列图所表示，求从O(0,0)点点到到P(10,5)点路径中不经过点路径中不经过AB，CD，EF，GH中中任何一条路径路径数。任何一条路径路径数。P(10,5)O(0,0)ABCDFEGH10/10/58第58页n设设A1,A2,A3,A4分别为从分别为从O点到点到P点过点过AB边、边、CD边、边、EF边、边、GH边路径；边路径；若干应用若干应用10/10/59第59页若干应用若干应用10/10/60第60页 所求路径数为所求路径数为 而而容斥原理容斥原理10/10/61第61页习题习题3.10 3.21 3.2210/10/62第62页n n个个有有区区分分球球放放到到m个个相相同同盒盒子子中中，要要求求无无一一空空盒盒，其其不不一一样样方方案案数数用用S(n,m)表表示示，称称为为第第二二类类Stirling数。数。nn个个有有区区分分球球放放到到m个个不不一一样样盒盒子子中中，要要求求无无一一空空盒，求不一样方案数。盒，求不一样方案数。设设Ai为为使使第第i个个盒盒子子为为空空方方案案集集合合，i=1,2,m。则则有有第二类司特林数展开式第二类司特林数展开式 10/10/63第63页容斥原理容斥原理10/10/64第64页所求方案为所求方案为 由由 知知 容斥原理容斥原理10/10/65第65页例例容斥原理容斥原理10/10/66第66页推论推论 1 推论推论 2 由由 ，容斥原理容斥原理10/10/67第67页问题：问题：设设S=1,2,n，从从S中取中取r 个进行排列，得个进行排列，得 要要求求只只有有k个个数数满满足足 ，这这么么错错排排数数用用来来表表示示 。例例 从从4个中取个中取3个排列数为个排列数为P(4,3)=24 其中其中 ，这，这11个排列为个排列为 2 3 1，3 1 2，2 1 4，2 4 1，4 1 2，3 1 4，3 4 1，4 3 1，2 3 4，3 4 2，4 3 2 错排问题推广错排问题推广 10/10/68第68页 ，这，这9个排列为个排列为 1 3 2，2 1 3，3 2 1，1 4 2，4 2 1，1 3 4，4 1 3，2 4 3，3 2 4 ，这，这3个排列为个排列为 1 2 4，1 4 3，4 2 3 ，这，这1个排列为：个排列为：1 2 3。容斥原理容斥原理10/10/69第69页定理定理 对于正对于正整数整数 ，若，若 ，则有，则有 证证 设设Ai为满足为满足 全部全部r排列集合，排列集合，i=1,r 当当 时，我们有时，我们有 容斥原理容斥原理10/10/70第70页容斥原理容斥原理10/10/71第71页广义容斥原理广义容斥原理定理定理 3.410/10/72第72页容斥原理容斥原理10/10/73第73页容斥原理容斥原理例例10/10/74第74页容斥原理容斥原理10/10/75第75页容斥原理容斥原理性质：性质：(1)证证 10/10/76第76页例例容斥原理容斥原理10/10/77第77页 (2)证证容斥原理容斥原理10/10/78第78页鸽鸽巢巢原原理理：若若n+1个个鸽鸽子子飞飞入入n个个鸽鸽巢巢，则则最最少少有有一个鸽巢中有两只鸽子。一个鸽巢中有两只鸽子。例例3.19 从从1到到2n正正整整数数中中任任取取n+1个个，则则这这n+1个个数中最少有一对数，其中一个数是另一个数倍数。数中最少有一对数，其中一个数是另一个数倍数。解解 设所取设所取n+1个数是：个数是：。令。令 其中其中 为奇数。为奇数。鸽巢原理鸽巢原理10/10/79第79页n因为因为1到到2n正整数中只有正整数中只有n个奇数，故个奇数，故 中最少有两个相等。中最少有两个相等。设设 ，那么当，那么当 时，时，是是 倍数，不然倍数，不然 是是 倍数。倍数。鸽巢原理鸽巢原理10/10/80第80页例例3.20 设设 是是正正整整数数序序列列，则则最最少少存存在在整整数数 k和和 ，使得，使得 证证 结构部分和结构部分和 (1)若若存存在在h，使使得得 ,此此时时取取 ,即即可可.(2)若不存在若不存在h，使得，使得 ，这时存在，这时存在 ,其被其被m除所得余数相等，除所得余数相等，所以所以 鸽巢原理鸽巢原理10/10/81第81页鸽巢原理鸽巢原理10/10/82第82页例例3.22 设设 为三个任意整数，为三个任意整数，为为 任任一一排排列列，则则 中中最最少少有一个是偶数。有一个是偶数。证证 中最少有两个数奇、偶性相同。中最少有两个数奇、偶性相同。不妨设不妨设 同为奇数。同为奇数。故故 中最少有一个是奇数。中最少有一个是奇数。所以所以 中最少有一个是偶数。中最少有一个是偶数。鸽巢原理鸽巢原理10/10/83第83页例例3.23 设设 是是由由1,2组组成成序序列列，已已知知从从其其中中 任任 意意 一一 个个 数数 开开 始始 次次 序序 10个个 数数 和和 不不 超超 出出 16，即即 对对 ，恒有，恒有 则存在则存在 ，使得，使得 解解 作序列作序列 鸽巢原理鸽巢原理10/10/84第84页因为因为 ，故，故 。考虑考虑 由由 知最少有两项相等。但知最少有两项相等。但 ，鸽巢原理鸽巢原理10/10/85第85页所以存在所以存在 ，使得，使得 即有即有鸽巢原理鸽巢原理10/10/86第86页定理定理 设设 都是正整数，若有都是正整数，若有 只只鸽鸽子子飞飞入入n个个鸽鸽巢巢，则则存存在在 ，使使得得第第j个鸽巢最少有个鸽巢最少有 只鸽子。只鸽子。推推论论1:设设k和和n都都是是正正整整数数，若若最最少少有有kn+1只只鸽鸽子子分分配配在在n个个鸽鸽巢巢里里，则则最最少少存存在在一一个个鸽鸽巢巢，使使得得该该鸽巢中最少有鸽巢中最少有k+1只鸽子。只鸽子。鸽巢原理推广鸽巢原理推广10/10/87第87页推推论论 2 m只只鸽鸽子子，n个个鸽鸽子子巢巢，则则最最少少有有一一个个鸽鸽子子巢里有不少于巢里有不少于 只鸽子。只鸽子。证证 若每个鸽巢中至多有若每个鸽巢中至多有 只鸽子，则只鸽子，则n个鸽个鸽巢中最多有巢中最多有 只鸽子，与假设矛盾。只鸽子，与假设矛盾。鸽巢原理推广鸽巢原理推广10/10/88第88页推推论论 3 将将 个个球球放放入入n个个盒盒子子，则则最最少少有有一个盒子有一个盒子有m个球。个球。推论推论 4 若若 是是n个正整数，而且个正整数，而且 则中最少有一个数大于则中最少有一个数大于r鸽巢原理推广鸽巢原理推广10/10/89第89页例例 例例3.25 设设 是是由由10个个0和和10个个1组组成成20位位二二进进制制数数串串；是是任任意意20位位二二进进制制数数串串。现现将将A、B分分别别记记入入如如图图(A)、(B)两两个个20个个格格子子，分分别别得得到到(A)、(B)两两种种图图象象，并并把把两两个个B连连接接得得40位位二二进制数进制数 ,它图象为它图象为(C)。(A)(B)(C)10/10/90第90页证证实实存存在在某某一一配配合合能能够够使使图图象象(C)上上某某相相连连20格格恰恰好和图象好和图象(A)20格中最少格中最少10位对应数字相同。位对应数字相同。证证 将将(A)第第1格对应格对应(C)第第i格格(i=1,2,20)。在这。在这个过程中，图象个过程中，图象(B)每一格和每一格和(A)每一格比较相同了每一格比较相同了10次，相同数字数目之和为次，相同数字数目之和为 ,平均每次有相同数字格数为平均每次有相同数字格数为 故最少有一次，其中相同数字格数不少于故最少有一次，其中相同数字格数不少于10。例例10/10/91第91页n定理定理 任意任意n2+1个不一样实数个不一样实数 组成序列中，必有一个长度为组成序列中，必有一个长度为n+1单调增子序列或单调增子序列或单调减子序列。单调减子序列。n给定序列给定序列 5,3,16,10,15,14,9,11,6,7 单调增子序列单调增子序列 5,16；5,10,15；3,9,11；3,6,7；单调减子序列单调减子序列 5,3；16,10,9,6；16,15,14,11,6；例例10/10/92第92页证证 假假定定没没有有长长度度为为n+1单单调调增增子子序序列列，下下面面证证实实必有长度为必有长度为n+1单调降子序列。单调降子序列。设设 表表示示从从 开开始始最最长长单单调调增增子子序列长度，由假设知序列长度，由假设知 由鸽巢原理知，最少有由鸽巢原理知，最少有 例例10/10/93第93页个个 ，使得，使得 不失普通性，假设不失普通性，假设 ，则有，则有 即存在一个长度为即存在一个长度为n+1单调减子序列。单调减子序列。例例10/10/94第94页3.3 3.6 3.7 3.54 习题习题10/10/95第95页定理定理 设设 都是正整数，若有都是正整数，若有 只只鸽鸽子子飞飞入入n个个鸽鸽巢巢，则则存存在在 ，使使得得第第j个鸽巢最少有个鸽巢最少有 只鸽子。只鸽子。推推论论1:设设k和和n都都是是正正整整数数，若若最最少少有有kn+1只只鸽鸽子子分分配配在在n个个鸽鸽巢巢里里，则则最最少少存存在在一一个个鸽鸽巢巢，使使得得该该鸽巢中最少有鸽巢中最少有k+1只鸽子。只鸽子。鸽巢原理推广鸽巢原理推广10/10/96第96页推推论论 2 m只只鸽鸽子子，n个个鸽鸽子子巢巢，则则最最少少有有一一个个鸽鸽子子巢里有不少于巢里有不少于 只鸽子。只鸽子。证证 由由 及推论及推论1便知结论正确便知结论正确鸽巢原理推广鸽巢原理推广10/10/97第97页推推论论 3 将将 个个球球放放入入n个个盒盒子子，则则最最少少有有一个盒子有一个盒子有m个球。个球。推论推论 4 若若 是是n个正整数，而且个正整数，而且 则中最少有一个数大于则中最少有一个数大于r 证证 在推论在推论1中取中取 ,并注意并注意鸽巢原理推广鸽巢原理推广10/10/98第98页例例3.28 设设A=1,2,99，X是是A子子集集,且且 ,则则能能够够找找到到X两两个个互互不不相相交交真真子子集集Y和和Z，使使得得Y中中元元素素之和等于之和等于Z中元素之和。中元素之和。解解 因因为为 ，所所以以X有有 个个非非空空真真子子集，但集，但X非空真子集非空真子集S中元素之和满足中元素之和满足 例例10/10/99第99页现现在在有有1022只只鸽鸽子子，855个个鸽鸽巢巢，故故最最少少有有两两个个鸽鸽巢中鸽子数相等。设这两个子集为巢中鸽子数相等。设这两个子集为B和和C，则，则 (1)当当 时，令时，令 Y=B，Z=C即可；即可；(2)当当 时，令时，令 即可。即可。例例10/10/100第100页例例 一一个个抽抽屉屉里里有有20件件衬衬杉杉，其其中中4件件是是蓝蓝，7件件是是灰灰，9件件是是红红。试试问问应应从从中中随随意意抽抽取取多多少少件件能能确确保保有有4件件是是同同色色？又又应应抽抽取取多多少少件件能能确确保保有有5，6，7，8，9件是同色？件是同色？解解 由鸽巢原理：由鸽巢原理：n个鸽巢，个鸽巢，kn+1只鸽子，则最少只鸽子，则最少存在一个鸽巢，使得该鸽巢中最少有存在一个鸽巢，使得该鸽巢中最少有k+1只鸽子。只鸽子。(1)这时这时n=3，k+1=4，所以，所以k=3，于是，于是 即随意抽取即随意抽取10件能确保有件能确保有4件是同色。件是同色。例例10/10/101第101页 (2)这时不能直接用鸽巢原理。考虑一个最坏情这时不能直接用鸽巢原理。考虑一个最坏情形，在所抽取衬衫中有形，在所抽取衬衫中有4件是蓝。件是蓝。这时这时n=2，k+1=5，所以，所以k=4，于是应抽取，于是应抽取 即随意抽取即随意抽取13件能确保有件能确保有5件是同色。件是同色。例例10/10/102第102页 (3)一样假设在所抽取衬衫中有一样假设在所抽取衬衫中有4件是蓝。件是蓝。这时这时n=2，k+1=6，所以，所以k=5，于是应抽取，于是应抽取 即随意抽取即随意抽取15件能确保有件能确保有6件是同色。件是同色。同理可证，随意抽取同理可证，随意抽取17，19，20件能确保有件能确保有7，8，9件是同色。件是同色。例例10/10/103第103页问问题题：6个个人人中中，或或有有3个个人人相相互互认认识识，或或有有3个个人人相互不认识。相互不认识。每每个个人人用用一一个个顶顶点点表表示示，若若两两个个人人相相互互认认识识，则则对对对对应应两两个个顶顶点点之之间间边边着着红红色色，若若两两个个人人相相互互不不认认识识，则则对对对对应应两两个个顶顶点点之之间间边边着着蓝蓝色色。这这么么问问题就转化为：题就转化为：n给定一个给定一个6个顶点完全图个顶点完全图K6，用红、蓝两色对其，用红、蓝两色对其边任意着色，那么或者存在一个红色边三角形，边任意着色，那么或者存在一个红色边三角形，或者存在一个蓝色边三角形。或者存在一个蓝色边三角形。Ramsey数数 10/10/104第104页n证证 选定选定K6一个顶点一个顶点v，顶点顶点v有有5条边条边,由鸽巢原由鸽巢原 理知，最少有理知，最少有 条同色边，设为红色。设这三条边另一个端点分条同色边，设为红色。设这三条边另一个端点分别为别为 v1,v2,v3。若若v1,v2,v3之间有一条红色边，则之间有一条红色边，则已得到一个红色边三角形，不然，则得到一个蓝已得到一个红色边三角形，不然，则得到一个蓝色边三角形。色边三角形。Ramsey数数vv1v2v310/10/105第105页n若干推论若干推论 (a)对对6个顶点完全图个顶点完全图K6边用红、蓝两色任意着色，边用红、蓝两色任意着色，那么最少有两个同色三角形。那么最少有两个同色三角形。下面分情况讨论：下面分情况讨论：Ramsey数数图1图2图310/10/106第106页 (1)若红色三角形某个顶点其它三条边均为蓝色若红色三角形某个顶点其它三条边均为蓝色 (2)若红色三角形某个顶点其它三条边中最少有两若红色三角形某个顶点其它三条边中最少有两条为红色；条为红色；(3)若红色三角形任一个顶点其它三条边中恰有一条若红色三角形任一个顶点其它三条边中恰有一条边为红色。边为红色。Ramsey数数10/10/107第107页(b)对对10个个顶顶点点完完全全图图K10边边用用红红、蓝蓝两两色色任任意意着着色色,那么或者有一红色那么或者有一红色K4,或者有一蓝色或者有一蓝色K3。证证 设设a是是K10一一个个顶顶点点，与与a关关联联9条条边边中中,或或者者有有6条红边条红边,或者有或者有4条蓝边。条蓝边。(1)若与若与a关联关联9条边中有条边中有4条蓝边；条蓝边；Ramsey数数a10/10/108第108页n(2)若与若与a关联关联9条边中有条边中有6条红边。这时与条红边。这时与a邻接邻接6个顶点所组成完全图中或有一个红色个顶点所组成完全图中或有一个红色K3，或有一，或有一个蓝色个蓝色K3。若有红色。若有红色K3，则该，则该K3与顶点与顶点a所组成所组成K4是一个红色是一个红色K4；不然有一个蓝色；不然有一个蓝色K3。Ramsey数数a10/10/109第109页(c)对对9个个顶顶点点完完全全图图K9边边用用红红、蓝蓝两两色色任任意意着着色色，那么或者有一红色那么或者有一红色K4，或者有一蓝色，或者有一蓝色K3。证证 在在K9中，假如与每个顶点关联红边均为中，假如与每个顶点关联红边均为5条，那条，那么在么在K9中，应有中，应有 条红边。但这是不可能。故必有一个顶点红边数不条红边。但这是不可能。故必有一个顶点红边数不为为5。设此顶点为。设此顶点为a,则与则与a关联红边数最少为关联红边数最少为6,或者或者至多为至多为4。以下与推论。以下与推论(b)证实类似。证实类似。Ramsey数数10/10/110第110页(d)对对18个个顶顶点点完完全全图图K18边边用用红红、蓝蓝两两色色任任意意着着色色,那么或者有一红色那么或者有一红色K4,或者有一蓝色或者有一蓝色K4。证证设设a是是K18一一个个顶顶点点，与与a关关联联17条条边边中中,最最少少有有9条是同色边条是同色边,不妨设为红色边。不妨设为红色边。在在这这9条条边边另另9个个端端点点组组成成完完全全图图K9中中,或或有有一一个个红色红色K3,或有一个蓝色或有一个蓝色K4.若有一个红色若有一个红色K3,则则a与该红色与该红色K3组成一个红色组成一个红色K4.不然有一个蓝色不然有一个蓝色K4.Ramsey数数10/10/111第111页n例例 对对17个顶点完全图个顶点完全图K17边用红、蓝、黄三种颜边用红、蓝、黄三种颜色任意着色，那么或者有一红色色任意着色，那么或者有一红色K3，或者有一蓝，或者有一蓝色色K3，或者有一黄色，或者有一黄色K3。证证 任取任取K17中一个顶点中一个顶点a，在与，在与a关联关联16条边中，条边中，最少有最少有6条是同色，不妨设为红色。条是同色，不妨设为红色。Ramsey数数a10/10/112第112页定定义义 对对于于任任意意给给定定两两个个正正整整数数a和和b，假假如如存存在在最最小正整数小正整数 ,使得当使得当 时，对时，对 中中边边用用红红、蓝蓝两两色色任任意意着着色色，中中或或者者有有红红色色 ,或者有蓝色或者有蓝色 ,则称则称 为为Ramsey数。数。例例Ramsey数数10/10/113第113页定理定理1 ,。定理定理2 对任意整数对任意整数 ，存在。存在。定理定理3 对任意正整数对任意正整数 ，有，有 证证 令令 ,对对KN中中边边用用红红、蓝蓝两两色色任任意意着着色色。设设x是是KN一一个个顶顶点点，在在KN中中与与x关关联联边边共共有有 条条,在在这这些些边边中中,或者最少有或者最少有 条条 红边红边,Ramsey数数10/10/114第114页或者最少有或者最少有 条蓝边。条蓝边。(1)有有 条红边。条红边。在在这这些些红红边边与与x关关联联 个个顶顶点点组组成成完完全全图图中中,或者有一个红色或者有一个红色 ,或者有一个蓝色或者有一个蓝色 .若若有有红红色色 ,则则该该红红色色 加加上上顶顶点点x以以及及x与与顶顶点点之之间间红红边边，组组成成一一个个红红色色 ;不不然然有有一一个个蓝蓝色色 。Ramsey数数10/10/115第115页(2)有条有条 蓝边蓝边 在在这这些些蓝蓝边边与与x关关联联 个个顶顶点点组组成成完完全全图图中中,或有一个红色或有一个红色 ,或有一个蓝色或有一个蓝色 。若若有有蓝蓝色色 ，则则该该蓝蓝色色加加上上顶顶点点x以以及及x与与顶顶点点之之间间蓝蓝边边，组组成成一一个个蓝蓝色色 ;不不然然有有一一个个红红色色 。由由(1)、(2)知知 。Ramsey数数10/10/116第116页n利用定理利用定理3.15，我们能够计算出，我们能够计算出R(a,b)上界。上界。Ramsey数数 b 2 3 4 5 6 7a2 2 3 4 5 6 7 3 3 6 10 15 21 28 4 4 10 20 35 5 5 15 3510/10/117第117页定理定理 4 对任意正整数对任意正整数 ，有，有 证证 对对a+b用归纳法。用归纳法。当当a+b=4时，定理显然成立。时，定理显然成立。假设对一切满足假设对一切满足 a,b，定理成立，定理成立，那么有那么有Ramsey数数10/10/118第118页 这就归纳地证实了定理。这就归纳地证实了定理。Ramsey数数10/10/119第119页设设 为正整数，对为正整数，对N个顶点完全图个顶点完全图 中边用中边用 k种颜色进行着色，则种颜色进行着色，则 中或有中或有 颜色颜色 ,或有或有 颜色颜色 ,，或有，或有 颜颜 色色 ，满满 足足 上上 述述 性性 质质 N最最 小小 值值 记记 为为 。Ramsey数推广数推广 10/10/120第120页n定理定理5 对任意正整数对任意正整数 ，有，有 证证 设设 对对 中边用中边用 染色染色,并将并将 看作是红色看作是红色,将将 看作是蓝看作是蓝色色,则或有一个红色则或有一个红色 ,或者有蓝色或者有蓝色 ,在蓝在蓝色色 中中,其边是用其边是用 染色染色,故故 中或有色中或有色 ,或有色或有色 。Ramsey数推广数推广10/10/121第121页例例 定理定理6 对任意正整数对任意正整数 ,有有 定理定理7 对任意正整数对任意正整数 ,有有 Ramsey数推广数推广10/10/122第122页一一个个半半群群是是一一个个含含有有满满足足结结合合律律二二元元运运算算有有限限集集合。合。命题命题:任何有限半群有一个幂等元任何有限半群有一个幂等元证证 令令a是半群中任一个元素，是半群中任一个元素，n是半群阶。是半群阶。设设 ,对对 KN 边用边用n种颜色着色，其种颜色着色，其 中这中这n种颜色分别响应半群种颜色分别响应半群n个元素。个元素。对对边边(i,j)着着色色 ,由由Ramsey定定理理,KN中中存存在在一一个个单单色色三三角角形形,即即存存在在 ,使使得得 应用应用10/10/123第123页 令令 ，便得，便得应用应用10/10/124第124页n考虑集合考虑集合1,2,13一个划分：一个划分：1,4,10,13,2,3,11,12,5,6,7,8,9 能够看出，在上面划分每一块中，都不存在三个能够看出，在上面划分每一块中，都不存在三个数数x,y,z(不一定不一样不一定不一样)，满足方程，满足方程 x+y=z (1)然而，不论怎样将然而，不论怎样将1,2,13,14划分成三个子划分成三个子集合，总有一个子集合中有三个数满足方程集合，总有一个子集合中有三个数满足方程(1)。应用应用10/10/125第125页 定定理理8 设设S1,S2,Sn是是集集合合 任任一一划划分分，则则对对某某个个 ,Si中中有有三三个个数数x,y,z(不不一一定定不不一一样样),满足方程满足方程x+y=z.其中其中 证证 对对 边以下着色：若边以下着色：若 ,则则(u,v)染成第染成第j 种颜色。种颜色