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

組合數(shù)學(xué)中的抽屜原則一般分三種形式來研究，即抽屜原則的最簡形式、抽屜原則的一般形式和抽屜原則的對(duì)稱形式，本文只研究前面的兩種形式。

抽屜原則的最簡形式：把n+1個(gè)或更多物體放到n個(gè)抽屜中去，那么至少有一個(gè)抽屜里要放進(jìn)兩個(gè)或者更多的物體。下面我們來介紹抽屜原則的一般形式。它有如下定理：

定理1 如果將m個(gè)物體放到n個(gè)抽屜里去，則至少一個(gè)抽屜里含有■+1物體（其中■表示不超過■的最大整數(shù)）。

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

證明：小于m的n的最大倍數(shù)是由■減去其分?jǐn)?shù)部分所得的整數(shù)，這就是■。如果不存在有一個(gè)抽屜，它含有■+1個(gè)物體，則每個(gè)抽屜含的物體最多是■。總共有n個(gè)抽屜，所以這n個(gè)抽屜所含有的物體總數(shù)小于等于n·■≤n·■=m-1＜m。

這與已知有m個(gè)物體矛盾，所以至少有一個(gè)抽屜有■+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-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。證畢。

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

一個(gè)國際社團(tuán)的成員來自6個(gè)國家，共有成員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è)國家，今有2011個(gè)成員，所以由抽屜原則的一般形式即定理1可知，至少有一個(gè)國家，其成員至少有■+1=336人，不妨假設(shè)A1國家中至少有336人成員，并假定這336個(gè)成員的號(hào)碼數(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)都是號(hào)碼數(shù)。由于a1-ai■A1，所以必定屬于A2，A3，A4，A5，A6這5個(gè)國家中。因?yàn)檫@里共有335個(gè)差數(shù)，所以由定理1可知，至少一個(gè)國家含有這335個(gè)差數(shù)中至少■+1=67個(gè)差數(shù)為號(hào)碼數(shù)的成員。并假設(shè)這67個(gè)成員的所在國家為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è)國家。因?yàn)檫@里有66個(gè)差數(shù)，所以由定理1可知，至少有一個(gè)國家含有這66個(gè)差數(shù)中至少■+1=17個(gè)差數(shù)為號(hào)碼數(shù)的成員。并假設(shè)這17個(gè)成員的所在國家為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è)國家。因?yàn)檫@里有16個(gè)差數(shù)，所以由定理1推知，至少有一個(gè)國家含有這16個(gè)差數(shù)中至少■+1=6個(gè)差數(shù)為號(hào)碼數(shù)的成員。并假設(shè)這6個(gè)成員的所在國家為A4，其號(hào)碼數(shù)為：d1＞d2＞…＞d6。由于A4也為自由差集，于是同理可知這些d1-de=（e=2，3，…，6）既不屬于A4，又不屬于A1，A2，A3，所以它們必屬于A5，A6這2個(gè)國家。因?yàn)檫@里有5個(gè)差數(shù)，所以根據(jù)定理1推知，這兩個(gè)國家必有一個(gè)國家含有這5個(gè)差數(shù)中至少■+1=3個(gè)差數(shù)為號(hào)碼數(shù)的成員。并假設(shè)這3個(gè)成員的所在國家為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è)國家中的一個(gè)。這個(gè)矛盾證明了A1，A2，A3，A4，A5，A6均為自由差集的假設(shè)不成立。于是原題結(jié)論正確。

（作者單位: 南昌教育學(xué)院）

責(zé)任編輯：李 林