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

鴿 籠 原 理徐健策 老師1、鴿籠原理的簡單形式及其應用定理：將n1隻或n1隻以上的鴿子放入n個鴿籠內，則至少有一個鴿籠內有二隻或二隻以上的鴿子。證明：假設每個籠子內最多只有一隻鴿子，則n個鴿籠內的鴿子總數小於或等於n，與鴿子總數是n1隻或n1隻以上矛盾。例1-1：(1) 十個人住九間房間，則至少二人共一房間。(2) 十三個人中，必有二人同月生。(3) 三男追二女，必有二男為情敵。(4) 六人分十九本書，一定有人至少分四本書。例1-2：在邊長為2的正三角形中任意放5個點，證明：至少有兩個點之間的距離不大於1。證明：如右圖，在三角形的三邊中點之間連線，整個三角形劃分成四個邊長均為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 。 那麼任意挑出的19個數，必有兩數同一堆，這兩數一定是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，2n1, 2n。 根據鴿籠原理，所取的 n + 1 數中，必有兩個數在同組，而連續的兩正整數是互質的。例1-5：從 1，2，3，2n 中，任取 n + 1 個數，求證：此 n + 1 數中，必有二數，其中之一是另一個倍數。證明：設 a1，a2，an + 1 為取出的 n + 1 個數。 將每一個ai 寫成 ，其中 為0或正整數，為奇數。則，是n + 1個奇數，但他們取值只有n種可能，即1，3，5，2n1。 根據鴿籠原理，一定有 1 i j n + 1，使得 。 不妨設，則 為 的倍數。例1-6：在某一個宴會裡，所參加的人當中，一定會有兩人所認識的朋友個數一樣多。證明：將人數為 n 的一群人分為 A0，A1，An-1。其中 Ai 表示有 i 個朋友的那些人。視 ai 為鴿，Ai 為籠。在此 n 鴿 n 籠，鴿籠原理得不出結論！但稍加注意就可看出 A0 與 An-1 中必有一籠是空的。若 A0 不空，表示有一人跟其他所有人都不是朋友，因此沒有一人認識所有其他 n-1 人，此即表示 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整除。如果對於所有的i = 1,2,n，都有，則n個ri只能有1，2，3，n1 種可能的值，根據鴿籠原理，一定有 1k j n，使得 。因此有 Sj Sk = xk+1 + xk+2 + + xj 可以被n整除。例1-8：一個棋手為了參加一次錦標賽將進行77天的練習，如果他每天至少下一盤棋，而每週最多下12盤棋。證明在這77天內這位棋手有連續的n天共下了21盤棋。證明：設 ai是從第一天到第i天下期的總盤數，i = 1,2,77。所以 1a1 a2 a77 作出序列：a1+21，a2 +21，a77 +21，則 a1+21 a2 +21 a77 +21 132 + 21 = 153現在考慮一個序列：a1，a2，a77，a1+21，a2 +21，a77 +21 這個序列共有154個數，每個數都是小於或等於153的正整數。根據鴿籠原理，其中必有二個數其值相同。所以存在有 i與j使得 ai = aj +21 ( j ，同理 , ，等。則 這n+1個數構成了長度為 n+1 之遞減子數列。 例2-2有大小兩個圓盤，將它們各分為200個相等的扇形。從大圓盤上任選100個扇形塗上紅色，其餘的塗上藍色，而再小圓盤上的每個小扇型中任意塗上紅色或藍色，然後將小圓盤放在大圓盤上，並使兩盤的圓心重合。證明：在旋轉小盤時可以找到某個位置使得至少有100個小扇形落在同樣顏色的大扇形內。證明：任取一個小扇形，當它落在某個大扇形的內部以後，這兩個扇形的顏色就構成一組顏色組合。在小盤旋轉一週的過程中，這個小扇形與大盤上所有的扇形共構成200組顏色組合，其中同色的有100組。因為小盤上有200個不同的扇形，所有的小扇形與所有的大扇形構成的同色的顏色組合總共有100 20020000組，而小盤與大盤的相對位置有200種，每個位置平均具有20000/200100組同色的顏色組合，由推論2，必存在某個位置使得至少有100個小扇形落在同色的大扇形內。3、拉姆西 (Ramsey) 定理鴿籠原理有一種更廣義的形式，那就是組合學上有廣泛應用的拉姆西 (Ramsey) 定理。Ramsey定理是鴿籠原理的推廣，拉姆西(Frank Plumpton Ramsey 19031930)是一個非常聰明的英國數學家，不幸青年早逝。Ramsey定理的數學形式很抽象，他本人倒是舉了一個有名的例子：世界上任意6個人中，總有3個人相互認識，或互相皆不認識。例子：一群人，人數大於等於 6，必然有三知友兩兩彼此認識或有三新鮮人兩兩彼此都不認識。證明： 任取一人名之為 A，其他人，人數至少為 5，可分為二類。與 A 認識者為一類，與 A 不認識者為另一類，由鴿籠原理，必有一類人數大於等於 3。令此三人之名為 B、C、D。若 B、C、D 皆與 A 認識且其中有二人彼此相識，則 A 及此二人為三知友，不然 B、C、D，兩兩不認識，則 B、C、D 為三新鮮人；若 B、C、D 皆與 A 不認識且其中有二人彼比不相識，則 A 與此二人為三新鮮人，不然 B、C、D 中兩兩互相認識，則 B、C、D 為三知友。無論有三知友或三新鮮人，結論都是對的。 6 是滿足上述性質最小整數，它有特殊的意義，我們記為 N(3,3;2) = 6，表示一群人 S，人數未知。但 S 中任 2 人的關係分為兩類，且知道 S 中有一小群人 T，T 人數為 3 而 T 中所有 2 人的關係都屬於同一類，則 S 的人數至少為 6。圖右頂點 A、B、C、D、E 代表五人，其二人之關係分為實線相連的與虛線相連的兩類。很容易看出任意三人其所有 2 人的關係不可能屬於同一類。 記號：為敘述方便，集合 S 的子集 T 若具有 l 個元素我們稱 T 為 S 的 l-子集。拉姆西定理： 將 S 中 l-子集分為 S1，S2， St 等互不相交之 t 類，任意給定不小於 l 之 t 個整數 q1，q2，qt，一定可以找到一個最小整數 ，只要 S 的元素個數，S 中必定有子集 T，其元素個數為某一 qk 且所有 T 之 l-子集都屬於 Sk。 當 l = 2，t = 2，q1 = q2 = 3 時 N(q1,q2;l) = 6 即為上一節所舉的例子。當 l=1 時， = q1 + q2 + + qnt + 1 即是鴿籠原理。 拉姆西定理可以說是將鴿籠原理從裝 1-子集的籠子推廣到裝一般 l-子集的籠子。 稱為拉姆西數，一般情形拉姆西數並不能寫成 q1, q2,qt 及 t 的整齊形式，這也是此定理難說、難懂的原因。拉姆西數由定理可知是確定存在的，但到底為何數，所知極少。譬如 ： N(3,3;2) = 6 N(3,4;2) = 9 N(3,5;2) = 14 N(3,6;2) = 18 N(4,4;2) = 18 N(3,7;2) = 23拉姆西定理的證明運用數學歸納法，雖巧妙但稍微繁複，在此從略。4、鴿籠原理的挑戰善用鴿籠原理常有奇妙驚人的結果，各位是不是也想一顯身手，以下是鴿籠原理對你的挑戰： 1. 在1，2，3，10中任取6數，求證一定存在兩數，其中一個是另一個的整數倍。2. 為什麼一定可以化為循環小數?3. 在直徑為5的圓中放入10個點，求證：其中必有兩個點的距離小於2。 4. 任給7個相異整數,求證其中必有2數,其和或差是10的倍數5. 任給12個整數，求證：其中必有兩個數，它們的和或者差恰是20的倍數。 6. 在任意15個整數中，必有8個整數的和是8的倍數。 7. 求證：在任意給出的12個數中，一定存在8個整數，記為a1, a2, ., a8使得 (a1-a2)(a3-a4)(a5-a6)(a7-a8) 能被1155整除。 8. 已知7個自然數a1, a2, ., a7，把它們重新排列後得到b1, b2, ., b7，求證：(a1-b1)(a2-b2).(a7-b7)為偶數。 9. 從自然數1, 2, ., 99, 100中，任意取出51個數，求證：其中一定有兩個數，它們中的一個是另一個的倍數。 10. 任意52個整數中，必存在兩個數，其和或其差能被100整除。 11. 平面些有15個點，每3點中必有兩點距離小於1，則從中至少可以找到8點，它們均落在半徑為1的一個圓內。 12. 5個人聚會，每人各帶3件禮品，分贈給其餘4人中3人，則至少有5對人是互贈過禮品的。 13. 一次集會其有155個參加，如果其中任何3人中必有兩人握過手，則必能找到一個人，他至少與77人均握過手。 14. 布袋裡有100個球，其中有紅球28個、綠球20個、黃球12個、藍球20個、白球10個、黑球10個。從袋中任意摸出球來，若要摸出至少15個同色球，則需要從袋裡摸出至少多少個球？ 15. 十個足球隊進行單循環比賽(即每個球隊與其他9隊進行且各進行一次比賽)。證明：在賽程的全何時候，至少有兩個隊賽完了相同的場次。 16. 從1、2、.、9中任取4個不同的數字，用這4個數案任意地寫成260位數，從這260個位數中任意截取相鄰的4位數，即得一個四位數。求證：所有這些四位數中，至少有兩個相等。 17. 10名男生與10名女生，任意地站在一個圓圈，另有20名學生(男女生數隨意)在這圈外也圈成一個圓圈，那麼外圈同學總可轉動到某一個位置，使內外圈相對應的同學中，至少有10對是男女相對應的。 18. 把圓周分成36段，將36個數字1、2、.、36任意標在每一段上(每段上恰有一個數字)，那麼一定存在連續的三段，它們的數字之和至少是56。 19. 一個學校其有1000名學生，每人都有一個編號，最大不超這1997，且沒有重複號，那麼最大號碼恰等於兩名同學碼數之和。 20. 在1到91這91個自然數中，任取10個數，其中必有兩個數的商在2/3與3/2之間。 21. 現有17位同學，其中每一位都與其他人上網寄，在他們的中共討論3個數學題目，而任兩位同學只討論一個數學題目，試證明至少有3位同學，他們彼此討論的是同一個題目22. 假設店老闆每日至少賣出一台電視，每星期至多賣出12台電視，共賣了十週之後，試證明店老闆必有在某一連續