離散第4講 鴿籠原理2.2_第1頁(yè)
離散第4講 鴿籠原理2.2_第2頁(yè)
離散第4講 鴿籠原理2.2_第3頁(yè)
離散第4講 鴿籠原理2.2_第4頁(yè)
離散第4講 鴿籠原理2.2_第5頁(yè)
已閱讀5頁(yè),還剩13頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)課程授課人:張桂蕓dyxy1999@126.comPowerPointTemplate_Sub1歸納原理2鴿籠原理2第3講歸納原理鴿籠原理Textbook

Page25to28《離散數(shù)學(xué)》第4講內(nèi)容提要鴿籠原理的基本形式基本形式一基本形式二巧妙應(yīng)用鴿籠原理鴿籠原理的加強(qiáng)形式*加強(qiáng)形式一加強(qiáng)形式二加強(qiáng)形式三4第3講歸納原理鴿籠原理的直觀解釋5第3講歸納原理鴿籠原理的直觀解釋十只鴿子飛進(jìn)9只籠子6第3講歸納原理鴿籠原理的直觀解釋十只鴿子飛進(jìn)9只籠子7第3講歸納原理小檔案——狄里克雷鴿籠原理也叫做抽屜原理,狄里克雷原理,以19世紀(jì)德國(guó)數(shù)學(xué)家狄里克雷的名字命名狄里克雷在數(shù)論中有許多重要發(fā)現(xiàn),并對(duì)于n=5的情況證明了費(fèi)馬的最后的定理,即x5+y5=z5不存在非平凡的整數(shù)解狄里克雷經(jīng)常在工作中使用鴿籠原理十分基本、非常重要、應(yīng)用極其廣泛的數(shù)學(xué)原理。是解決存在性問(wèn)題的基本工具。8第3講歸納原理鴿籠原理的基本形式基本形式一:如果把n+1個(gè)(n為正整數(shù))對(duì)象放入n個(gè)盒子里,那么至少有一個(gè)盒子中放有兩個(gè)或兩個(gè)以上的對(duì)象證明:反設(shè)每個(gè)盒子都少于兩個(gè)物體,則n個(gè)盒子里最多放置了n個(gè)物體,與前提矛盾。

9第3講歸納原理應(yīng)用舉例例1:在一組367個(gè)人中至少有多少人生日相同?至少有兩個(gè)人有相同的生日,因?yàn)樽疃嘀挥?66種可能的出生日期。例2:在27個(gè)英文單詞中至少有多少個(gè)單詞以同一字母打頭?一定至少有兩個(gè)單詞以同一字母打頭。10第3講歸納原理巧妙使用鴿籠原理在邊長(zhǎng)為2的正方形中任取5個(gè)點(diǎn),證明存在兩個(gè)點(diǎn),它們之間的距離不超過(guò)。證明如圖將正方形等分為4份。根據(jù)鴿籠原理,至少有一份中含有這5個(gè)點(diǎn)中的2個(gè)。由于這2個(gè)點(diǎn)在一個(gè)邊長(zhǎng)為1的正方形中,它們之間的距離顯然不超過(guò)。

11第3講歸納原理例2.9:三維空間中有9個(gè)格點(diǎn)(各坐標(biāo)均為整數(shù)的點(diǎn)),證明所有格點(diǎn)連線(xiàn)的中點(diǎn)中至少有一個(gè)也是格點(diǎn)。證:我們知道,格點(diǎn)的三個(gè)坐標(biāo)的奇(用1表示)偶(用0表示)狀況只有8個(gè):(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)。因此,根據(jù)鴿籠原理基本形式一,9個(gè)格點(diǎn)中至少有兩個(gè)格點(diǎn)的坐標(biāo)的奇、偶狀況相同。設(shè)這兩個(gè)格點(diǎn)的坐標(biāo)是(a,b,c)和(a’,b’,c’),于是,它們之間連線(xiàn)的中點(diǎn)的坐標(biāo)是((a+a’)/2,(b+b’)/2,(c+c’)/2),由于(a,b,c)和(a’,b’,c’)的奇、偶狀況相同,((a+a’)/2,(b+b’)/2,(c+c’)/2)中各坐標(biāo)均為整數(shù),故該點(diǎn)是一個(gè)格點(diǎn)。12第3講歸納原理鴿籠原理的基本形式基本形式二:如果把m個(gè)對(duì)象放入n個(gè)盒子里(m、n均為正整數(shù)),那么有一個(gè)盒子中至少放入了(=r)個(gè)對(duì)象證明:如果每個(gè)盒子包含的物體都不多于,那么物體總數(shù)最多為,從而不多于m-1,與前提矛盾。在基本形式二中,令m=n+1,則得到基本形式一13第3講歸納原理應(yīng)用舉例例3:100個(gè)人中至少有多少個(gè)人同一個(gè)月出生?至少有9個(gè)人同一個(gè)月出生.例4:如果有5種可能的成績(jī)A、B、C、D、E,那么一個(gè)班里至少有多少個(gè)學(xué)生才能保證至少有6個(gè)學(xué)生得到相同的分?jǐn)?shù)?至少有26個(gè)學(xué)生在鴿籠原理的許多有趣應(yīng)用中,必須以某種巧妙的方式找到或設(shè)計(jì)問(wèn)題中的盒子(n)、放入盒子里的物體(m)及盒子中物體的個(gè)數(shù)r。14第3講歸納原理應(yīng)用舉例例5:為保證一個(gè)省的2500萬(wàn)個(gè)電話(huà)有不同的10位號(hào)碼,所需的區(qū)號(hào)至少是多少?假定電話(huà)號(hào)碼是Nxx-Nxxxxxx形式,前3位是區(qū)號(hào),N表示2到9的十進(jìn)制數(shù)字,x表示任意十進(jìn)制數(shù)字。

所需的區(qū)號(hào)至少是4個(gè)(201,202,203,204):15第3講歸納原理例2.11:從集合{1,2,…,200}中任選101個(gè)數(shù)。證明:無(wú)論怎樣選取,在選取的這些數(shù)中,必定存在兩個(gè)數(shù),使得其中之一可以被另一個(gè)整除。證:我們知道,任何正整數(shù)都可以寫(xiě)成2k·a的形式,其中k是自然數(shù),a是奇數(shù)。對(duì)于集合{1,2,…,200}中的數(shù),a只能是1,3,5,…,199這100個(gè)數(shù)中的一個(gè)。于是,根據(jù)鴿籠原理基本形式一,在選取的101個(gè)數(shù)中,有兩個(gè)數(shù)的上述表示形式中的a是相同的。即分別是2k·a,2j·a,它們之中自然有一個(gè)可以被另一個(gè)整除。16第3講歸納原理例2.13取黑白圍棋子21枚,黑白數(shù)目不限,排列成3行7列的長(zhǎng)方形。求證:無(wú)論怎樣排放,都可以從中找到一個(gè)長(zhǎng)方形,使該長(zhǎng)方形的四個(gè)角的棋子同色。證.設(shè)21枚棋子排成的長(zhǎng)方形如下:

由鴿籠原理基本形式二,中至少有枚棋子同色,不妨設(shè)它們是(黑子)。考慮,如果其中有兩枚黑子,那么命題已成立;若不然,中至少有三枚白子,不妨設(shè)它們是。再考慮,這3枚棋子中必有枚棋子同色,如果其中有兩枚白子,那么與中白子組成長(zhǎng)方形白色的四角,滿(mǎn)足命題要求;如果其中有

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論