離散數(shù)學(xué)(第19講)鴿巢原理省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)?wù)n件

第6章鴿巢原理第1頁(yè)容斥原理鴿巢原理Saturday,April13,20242第2頁(yè)容斥原理在依據(jù)條件對(duì)某類(lèi)對(duì)象計(jì)數(shù)時(shí)，有時(shí)直接計(jì)算會(huì)碰到很大困難，不過(guò)利用間接方法卻可能收到良好效果。容斥原理就是采取多退少補(bǔ)思想，逐步求精以到達(dá)計(jì)數(shù)目標(biāo)一個(gè)有效方法。Saturday,April13,20243第3頁(yè)容斥原理計(jì)算從1到1000整數(shù)中有多少個(gè)能被3、5、7中最少一個(gè)整除。設(shè)前1000個(gè)正整數(shù)組成集合為S，能被3整除數(shù)組成集合A，能被5整除數(shù)組成集合B，能被7整除數(shù)組成集合C。能被3、5、7中最少一個(gè)整除數(shù)組成集合就是。Saturday,April13,20244第4頁(yè)容斥原理Saturday,April13,20245第5頁(yè)容斥原理設(shè)在有限集A元素上定義了n個(gè)性質(zhì)。假如把含有性質(zhì)Pi元素組成子集合記為Ai(),表示由同時(shí)含有性質(zhì)Pi和Pj元素組成子集合，表示由同時(shí)含有性質(zhì)Pi，Pj和Pk元素組成子集合，其余依這類(lèi)推。補(bǔ)集表示由A中不含有性質(zhì)Pi元素組成子集合Saturday,April13,20246第6頁(yè)容斥原理有限集A中不含有性質(zhì)元素個(gè)數(shù)為Saturday,April13,20247第7頁(yè)有限集A中含有性質(zhì)中最少一個(gè)性質(zhì)元素個(gè)數(shù)為Saturday,April13,20248第8頁(yè)容斥原理求由數(shù)字1,2,3,4,5組成5位數(shù)中，數(shù)1不排在第一位，數(shù)2不排在第二位，數(shù)3不排在第三位，數(shù)4不排在第4位，數(shù)5不排在第五位五位數(shù)個(gè)數(shù)。設(shè)A是由1,2,3,4,5組成全部五位數(shù)集合，A1,A2,A3,A4,A5分別表示1,2,3,4,5各自出現(xiàn)在第一、第二、第三、第四、第五位五位數(shù)組成集合，

Saturday,April13,20249第9頁(yè)容斥原理Saturday,April13,202410第10頁(yè)容斥原理Saturday,April13,202411第11頁(yè)鴿巢原理鴿巢原理：假如n+1只鴿子飛入n個(gè)鴿巢中，則必定有鴿巢中最少飛進(jìn)了兩只鴿子在任意13個(gè)人集合中，最少有2個(gè)人生日同月。因?yàn)?年只有12個(gè)月，相當(dāng)于13只鴿子飛入了12個(gè)巢中。任意367個(gè)人中，最少有2個(gè)人生日相同。Saturday,April13,202412第12頁(yè)在任意11個(gè)整數(shù)中，最少有2個(gè)整數(shù)之差是10倍數(shù):設(shè)這11個(gè)整數(shù)分別是關(guān)于10模分別為每個(gè)余數(shù)只能是0,1,…,9中一個(gè)。假如把這11個(gè)余數(shù)看成鴿子，它們要飛進(jìn)0,1,…,9這10個(gè)巢中，依據(jù)鴿巢原理，這11個(gè)整數(shù)中最少有2個(gè)整數(shù)關(guān)于模10余數(shù)相同，這2個(gè)之差一定是10整數(shù)倍Saturday,April13,202413第13頁(yè)定理8-5.1:當(dāng)n只鴿子飛進(jìn)m個(gè)巢時(shí)，必定最少有一個(gè)巢中飛入了Saturday,April13,202414第14頁(yè)一個(gè)人騎車(chē)10小時(shí)內(nèi)走完了281公里旅程，已知他第一小時(shí)走了30公里，最終一小時(shí)走了17公里。證實(shí)：他一定在某相繼兩小時(shí)中最少走完了58公里旅程。在這10個(gè)小時(shí)中有9個(gè)相繼兩小時(shí)，依據(jù)題目給定條件，全部相繼兩小時(shí)所走旅程之和應(yīng)該等于281×2-30-17=515公里。把問(wèn)題看成是讓515只鴿子飛進(jìn)9個(gè)鴿巢，必有一個(gè)鴿巢中飛進(jìn)了最少Saturday,April13,202415第15頁(yè)在任意6個(gè)人集體中，要么有3個(gè)人相互認(rèn)識(shí)，要么有3個(gè)人互不認(rèn)識(shí)。以這6個(gè)人中任一個(gè)特定人，比如張三作為目標(biāo)結(jié)構(gòu)兩個(gè)子集合S1和S2，其中：S1：由與張三相互認(rèn)識(shí)人組成，S2：由與張三不認(rèn)識(shí)人組成，S1和S2中最少有一個(gè)集合不少于Saturday,April13,202416第16頁(yè)假如S1中最少有3個(gè)人，要是其中任何兩個(gè)人都互不認(rèn)識(shí)，那么就找到了3個(gè)互不認(rèn)識(shí)人；不然，最少有2個(gè)人是相互認(rèn)識(shí)，他們與張三一起組成了3個(gè)相互認(rèn)識(shí)人集合。假如S2中最少有3個(gè)人