離散數(shù)學(第19講)鴿巢原理省公開課一等獎全國示范課微課金獎課件

第6章鴿巢原理第1頁容斥原理鴿巢原理Saturday,April13,20242第2頁容斥原理在依據(jù)條件對某類對象計數(shù)時，有時直接計算會碰到很大困難，不過利用間接方法卻可能收到良好效果。容斥原理就是采取多退少補思想，逐步求精以到達計數(shù)目標一個有效方法。Saturday,April13,20243第3頁容斥原理計算從1到1000整數(shù)中有多少個能被3、5、7中最少一個整除。設前1000個正整數(shù)組成集合為S，能被3整除數(shù)組成集合A，能被5整除數(shù)組成集合B，能被7整除數(shù)組成集合C。能被3、5、7中最少一個整除數(shù)組成集合就是。Saturday,April13,20244第4頁容斥原理Saturday,April13,20245第5頁容斥原理設在有限集A元素上定義了n個性質(zhì)。假如把含有性質(zhì)Pi元素組成子集合記為Ai(),表示由同時含有性質(zhì)Pi和Pj元素組成子集合，表示由同時含有性質(zhì)Pi，Pj和Pk元素組成子集合，其余依這類推。補集表示由A中不含有性質(zhì)Pi元素組成子集合Saturday,April13,20246第6頁容斥原理有限集A中不含有性質(zhì)元素個數(shù)為Saturday,April13,20247第7頁有限集A中含有性質(zhì)中最少一個性質(zhì)元素個數(shù)為Saturday,April13,20248第8頁容斥原理求由數(shù)字1,2,3,4,5組成5位數(shù)中，數(shù)1不排在第一位，數(shù)2不排在第二位，數(shù)3不排在第三位，數(shù)4不排在第4位，數(shù)5不排在第五位五位數(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頁容斥原理Saturday,April13,202410第10頁容斥原理Saturday,April13,202411第11頁鴿巢原理鴿巢原理：假如n+1只鴿子飛入n個鴿巢中，則必定有鴿巢中最少飛進了兩只鴿子在任意13個人集合中，最少有2個人生日同月。因為1年只有12個月，相當于13只鴿子飛入了12個巢中。任意367個人中，最少有2個人生日相同。Saturday,April13,202412第12頁在任意11個整數(shù)中，最少有2個整數(shù)之差是10倍數(shù):設這11個整數(shù)分別是關于10模分別為每個余數(shù)只能是0,1,…,9中一個。假如把這11個余數(shù)看成鴿子，它們要飛進0,1,…,9這10個巢中，依據(jù)鴿巢原理，這11個整數(shù)中最少有2個整數(shù)關于模10余數(shù)相同，這2個之差一定是10整數(shù)倍Saturday,April13,202413第13頁定理8-5.1:當n只鴿子飛進m個巢時，必定最少有一個巢中飛入了Saturday,April13,202414第14頁一個人騎車10小時內(nèi)走完了281公里旅程，已知他第一小時走了30公里，最終一小時走了17公里。證實：他一定在某相繼兩小時中最少走完了58公里旅程。在這10個小時中有9個相繼兩小時，依據(jù)題目給定條件，全部相繼兩小時所走旅程之和應該等于281×2-30-17=515公里。把問題看成是讓515只鴿子飛進9個鴿巢，必有一個鴿巢中飛進了最少Saturday,April13,202415第15頁在任意6個人集體中，要么有3個人相互認識，要么有3個人互不認識。以這6個人中任一個特定人，比如張三作為目標結(jié)構(gòu)兩個子集合S1和S2，其中：S1：由與張三相互認識人組成，S2：由與張三不認識人組成，S1和S2中最少有一個集合不少于Saturday,April13,202416第16頁假如S1中最少有3個人，要是其中任何兩個人都互不認識，那么就找到了3個互不認識人；不然，最少有2個人是相互認識，他們與張三一起組成了3個相互認識人集合。假如S2中最少有3個人