鸽笼原理的简单形式及其应用

《鸽笼原理的简单形式及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、鴿籠原理徐健策老師§1、鴿籠原理的簡單形式及其應用定理：將n＋1隻或n＋1隻以上的鴿子放入n個鴿籠內，則至少有一個鴿籠內有二隻或二隻以上的鴿子。證明：假設每個籠子內最多只有一隻鴿子，則n個鴿籠內的鴿子總數小於或等於n，與鴿子總數是n＋1隻或n＋1隻以上矛盾。例1-1：(1)十個人住九間房間，則至少二人共一房間。(2)十三個人中，必有二人同月生。(3)三男追二女，必有二男為情敵。(4)六人分十九本書，一定有人至少分四本書。例1-2：在邊長為2的正三角形中任意放5個點，證明：至少有兩個點之間的距離不大於1。證明：如右圖，

2、在三角形的三邊中點之間連線，整個三角形劃分成四個邊長均為1的小三角形，由鴿籠原理，5個點至少有兩個點落在同一個小三角形裡，而這兩個點之間的距離一定小於等於1。例1-3：從等差數列：1、4、7、10、13、…、100中，任意挑出19個數，求證：此19個數中必有二數，其和為104。證明：把1、4、7、10、13、…、100這些數，分成如下的18堆：{1}，{52}，{4,100}，{7,97}，{10,94}，{13,91}，{16,88}，…，{49,55}。Page8鴿籠原理徐健策老師那麼任意挑出的19個數，必有兩數

3、同一堆，這兩數一定是4與100，或7與97，或，…，或49與55。此兩數之和為104。例1-4：從{1,2,3,…,2n}中，任取n+1數，求證：此n+1數中，必有兩數互質。證明：把1,2,3,...,2n分成如下的n組：{1,2}，{3,4}，…，{2n－1,2n}。根據鴿籠原理，所取的n+1數中，必有兩個數在同組，而連續的兩正整數是互質的。例1-5：從1，2，3，…，2n中，任取n+1個數，求證：此n+1數中，必有二數，其中之一是另一個倍數。證明：設a1，a2，…，an+1為取出的n+1個數。將每一個ai寫成，其

4、中為0或正整數，為奇數。則，，…，是n+1個奇數，但他們取值只有n種可能，即1，3，5，…，2n－1。根據鴿籠原理，一定有1i

5、8鴿籠原理徐健策老師此即表示An-1，是空的；若An-1不空，表示有一人認識所有其他n-1人，因此不可能有一人跟其他所有人都不是朋友，此即表示A0是空的。故或A0或An-1為空！不管如何，所有人事實上分為n-1類。由鴿籠原理，有一類至少有二人。換言之，有二人各有一樣多的朋友。例1-7：設x1、x2、…、xn是n個正整數，證明其中存在著連續的若干個數，其和為n的倍數。證明：令Si=x1+x2+…+xi，i=1,2,…,n。我們把Si除以n的餘數記作ri，。如果有i，使得ri=0，則x1+x2+…+xi可以被n整除。如果

6、對於所有的i=1,2,…,n，都有，則n個ri只能有1，2，3，…，n－1種可能的值，根據鴿籠原理，一定有1k

7、21<132+21=153現在考慮一個序列：a1，a2，…，a77，a1+21，a2+21，…，a77+21這個序列共有154個數，每個數都是小於或等於153的正整數。根據鴿籠原理，其中必有二個數其值相同。Page8鴿籠原理徐健策老師所以存在有i與j使得ai=aj+21(j

8、盒內至少含有q2個物品……，或者有一盒內至少含有qn個物品。證明：對於i=1,2,…,n，假設第i個盒子裡最多含有qi－1個物品，則n個盒子裡物品數的總和不超過q1+q2+…+qn－n與條件的物品數矛盾。推論1：若將n(r－1)+1個物品放入n個盒子裡，則至少有一個盒子裡含有r個或者更多的物品。證明：取q1=q2=…=qn=r即可。推論2：設n