離散第4講 鴿籠原理2.2

計算機專業(yè)基礎課程授課人：張桂蕓dyxy1999@126.comPowerPointTemplate_Sub1歸納原理2鴿籠原理2第3講歸納原理鴿籠原理Textbook

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

9第3講歸納原理應用舉例例1：在一組367個人中至少有多少人生日相同？至少有兩個人有相同的生日，因為最多只有366種可能的出生日期。例2：在27個英文單詞中至少有多少個單詞以同一字母打頭？一定至少有兩個單詞以同一字母打頭。10第3講歸納原理巧妙使用鴿籠原理在邊長為2的正方形中任取5個點，證明存在兩個點，它們之間的距離不超過。證明如圖將正方形等分為4份。根據(jù)鴿籠原理，至少有一份中含有這5個點中的2個。由于這2個點在一個邊長為1的正方形中，它們之間的距離顯然不超過。

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

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

由鴿籠原理基本形式二，中至少有枚棋子同色，不妨設它們是（黑子）?？紤]，如果其中有兩枚黑子，那么命題已成立；若不然，中至少有三枚白子，不妨設它們是。再考慮，這3枚棋子中必有枚棋子同色，如果其中有兩枚白子，那么與中白子組成長方形白色的四角，滿足命題要求；如果其中有