組合數(shù)學鴿巢原理例題初中教育

1/1組合數(shù)學鴿巢原理例題-初中教育

組合數(shù)學鴿巢原理例題

鴿巢原理例題

組合數(shù)學鴿巢原理例題

證明[1,2n]中任意n+1個不同的數(shù)中至少有一對數(shù)互質設這n+1數(shù)為a1a2…an+1,令bi=ai+1(i=1,2,…,n)。明顯，b1b2…bn=2n,a1,…,an+1,b1,…,bn這2n+1個數(shù)中必有二數(shù)相等，即存在bi與ai+1相等，而bi=ai+1,而ai與ai+1(即ai+1)是互質的。

組合數(shù)學鴿巢原理例題

一人以11周時間預備考試，他打算每天至少做一道題，但每周不多于12題。證明：存在連續(xù)的若干天，在這些天時他恰好做了21題。改為更少的題數(shù)如何？改為22題如何？令ai表示從第一天到第i天所做的題數(shù)之和。由于每天至少做一題，有：a1a2…a77=12*11=132?？紤]序列:a1+21,a2+21,…,a77+21(=153).兩個序列共有154個數(shù)，而ai≠aj(當i≠j時),同理，ai+21≠aj+21(當i≠j時),所以，必有某個aj=ai+21,即從第i+1天到第j天共做了21題。原命題改為小于21題，明顯是成立的。

組合數(shù)學鴿巢原理例題

續(xù)：22題的狀況若存在某一周沒有做滿12題，則a77+22154,使得這154個數(shù)最多到153,從而仍有aj=ai+22;若每周都做滿12題，那么a1,a2,…,a77,a1+22,a2+22,…,a77+22這154個數(shù)恰在1~154之間。

若不存在i,j使得aj=ai+22,則它們取值遍歷1,2,…,154。即有a1=1,a2=2,…,a22=22。那么，他在第一周里只做了7題，與每周做滿12題假設沖突。所以，存在連續(xù)的若干天，他恰好做了22題。

組合數(shù)學鴿巢原理例題

設a1,a2,…,an是1,…,n的一個排列，證明，當n是奇數(shù)時，(a1-1)(a2-2)…(an-n)是一偶數(shù)。證明：只須證明上述因子中有一個是偶數(shù)即可。由于只要有一個因子是偶數(shù)，則積必為偶數(shù)。n是奇數(shù)時，1~n中有(n+1)/2個奇數(shù)，(n-1)/2個偶數(shù)。從而，a1,a3,…,an中至少有一個是奇數(shù),設為a2i+1這樣以來，(a2i+1-(2i+1))為偶數(shù)。乘積為偶數(shù)。證畢。

組合數(shù)學鴿巢原理例題

證明：在1~200中可選取100個數(shù)它們中任何兩個數(shù)互素。并證明所選的100個數(shù)中的最小數(shù)不小于16。明顯，當選出的數(shù)為101時，可用鴿巢原理證明，必存在兩個數(shù)是倍數(shù)(或整除)關系。本題證明參見《輔導》P301,7.7題

組合數(shù)學鴿巢原理例題

證明：任給m個正整數(shù)a1,a2,…,am,必存在連續(xù)的若干項，其和是m的倍數(shù)(能被m整除)。證明：構造數(shù)列：S1=a1,S2=a1+a2,…,Sn=a1+a2+…+an;若某個Si已經可被m整除，則得證。設不存在被整除的狀況，則每個Si模m的余數(shù)ri滿意：1≤ri≤m-1。這樣的ri共有m個。依據(jù)鴿巢原理，存在ij,但ri=rj。即Si與Sj同余。從而有：Sj-Si=km=ai+1+ai+2+…+aj.得證。

組合數(shù)學鴿巢原理例題

思索題1.2.一個1*1的方格里任選5個點，則必存在兩點，其距離√2/2.空間直角坐標系中，我們把(x,y,z)坐標均為整數(shù)的點簡稱為格點，證明，任意9個格點中，必存在兩點，其連線的中點亦是格點。設西工大在北京的辦事處有90間房間。每次總是有100人中的90人到那里出差，試設計一