組合數(shù)學(xué)幻燈片2.1鴿籠原理與Ramsey定理課件

1、第二章鴿籠原理與Ramsey定理 鴿籠原理又稱抽屜原理，它是組合數(shù)學(xué)中的一個(gè)重要的也是最基本的原理。這個(gè)原理是指：“有n只鴿子，飛進(jìn)m(nm)個(gè)鴿籠時(shí)，至少有一個(gè)鴿籠內(nèi)有兩只以上的鴿子”。這是一個(gè)顯而易見的道理，然而，它卻有許多重要而有趣的應(yīng)用和幾種不同的表達(dá)形式，這節(jié)先介紹鴿籠原理的簡單表達(dá)形式。鴿籠原理的簡單形式2.1 證明：用反證法。如果n個(gè)盒子中每個(gè)盒子至多放入一個(gè)物體，則放入n個(gè)盒子中的物體總數(shù)至多為n個(gè)。這與假設(shè)有n+1個(gè)物體矛盾。從而定理得證。必須注意，鴿籠原理只指出了至少存在這樣的盒子，并沒有給出“確定哪一個(gè)盒子有此性質(zhì)”的方法。因此，它只能用來解決存在性問題。定理2.1如果把

2、n+1個(gè)物體放到n個(gè)盒子中去，則至少有一個(gè)盒子中放有兩個(gè)或更多的物體。例1一教師每周上7次課，則這教師至少有一天要上兩次課(除星期天)。在此例中，把“天”當(dāng)作“盒子”。例2證明：把5個(gè)頂點(diǎn)放到邊長為2的正方形中，至少存在兩個(gè)頂點(diǎn)，它們之間的距離小于或等于 。證明：把邊長為2的正方形分成四個(gè)相等的小正方形，則每個(gè)小正方形的對角線長為 。如果把每個(gè)小正方形當(dāng)作一個(gè)盒子，由鴿籠原理知，把5個(gè)頂點(diǎn)放入4個(gè)盒子中，必有一個(gè)盒子中放入了兩個(gè)頂點(diǎn)。即必有一個(gè)小正方形中有兩個(gè)頂點(diǎn)。而小正方形的對角線長為 。也就是說，小正方形中任意兩點(diǎn)的最大距離為 。這就證明了本題。附，試證明把四個(gè)點(diǎn)放入23的矩形中，至少有兩

3、個(gè)點(diǎn)之間的距離不超過 。例3設(shè) 為三個(gè)任意的整數(shù)，為 的任一排列，則 中至少有一個(gè)是偶數(shù). 證明：由鴿籠原理知， 這三個(gè)整數(shù)中至少有兩個(gè)數(shù)同為偶數(shù)或奇數(shù)。而 是 的一個(gè)排列. 因此， , 這六個(gè)數(shù) 中至少有4個(gè)數(shù)同奇偶性。將這4個(gè)數(shù)放入3個(gè)盒子時(shí)，必有兩個(gè)在同一盒子中，其差為偶數(shù)。故 中至少有一個(gè)為偶數(shù)。 例4在給定的n個(gè)整數(shù) 中，存在k和 ，使得 能被n整除。 證明：考慮n個(gè)和：(2)如果這n個(gè)和中沒有一個(gè)能被n整除，則這些和被n除時(shí)必有1，2，n-1這樣的余數(shù)。由于有n個(gè)和，且只有n-1個(gè)余數(shù)，于是我們可以構(gòu)造n-1個(gè)盒子，第i個(gè)“盒子”裝被n除余數(shù)為i的數(shù)(i=1，2，n-1)。分兩種情

4、況： (1)如果這n個(gè)和中有一個(gè)能被n整除，則結(jié)論成立。由鴿籠原理知，用n除各和時(shí)有兩個(gè)和的余數(shù)是相同的。所以存在整數(shù)k和 ,使得 和 被n除時(shí)有相同的余數(shù)r，即兩式相減得由上式知， 能被n整除。這就證明了本題的結(jié)論。 證明： 因?yàn)槿我徽麛?shù)都可以寫成2kl的形式，其中k是非負(fù)整數(shù)，l是正的奇數(shù)。顯然，從1到2n中只有n個(gè)奇數(shù)。由于選出的n+1個(gè)數(shù)都可以寫成2kl的形式，而l的取值只有n種可能。由鴿籠原理知至少有兩個(gè)數(shù)所對應(yīng)的奇數(shù)l是相同的，于是對應(yīng)于k小的那個(gè)整數(shù)可以整除對應(yīng)于k大的另一個(gè)整數(shù)，故本題結(jié)論得證。例5從1，2，2n中任意選出n+1個(gè)數(shù)，這n+1個(gè)數(shù)中，一定存在兩個(gè)數(shù)，其中一個(gè)整

5、數(shù)能整除另外一個(gè)整數(shù)。例6在任意的一群人中，一定有這樣的兩個(gè)人，他們在這群人中有相同數(shù)目的熟人。證明： 設(shè)任意一群人的個(gè)數(shù)為n，且n2。(因?yàn)閚=1時(shí)，不成其為一個(gè)人群)。當(dāng)n=2時(shí)，這兩個(gè)人或者互相是熟人或者互相是生人。當(dāng)這兩個(gè)人是熟人時(shí)，則他們的熟人都是1個(gè)人。當(dāng)這兩個(gè)人互不相識(shí)時(shí)，則他們的熟人都是0。故當(dāng)n=2時(shí)，本例結(jié)論成立。當(dāng)n3時(shí)，假設(shè)用 (i=1,2,n)表示第i個(gè)人的熟人數(shù)目。下面分三種情況討論。(1)假設(shè)這群人中每人都有熟人。即 0且1 n-1。視 X1,X2 ,Xn為n個(gè)物體，1，2，n-1為n-1個(gè)盒子。這樣一來，問題就成為把n個(gè)物體放入n-1個(gè)盒子的問題了。由鴿籠原理知

6、至少有兩個(gè)物體放在同一盒子中。不妨設(shè) 與 在同一盒子中( )，即 = 。這表明第k個(gè)人與第l個(gè)人有相同數(shù)目的熟人。在這種情況下，本例結(jié)論成立。(2)假設(shè)這群人中只有1個(gè)人沒有熟人，不妨設(shè)這個(gè)人就是第n個(gè)人。即 =0且1 n-2(i=1,2,n-1)。同樣視 , , 為n-1個(gè)物體，視1,2,n-2為n-2個(gè)盒子，則由鴿籠原理知至少有一個(gè)盒子里放了兩個(gè)物體。不妨設(shè) 與 ( )在同一盒子里，即 = 。故第 個(gè)人與第 個(gè)人的熟人數(shù)目相同。故在第二種情況下，本例結(jié)論也是成立的。(3)假設(shè)在這群人中至少有兩個(gè)人都沒有熟人，也就是說這兩個(gè)人的熟人數(shù)目為0。故在這種情況下，本例結(jié)論仍然成立。綜上所述，本例結(jié)論成立。 解：設(shè) 為第一天該棋手下棋的盤數(shù)， 是第一、二天該棋手下棋盤數(shù)的和， 是第一、二、j天該棋手下棋盤數(shù)的和，j=1,2,77，于是序列是嚴(yán)格遞增序列，且例7 一棋手為參加一次錦標(biāo)賽要進(jìn)行77天 的訓(xùn)練，如果他每天至少下一盤棋，且每周至多下12盤棋，試證明不管他怎樣安排，必存在相繼的若干天，在這段時(shí)間中他恰好下棋21盤。 于是序列 也是嚴(yán)