离散数学(第19讲)鸽巢原理省公开课一等奖全国示范课微课金奖课件

第6章鸽巢原理第1页容斥原理鸽巢原理Saturday,April13,20242第2页容斥原理在依据条件对某类对象计数时，有时直接计算会碰到很大困难，不过利用间接方法却可能收到良好效果。容斥原理就是采取多退少补思想，逐步求精以到达计数目标一个有效方法。Saturday,April13,20243第3页容斥原理计算从1到1000整数中有多少个能被3、5、7中最少一个整除。设前1000个正整数组成集合为S，能被3整除数组成集合A，能被5整除数组成集合B，能被7整除数组成集合C。能被3、5、7中最少一个整除数组成集合就是。Saturday,April13,20244第4页容斥原理Saturday,April13,20245第5页容斥原理设在有限集A元素上定义了n个性质。假如把含有性质Pi元素组成子集合记为Ai(),表示由同时含有性质Pi和Pj元素组成子集合，表示由同时含有性质Pi，Pj和Pk元素组成子集合，其余依这类推。补集表示由A中不含有性质Pi元素组成子集合Saturday,April13,20246第6页容斥原理有限集A中不含有性质元素个数为Saturday,April13,20247第7页有限集A中含有性质中最少一个性质元素个数为Saturday,April13,20248第8页容斥原理求由数字1,2,3,4,5组成5位数中，数1不排在第一位，数2不排在第二位，数3不排在第三位，数4不排在第4位，数5不排在第五位五位数个数。设A是由1,2,3,4,5组成全部五位数集合，A1,A2,A3,A4,A5分别表示1,2,3,4,5各自出现在第一、第二、第三、第四、第五位五位数组成集合，

Saturday,April13,20249第9页容斥原理Saturday,April13,202410第10页容斥原理Saturday,April13,202411第11页鸽巢原理鸽巢原理：假如n+1只鸽子飞入n个鸽巢中，则必定有鸽巢中最少飞进了两只鸽子在任意13个人集合中，最少有2个人生日同月。因为1年只有12个月，相当于13只鸽子飞入了12个巢中。任意367个人中，最少有2个人生日相同。Saturday,April13,202412第12页在任意11个整数中，最少有2个整数之差是10倍数:设这11个整数分别是关于10模分别为每个余数只能是0,1,…,9中一个。假如把这11个余数看成鸽子，它们要飞进0,1,…,9这10个巢中，依据鸽巢原理，这11个整数中最少有2个整数关于模10余数相同，这2个之差一定是10整数倍Saturday,April13,202413第13页定理8-5.1:当n只鸽子飞进m个巢时，必定最少有一个巢中飞入了Saturday,April13,202414第14页一个人骑车10小时内走完了281公里旅程，已知他第一小时走了30公里，最终一小时走了17公里。证实：他一定在某相继两小时中最少走完了58公里旅程。在这10个小时中有9个相继两小时，依据题目给定条件，全部相继两小时所走旅程之和应该等于281×2-30-17=515公里。把问题看成是让515只鸽子飞进9个鸽巢，必有一个鸽巢中飞进了最少Saturday,April13,202415第15页在任意6个人集体中，要么有3个人相互认识，要么有3个人互不认识。以这6个人中任一个特定人，比如张三作为目标结构两个子集合S1和S2，其中：S1：由与张三相互认识人组成，S2：由与张三不认识人组成，S1和S2中最少有一个集合不少于Saturday,April13,202416第16页假如S1中最少有3个人，要是其中任何两个人都互不认识，那么就找到了3个互不认识人；不然，最少有2个人是相互认识，他们与张三一起组成了3个相互认识人集合。假如S2中最少有3个人