評論(0

狄利克雷原則

標籤:抽屜原理鴿巢原理組合數學

狄利克雷原則是德國數學家狄利克雷首先明確的提出來並用以證明一些數論中的問題,也稱為狄利克雷原則。

狄利克雷原則即抽屜有時也被稱為鴿巢原理,它是德國數學家狄利克雷首先明確的提出來並用以證明一些數論中的問題,因此,也稱為狄利克雷原則。它是組合數學中一個重要的原理。把它推廣到一般情形有以下幾種表現形式。
形式一:
證明:設把n+1個元素分為n個集合A1,A2,…,An,用a1,a2,…,an表示這n個集合里相應的元素個數,需要證明至少存在某個ai大於或等於2
(用反證法)假設結論不成立,即對每一個ai都有ai<2,則因為ai是整數,應有ai≤1,於是有:
a1+a2+…+an≤1+1+…+1=n<n+1
這與題設矛盾。
所以,至少有一個ai≥2,即必有一個集合中含有兩個或兩個以上的元素。
形式二:
設把n·m+1個元素分為n個集合A1,A2,…,An,用a1,a2,…,an表示這n個集合里相應的元素個數,需要證明至少存在某個ai大於或等於m+1。
(用反證法)假設結論不成立,即對每一個ai都有ai<m+1,則因為ai是整數,應有ai≤m,於是有:
a1+a2+…+an≤m+m+…+m=n·m
n個m
<n·m+1
這與題設相矛盾。
所以,至少有存在一個ai≥m+1
高斯函數:
對任意的實數x,
[x]表示「不大於x的最大整數」.
例如:[3.5]=3,[2.9]=2,
[-2.5]=-3,[7]=7,……
一般地,我們有:[x]≤x<[x]+1
形式三:
證明:設把n個元素分為k個集合A1,A2,…,Ak,用a1,a2,…,ak表示這k個集合里相應的元素個數,需要證明至少存在某個ai大於或等於[n/k]。
(用反證法)假設結論不成立,即對每一個ai都有ai<[n/k],於是有:
a1+a2+…+ak<[n/k]+[n/k]+…+[n/k]
k個[n/k]
=k·[n/k]≤k·(n/k)=n
∴ a1+a2+…+ak<n
這與題設相矛盾。
所以,必有一個集合中元素個數大於或等於[n/k]
形式四:
證明:設把q1+q2+…+qn-n+1個元素分為n個集合A1,A2,…,An,用a1,a2,…,an表示這n個集合里相應的元素個數,需要證明至少存在某個i,使得ai大於或等於qi。
(用反證法)假設結論不成立,即對每一個ai都有ai<qi,因為ai為整數,應有ai≤qi-1,於是有:
a1+a2+…+an≤q1+q2+…+qn-n
<q1+q2+…+qn-n+1
這與題設矛盾。
所以,假設不成立,故必有一個i,在第i個集合中元素個數ai≥qi
形式五:
證明:(用反證法)將無窮多個元素分為有限個集合,假設這有限個集合中的元素的個數都是有限個,則有限個有限數相加,所得的數必是有限數,這就與題設產生矛盾,所以,假設不成立,故必有一個集合含有無窮多個元素。
例題1:400人中至少有兩個人的生日相同.
分析:生日從1月1日排到12月31日,共有366個不相同的生日,我們把366個不同的生日看作366個抽屜,400人視為400個蘋果,由表現形式1可知,至少有兩人在同一個抽屜里,所以這400人中有兩人的生日相同.
解:將一年中的366天視為366個抽屜,400個人看作400個蘋果,由抽屜原理的表現形式1可以得知:至少有兩人的生日相同.
例題2:邊長為1的正方形中,任意放入9個點,求證這9個點中任取3個點組成的三角形中,至少有一個的面積不超過1/8.
解:將邊長為1的正方形等分成邊長為 的四個小正方形,視這四個正方形為抽屜,9個點任意放入這四個正方形中,據形式2,必有三點落入同一個正方形內.現特別取出這個正方形來加以討論.
把落在這個正方形中的三點記為D、E、F.通過這三點中的任意一點(如E)作平行線,如圖可知:
S△DEF=S△DEG+S△EFG
≤ ×h+ = =
例題3:任取5個整數,必然能夠從中選出三個,使它們的和能夠被3整除.
證明:任意給一個整數,它被3除,餘數可能為0,1,2,我們把被3除餘數為0,1,2的整數各歸入類r0,r1,r2.至少有一類包含所給5個數中的至少兩個.因此可能出現兩種情況:
1°.某一類至少包含三個數;
2°.某兩類各含兩個數,第三類包含一個數.
若是第一種情況,就在至少包含三個數的那一類中任取三數,其和一定能被3整除;
若是第二種情況,在三類中各取一個數,其和也能被3整除.
綜上所述,原命題正確.
例題4:九條直線中的每一條直線都將正方形分成面積比為2∶3的梯形,證明:這九條直線中至少有三條經過同一點.
證明:如圖,設PQ是一條這樣的直線,作這兩個梯形的中位線MN
∵這兩個梯形的高相等
∴它們的面積之比等於中位線長的比,即|MH|∶|NH|
∴點H有確定的位置
(它在正方形一對對邊中點的連線上,並且|MH|∶|NH|=2∶3).
由幾何上的對稱性,這種點共有四個,即,圖中的H、J、I、K.已知的九條適合條件的分割直線中的每一條必須經過H、J、I、K這四點中的一點.把H、J、I、K看成四個抽屜,九條直線當成9個蘋果,即可得出必定有3條分割線經過同一點.
例題5:某校派出學生204人上山植樹15301株,其中最少一人植樹50株,最多一人植樹100株,則至少有5人植樹的株數相同.
證明:按植樹的多少,從50到100株可以構造51個抽屜,則個問題就轉化為至少有5人植樹的株數在同一個抽屜里.
(用反證法)假設無5人或5人以上植樹的株數在同一個抽屜里,那只有5人以下植樹的株數在同一個抽屜里,而參加植樹的人數為204人,所以,每個抽屜最多有4人,故植樹的總株數最多有:
4(50+51+…+100)
=4×
=15300
<15301
得出矛盾.
因此,至少有5人植樹的株數相同.
練習:
1.邊長為1的等邊三角形內有5個點,那麼這5個點中一定有距離小於0.5的兩點.
2.邊長為1的等邊三角形內,若有n2+1個點,則至少存在2點距離小於 .
3.求證:任意四個整數中,至少有兩個整數的差能夠被3整除.
4.某校高一某班有50名新生,試說明其中一定有二人的熟人一樣多.
5.某個年級有202人參加考試,滿分為100分,且得分都為整數,總得分為10101分,則至少有3人得分相同
上一篇[男人更年期]  

相關評論

同義詞:暫無同義詞