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