離散第4講 鴿籠原理2.2

計(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)連線的中點(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’)，于是，它們之間連線的中點(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)足命題要求；如果其中有