組合數(shù)學(xué)中的抽屜原則與自由差集

【摘要】用抽屜原則的一般形式和整數(shù)集合中的自由差集來解決一類組合理論中的一些實(shí)際問題。

【關(guān)鍵詞】抽屜原則;一般形式;自由差集

Portfolio in mathematics drawer principle of freedom of difference set

Tian Chengwei Hu Hanlin

【Abstract】The general form of the principle of using a drawer and integer set free to resolve a class of difference set in a number of portfolio theory， practical problems.

【Key words】Drawer principle; general form; free difference set

組合數(shù)學(xué)中的抽屜原則一般分三種形式來研究，即抽屜原則的最簡(jiǎn)形式，抽屜原則的一般

形式和抽屜原則的對(duì)稱形式，本文只研究前面兩途中形式。

抽屜原則的最簡(jiǎn)形式:把n+1個(gè)或更多物體放到n個(gè)抽屜中去，那么至少有一個(gè)抽屜里

要放進(jìn)兩或者更多的物體。抽屜原則又稱重迭原則，在國(guó)外人稱鴿舍原則，或叫做狹利克雷

(P.G.Dirichlet)原則。這一道理似乎并無驚人之處，其正確性可算至為明顯，當(dāng)十九世紀(jì)出現(xiàn)

在數(shù)學(xué)中卻解決了幾個(gè)很重要的問題。下面我們來介紹抽屜原則的一般形式。它有如下定理。

定理1 如果將m個(gè)物體放到n個(gè)抽屜里去，則至少一個(gè)抽屜里含有[m-1n]+1物體(其

中[m-1n]表示不超過[m-1n]的最大整數(shù))。

以后我們就把定理1稱為抽屜原則的一般形式。

證明:小于m的n的最大倍數(shù)是由m-1n減去其分?jǐn)?shù)部分所得的整數(shù)，這就是[m-1n]。如

果不存在有一個(gè)抽屜，它合有[m-1n]+1個(gè)物體，則每個(gè)抽屜含的物體最多是[m-1n]面總共

有n個(gè)抽屜，所以這n個(gè)抽屜所含的物體總數(shù)小于等于:

n#8226;[m-1n]≤n#8226;m-1n=m-1≤m。這與已知有m個(gè)物體矛盾，所以至少有一個(gè)抽屜有

[m-1n]+1個(gè)(或更多)物體。

我們?cè)賮砜醋杂刹罴?/p>

定義 設(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=(x-y)+y∈-M矛

盾，所以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)?x-y)-(x-z)=z-y∈-M證畢。

有了上面的原則，定義和定理我們來研究下面問題。

一個(gè)國(guó)際社團(tuán)的成員來自六個(gè)國(guó)家，共有成員1978人，用1，2，…，1977，1978編號(hào)，請(qǐng)證

明，該社團(tuán)至少有一個(gè)成員的順序號(hào)數(shù)，等于他的兩個(gè)同胞的順序號(hào)數(shù)之和，或等于同胞的順

序號(hào)數(shù)的2倍。

解:設(shè)A1，A ，A3，A4，A5，A6代表6個(gè)國(guó)家，今有1978個(gè)成員，所以由抽屜原則的一般形式即

定理1可知，至少有一個(gè)國(guó)家，其成員至少有[1978-16]+1=330人，不妨假設(shè)A1國(guó)家中至少

有330人成頁，并假定這330個(gè)成員的號(hào)碼數(shù)是

a1>a >a3>…>a330

現(xiàn)在，用反證法來證明。假定結(jié)論不成立，于是A1，A ，A3，A4，A5，A6都適合自由差集的定義，

即它們均為自由差集，由引理可得:

a1-ai∈-A (i=2，3，…，330)

由于0

所以這些a1-ai也應(yīng)當(dāng)都是號(hào)碼數(shù)，由于a1-ai∈-a1，所以必定屬于A ，A3，A4，A5，A6這5個(gè)國(guó)

家中，因?yàn)檫@里共有329個(gè)差數(shù)，所以由定理1可知，至少一個(gè)國(guó)家含有這329個(gè)差數(shù)中至少

[329-15]+1=66個(gè)差數(shù)為號(hào)碼的成員，并假設(shè)這66個(gè)成員的所在國(guó)家為A ，其號(hào)碼假設(shè)為:

b1>b >…>b66

由于A 也為自由差集，所以

b1-bi∈-A(j=2，3，…，66)

又由定理3

b1-bj=(a1-aj1)(a1-aj2)=aj2-aj1∈-A1

所以這里b1-bj必等于A3，A4，A5，A6這4個(gè)國(guó)家，因?yàn)檫@里有65個(gè)差數(shù)，所以由定理1可

知，至少有一個(gè)國(guó)家含有這65個(gè)差數(shù)中至少[65-14]+1=17

個(gè)差數(shù)為號(hào)碼的成員，并假設(shè)這17個(gè)成員的所在國(guó)家為A3，其號(hào)碼為

c1>c >…>c17

由于A3也為自由差集，所以

c1-ck∈-A3 ck=2，3，…，17)

再由定理3可知

c1-ck=(b1-bk1)-(b1-bk2)=bk2-bk1∈-A

并且

c1-ck=(bk2-bk1)=(a1-aix)-(a1-ai1)

=ai1-ai2∈-A1

所以這些c1-ck(k=2，3，…，17)必等于A4，A5，A6這3個(gè)國(guó)家。因?yàn)檫@里有16個(gè)差數(shù)，所以

由定理1推知，至少有一個(gè)國(guó)家含有這16個(gè)差數(shù)中至少[16-13]+1=6

個(gè)差數(shù)為號(hào)碼的成員，并假設(shè)這6個(gè)成員的所在國(guó)家為A4，其號(hào)碼為:d1>d >d3>d4>d5>d6

由于A4也為自由差集，于是同理可知這些d1-de(e=2，3，…，6)既不屬于A4，又不屬于A1，

A ，A3，所以它們必屬于A5，A6這兩個(gè)國(guó)家。國(guó)為這里有5個(gè)差數(shù)，所以根據(jù)定理1推知，這

兩個(gè)國(guó)家必有一個(gè)國(guó)家含有這5個(gè)差數(shù)中至少[5-12]+1=3個(gè)差數(shù)為號(hào)碼的成員，并假設(shè)這

3個(gè)成員的所在國(guó)家為A5，其號(hào)碼為e1>e >e3

由于A5也為自由差集，于是同上面論證中的一樣的推理，可知差數(shù)e1-e 及e1-e3

既不屬于A5，又不屬于A1，A ，A3，A4。所以這兩個(gè)差必屬于A6。但由于A6也為自由差集，所以

(e1-e3)-(e1-e )=e -e3∈-A6

并且e -e3也不屬于A1，A ，A3，A4，A5，然后，由于

0

所以e -e3也應(yīng)當(dāng)是某一個(gè)成員的號(hào)碼數(shù)，它應(yīng)當(dāng)屬于A1，…，A6這6個(gè)國(guó)家中的一個(gè)，這個(gè)

矛盾證明了A1，…，A6均不為自由有效期集的假設(shè)不成立。于是原題結(jié)論正確。

參考文獻(xiàn)

[1] 陳景潤(rùn).組合數(shù)學(xué)[M].鄭州:河南教育出版社，1983

[2] [美]S.L格雷特.美國(guó)及國(guó)際數(shù)學(xué)競(jìng)賽題解1976~1978[M].北京:科學(xué)普及出版社，1980

收稿日期:2009-12-11