組合數(shù)學(xué)中的抽屜原則一般分三種形式來研究,即抽屜原則的最簡形式、抽屜原則的一般形式和抽屜原則的對稱形式,本文只研究前面的兩種形式。
抽屜原則的最簡形式:把n+1個或更多物體放到n個抽屜中去,那么至少有一個抽屜里要放進(jìn)兩個或者更多的物體。下面我們來介紹抽屜原則的一般形式。它有如下定理:
定理1 如果將m個物體放到n個抽屜里去,則至少一個抽屜里含有■+1物體(其中■表示不超過■的最大整數(shù))。
以后我們就把定理1稱為抽屜原則的一般形式。
證明:小于m的n的最大倍數(shù)是由■減去其分?jǐn)?shù)部分所得的整數(shù),這就是■。如果不存在有一個抽屜,它含有■+1個物體,則每個抽屜含的物體最多是■??偣灿衝個抽屜,所以這n個抽屜所含有的物體總數(shù)小于等于n·■≤n·■=m-1<m。
這與已知有m個物體矛盾,所以至少有一個抽屜有■+1個(或更多)物體。
我們再來看自由差集:
定義 設(shè)M為整數(shù)集。若在M中不存在這樣的數(shù),使得它等于M中某兩個數(shù)字之和,或等于M中某個數(shù)的2倍。則M稱為自由差集。否則就稱為非自由差集。
由以上定義很容易得出兩個性質(zhì)定理:
定理2 若M為自由差集,則M中任意兩數(shù)的差,一定不屬于M。
證明:反證法,設(shè)x∈M,y∈M,且x-y∈M。根據(jù)M的定義,因?yàn)閤=(x-y)+y■M,與假設(shè)矛盾,所以x-y■M。
定理3 設(shè)x,y,z是自由差集M中任意3個數(shù),那么不僅x-y,x-z,z-y不屬于M,而且差(x-y)-(x-z)也不屬于M。
證明:因?yàn)椋▁-y)-(x-z)=z-y■M。證畢。
有了上面的原則、定義和定理,我們來研究下面問題。
一個國際社團(tuán)的成員來自6個國家,共有成員2011人,用1,2,…,2010,2011編號,請證明,該社團(tuán)至少有一個成員的順序號數(shù)等于它的兩個同胞的順序號數(shù)之和,或等于同胞的順序號數(shù)的2倍。
解:設(shè)A1,A2,A3,A4,A5,A6代表6個國家,今有2011個成員,所以由抽屜原則的一般形式即定理1可知,至少有一個國家,其成員至少有■+1=336人,不妨假設(shè)A1國家中至少有336人成員,并假定這336個成員的號碼數(shù)是a1>a2>a3>…>a336
現(xiàn)在,用反證法來證明。假設(shè)結(jié)論不成立,于是A1,A2,A3,A4,A5,A6都適合自由差集的定義,即它們均為自由差集,由引理可得a1-ai■A1(i=2,3,…,336)。
由于0<a1-ai<a1≤2011,
所以這些a1-ai也應(yīng)當(dāng)都是號碼數(shù)。由于a1-ai■A1,所以必定屬于A2,A3,A4,A5,A6這5個國家中。因?yàn)檫@里共有335個差數(shù),所以由定理1可知,至少一個國家含有這335個差數(shù)中至少■+1=67個差數(shù)為號碼數(shù)的成員。并假設(shè)這67個成員的所在國家為A2,其號碼假設(shè)為b1>b2>…>b67
由于A2也為自由差集,所以b1>bj■A2(j=2,3,…,67)
又由定理3得 b1-bj=(a1-aj1)-(a1-aj2)=aj2-aj1■A1,
所以這里b1-bj必屬于A3,A4,A5,A6這4個國家。因?yàn)檫@里有66個差數(shù),所以由定理1可知,至少有一個國家含有這66個差數(shù)中至少■+1=17個差數(shù)為號碼數(shù)的成員。并假設(shè)這17個成員的所在國家為A3,其號碼數(shù)為c1>c2>…>c17。
由于A3也為自由差集,所以c1-ck■A3 (k=2,3,…,17)
再由定理3可知c1-ck=(b1-bk1)-(b1-bk2)=bk2-bk1■A2,
并且c1-ck=bk2-bk1=(a1-ai2)-(a1-ai1)=ai1-ai2■A1,
所以這些c1-ck必屬于A4,A5,A6這3個國家。因?yàn)檫@里有16個差數(shù),所以由定理1推知,至少有一個國家含有這16個差數(shù)中至少■+1=6個差數(shù)為號碼數(shù)的成員。并假設(shè)這6個成員的所在國家為A4,其號碼數(shù)為:d1>d2>…>d6。由于A4也為自由差集,于是同理可知這些d1-de=(e=2,3,…,6)既不屬于A4,又不屬于A1,A2,A3,所以它們必屬于A5,A6這2個國家。因?yàn)檫@里有5個差數(shù),所以根據(jù)定理1推知,這兩個國家必有一個國家含有這5個差數(shù)中至少■+1=3個差數(shù)為號碼數(shù)的成員。并假設(shè)這3個成員的所在國家為A5,其號碼數(shù)為e1>e2>e3。由于A5也為自由差集,于是同上面論證中一樣的推理,可知差數(shù)e1-e2及e1-e3既不屬于A5,又不屬于A1,A2,A3,A4。所以這兩個差必屬于A6。但由于A6也為自由差集,所以(e1-e3)-(e1-e2)=e2-e3■A6,
并且e2-e3也不屬于A1,A2,A3,A4,A5。然后,由于
0<e2-e3<e2<e1<d1<c1<b1<a1<2011,
所以e2-e3也應(yīng)當(dāng)是某一個成員的號碼數(shù),它應(yīng)當(dāng)屬于A1,A2,A3,A4,A5,A6這6個國家中的一個。這個矛盾證明了A1,A2,A3,A4,A5,A6均為自由差集的假設(shè)不成立。于是原題結(jié)論正確。
(作者單位: 南昌教育學(xué)院)
責(zé)任編輯:李 林