鴿巢原理

• 前言
• 鴿巢原理
• • 運用1
  • 運用二
  • 運用三
• 鴿巢原理的推廣
• • 推論
  • • 運用一
    • 運用二
• 鴿巢原理在幾何上的作用
• 鴿巢原理對于數學的證明

前言

鴿巢原理又稱抽屜原理或鞋盒原理，這個原理最早是由狄利克雷（Dirichlet）提出的。鴿巢原理是解決組合論中一些存在性問題的基本而又有力的工具。它是組合數學中最簡單也是最基本的原理，從這個顯而易見的原理出發，可以導出許多并非顯而易見的有趣結果，而這些結果常常是令人驚奇的。特別是Ramsey理論產生了重要而深遠的影響。1928年，年僅24歲的英國杰出數學家F. P. Ramsey發表了著名論文《論形式邏輯中的一個問題》，他在這篇論文中，提出并證明了關于集合論的一個重大研究成果，現已公認為Ramsey定理。他開拓的這一新領域至今在理論上仍十分活躍，而且近年來在科學技術領域獲得了成功的應用。

鴿巢原理對于我們在解題的時候對解法存在性和正確性的一種強有力的方法。

鴿巢原理

定理 若有n+1只鴿子飛回n個鴿巢，則至少有一個鴿巢里有不少于兩只鴿子。
我們還可以這么描述，若由n+1個東西放入n個盒子中，則至少有一個盒子有不少于兩個物品。
證明：(反證法)假設n個鴿巢中，每個鴿巢里至多有一只鴿子，則鴿子的總數至多為n，但是有n+1只鴿子，矛盾。
[說明]：(1)定理的條件?結論?實質上指出了一種必然性。
(2)鴿巢原理的等價原理：若有n+1個物件放入n個盒子，則至少有一個盒子里有不少于兩個的物件。
(3)鴿巢原理的應用關鍵是：
“認準鴿子”、“構筑鴿巢”。

運用1

從整數1，2，…，100中任選51個整數，證明在選取的這些整數中必存在兩個整數，其中之一可被另一個整除。

證明：
對于1到100之間的任何整數，都可以表示為$2^n.\alpha$的形式，其中n≥0，且α為50個奇數1，3，…，99之中的數。故在所任選的51個整數中，至少有兩個整數含有相同的奇數因子α，令這兩個整數為$2^r?\alpha 和2^s?\alpha ，不妨r>s，則2^s?\alpha 能被2^r?\alpha 整除$。

• 對于1到100之間的任何整數，都可以表示為$2^n.\alpha$的形式 .這是因為我們知道任何一個數都能有唯一的質因子乘積表示。在這些質因子中，2后邊的都是奇數，因此無論多少個奇數的乘積任然是奇數。因此就有上面的結論。

運用二

$有9個任給定的整數a_1,a_2,?,a_9,試證明必存在兩個整數k和l(0\le k\le l\le 9)，使得a_{k+1}+a_{k+2}+...+a_l能被9整除$。

證明：
首先，如果某個 $a_i(1\le i\le 9)$ 能被9整除，取k=l=i、得證。
否則，由9個整數可得到9個連續的和式： $a1,a1+a2,a1+a2+a3,....,a1+a2+?+a9$。 如果某個 $a1+a2+?+ai(1<i\le 9)$ 能被9整除，即存在兩個整數$k和l(0\le k\le 1=i\le 9)$，得證。
否則，上述9個和式被9除余數可能為1，2，…，8，由鴿巢原理知最少存在兩個和式被9除余數相同，不妨設為 $a1+a2+?+ak=a?9+r和a1+a2+?+al=9?b+r,(k<l)$, 那么它們的差 $a_{k1}+a_{k+2}+?+a_l=9?(a?b)(0\le k\le 1\le 9)$能夠被9整除。得證

• 對于這個例子我們可以推廣為: $$有K個數，那么必有一個連續的序列的和能被S整除。(S<=K)$$

運用三

$在一個正六邊形內任置7點，則至少有兩點之間的距離小于該正六邊形外接圓的半徑$

證明：連接這個正六邊形的三條對角線，得到六個小正三角形，每個正三角形的直徑都恰是正六邊形外接圓的半徑。正六邊形內置7點，由鴿巢原理知，總有一個三角形內至少有兩個點，顯然它們的距離小于正六邊形外接圓的半徑。

鴿巢原理的推廣

定理：設m?,m?,… ,mn 均為正整數.如果有 m1+m2+?+mn?n+1 只鴿子飛回n個鴿巢，則或者第一個鴿巢至少有m，只鴿子，或者第二個鴿巢至少有m，只鴿子，…，或者第n個鴿巢至少有m，只鴿子。
證明：（反證法）若定理結論不成立，即第一個鴿巢至多有 m1?1 只鴿子，第二個鴿巢至多有m2-1只鴿子，…，第n個鴿巢至多有m，-1只鴿子。則鴿子總數至多為
$(m_1?1)+(m_2?1)+?+(m_n?1)=m_1+m_2+?+m_n?n$
這與設定的鴿子數 m1+m2+?+mn?n+1 相矛盾。得證。

[注意]：
(1)鴿巢原理的一般形式是推廣形式的特例，事實上，當 m1=m2=??mn=2 時，
m1+m2+?+mn?n+1=n+1
(2)鴿巢原理的等價表示：設m，，m2，… mn 為正整數，若有 m1+m2+?+mn?n+1 個球放入n個盒子，則或者第一個盒子至少有m，個球，或者第二個盒子至少有m，個球，…，或者第n個盒子至少有m，個球。

推論

推論1：$如果m_1=m_2=?=m_n=r,若將n(r?1)+1個球放入n個盒子中，則至少有一個盒子不會少于r個球。$

推論2；$如果n個正整數m_1，m_{?},?,m_n的平均數m_1+m?2+?+m_n>r?1則m_1,m_2,?,m_n中至少有一個正n整數不會小于r。$

推論3：$有m個球放入n個盒子，則至少有一個盒子中有不?\frac{m?1}{n}?+1個球。$

這三個推論在證明的時候很常用，下面舉幾個例子。

運用一

• 設有兩個隊Q，和Q，每隊都有30人，其中Q隊由15名男孩和15名女孩組成，Q，隊男、女孩人數不限這兩隊按序號面對面站好。然后，Q，隊不動，Q.隊迂回往右錯動，每次依序錯動一個位置。試證明當Q：錯動到某一位置上時，Q，和Q，在對應位置上的兩個小孩至少有15對是性別相同的。

Q隊迂回錯動一圈再回到初始狀態時，每個小孩，無論是男孩還是女孩，在對應位置上都與Q?隊的15個小孩同性別。故同性別的總對數為15×30=450。
因此，每個錯動位置上同性別的平均對數為 45030=1 15>15-1。由推論2知，必存在某一位置，當Q錯動到這個位置上時，則性別相同的小孩至少有15對。

• 無論是男孩還是女孩，在對應位置上都與Q?隊的15個小孩同性別 ： 意思是好比我是一個男孩，那么我在轉一周之后一定會與對面的15個男孩碰面，那么有15次。

運用二

• $若給定n2+1個不等實數構成的序列a_{?},a_{?},\dots a_{n^2+1}則該序列中至少存在一個由n+1個實數組成的單調遞增或單調遞減子序列。$

證明：不妨先考慮尋找單調遞增子序列。
令$m_i$表示從$a_i$開始最長遞增子序列的項數或長度。若有某個$m_i\ge n+1$ 則定理得證。
否則，注意到給定的序列有 $n^2+1$ 個實數，故可產生 $n^2+1個長度，m_1,m_2?m_{n^2+1},如果全部的m_i<n+1,(i=1,2,?,n^2+1則這些整數必定在1和n之間。相當于把n^2+1個球放入n個盒子$。
由推論1知，$(取m_1=m_2=?=m_{n^2+1}=r=n+1,將n(r?1)+1=n^2+1個球放入n個盒子中，至少有某個盒子里不少于r個球。)在m_1，m_2,?,m_{n^2+1}中至少有r=n+1個數相等。不妨設m_1=m_2=?=m_{n+1}=m,且1\le i1<i2<?<in+1\le n2+1,或者說a，，ai2,?,ain+1有相同的m值，則必有a1>a1>?>ai+1即存在著一個長度為n+1的單調遞減子序列。若不然，假如a{i}_1<a{?}_{?}會有m_{i_1}=m_{i_2}+1=m_{i_2}=m,矛盾$。

鴿巢原理在幾何上的作用

在邊長為1的正方形內任取5個點，那么至少有兩個點之間的距離不會超過$\frac{\sqrt{2}}{2}$ .證明：將其4等分在每一個小方格中最遠紅色部分，為$\frac{\sqrt{2}}{2}$ 。對于5個點，由鴿巢原理知至少有兩個點在一個格子中，那么這兩個點的距離小于$\frac{\sqrt{2}}{2}$

在邊長為1的等邊三角形內任取5個點，至少有兩個之間的距離小于$\frac{1}{2}$.證明類似上一題，圖形如下

鴿巢原理對于數學的證明

$a_1,a_2,a_3,為三個任意整數，b_1{b}_2{b}_3為a_1,a_2,a_3的任一排列，則a_1?b_1,a_2?b_2,a_3?b_3中至少有一個為偶數。$證明：假設其全為奇數，那么三個奇數相加任然為奇數，我們有$a_1?b_1+a_2?b_2+a_3?b_3=0,0不是奇數，故矛盾。$

任取11個整數，求證其中至少有兩個它們的差是10的倍數。證明：0也是符合的，由11個數，,它們的差為10的倍數等價于它們對10取余之后的余數相同，由余數為0-9，一共10個，由鴿巢原理知，至少有兩個數的余數相同，那么這兩個的差符合條件。

上一問的推廣：設m為一自然數，任取m+1個整數，則其中至少有2個整數的差是m的倍數。

總結

以上是生活随笔為你收集整理的算法之组合数学及其算法篇(二） ----- 鸽巢原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。