【正文】 物品” ，則進(jìn)入同一抽屜的人有成千上萬個(gè)，因此“生時(shí)同者必不為少矣”.既然“八字”相同， “又何貴賤貧富之不同也？這是大基數(shù)的社會(huì)現(xiàn)象，常給人感覺世事很奇巧，碰到同生日、同名的人，活中也有常見的抽屜原理的應(yīng)用之處，如“搶凳子”游戲，一群人搶凳子，凳子數(shù)比人少，必然淘汰一些人,又或者是 13 個(gè)人中總有 2 人是同一個(gè)月份出生，52 張撲克牌中取出 5 張總有 2 張花色相同，在 100 米長(zhǎng)的小路上種 101 棵小樹，不管怎么種，至少有兩棵樹苗之間的距離不超過 1 米等等. 下面我們?cè)賮砜磶讉€(gè)例子.例 11 名學(xué)生到老師家借書，老師是書房中有 A、B、C、D 四類書，每名學(xué)生最多可借兩本不同類的書，型相同.證明 若學(xué)生只借一本書，則不同的類型有 A、B、C、D 四種；若學(xué)生借兩本不同類型的書，則不同的類型有 =6 種，即 AB、AC、AD、BC、BD、 1023?C種類型. 把這 10 種類型看作 10 個(gè)“抽屜”，把 11 個(gè)學(xué)生看作 11 個(gè)“物品”.那個(gè)學(xué)生借了哪種類型的書，就將其放入對(duì)應(yīng)的那個(gè)抽屜里. 根據(jù)抽屜原理， . 所以，????????例 、排球和籃球，某班 50 名同學(xué)來倉(cāng)庫(kù)拿球，規(guī)定每個(gè)人至少拿 1 個(gè)球，至多拿 2 個(gè)球，問至少有幾名同學(xué)所拿的球種類是一致的？解首先來看具體的拿球的配組方式，有以下9種：｛足｝ ， ｛排｝ ， ｛籃｝ ， ｛足，足｝ ， ｛排，排｝ ， ｛籃，籃｝ ， ｛足，排｝ ， ｛足，籃｝ ，｛排，籃｝. 把這9種配組方式看作9個(gè)抽屜,則根據(jù)抽屜原理，有 61950???????? 所以至少有6名同學(xué)所拿的球的種類是完全一樣的.例 5 個(gè)班，每班一支球隊(duì)在同一塊場(chǎng)地上進(jìn)行單循環(huán)賽, 共要進(jìn)行 10 場(chǎng)比賽. 則各隊(duì)每?jī)蓤?chǎng)比賽中間至少隔多少場(chǎng)才最公平呢？下面是隨便安排的一個(gè)賽程: 記 5 支球隊(duì)為 A, B, C, D, E，在下表左半部分的右上三角的 10 個(gè)空格中, 隨手填上 1,2,…，10, 就得到一個(gè)賽程, 即第 1 場(chǎng) A 對(duì) B, 第 2 場(chǎng) B 對(duì) C,…, 第 10 場(chǎng) C 對(duì) E. 表的右半部分是各隊(duì)每?jī)蓤?chǎng)比賽間相隔的場(chǎng)次數(shù), 顯然這個(gè)賽程對(duì) A, E 有利, 對(duì) D 則不公平.答案是 .2????????n證明因 ，所以分兩種情況討論.?????????????時(shí)當(dāng) 時(shí)當(dāng) 12,21mnn1）當(dāng) n=2m 為偶數(shù)時(shí)，這 2m 支球隊(duì)為 0，1，2，…， （2m1）.順次安排（m+1）場(chǎng)比賽需要 2（m+1）支球隊(duì)參賽，由抽屜原理，必然有重復(fù)出現(xiàn)的球隊(duì)，由單循環(huán)賽知，場(chǎng)次數(shù)最多為 m2.2)當(dāng) n=2m+1 為奇數(shù)時(shí)，這 2m+1 支球隊(duì)為 0,1,2,…,（m+1）場(chǎng)比賽需要 2（m+1）支球隊(duì)參賽，由抽屜原理，必然有重復(fù)出現(xiàn)的球隊(duì)，其兩場(chǎng)比賽中間相隔的場(chǎng)次數(shù)最多為 m1.因此，當(dāng) n 支球隊(duì)比賽時(shí)，若安排的賽程使各隊(duì)每?jī)蓤?chǎng)比賽中間至少相隔場(chǎng)，????????n－Ramsey 定理曹汝成編著的《組合數(shù)學(xué)》教科書中指出，應(yīng)用抽屜原理雖然可以解決許多涉及存在性的組合問題,但對(duì)于一些更加復(fù)雜的有關(guān)存在性的組合問題，抽屜原理顯得無能為力，這時(shí)我們就需要運(yùn)用抽屜原理的推廣定理 Ramsey 定理來解決問題，下面我們就來探討抽屜原理在應(yīng)用上的不足.Ramsey(19031930)是英國(guó)數(shù)理邏輯學(xué)家,他把抽屜原理加以推廣，得出廣義抽屜原理，也稱為 Ramsey 定理. Ramsey 定理設(shè) p,q 是正整數(shù)，p,q2,則存在最小正整數(shù) R(p,q),使得當(dāng)nR(p,q)時(shí)，用紅藍(lán)兩色涂 的邊，則或存在一個(gè)藍(lán)色的 ,或存在一個(gè)紅色nKpK的 .pKRamsey 定理（狹義）的內(nèi)容任意六個(gè)人中要么至少三個(gè)人認(rèn)識(shí)，要么至少三個(gè)不認(rèn)識(shí). Ramsey 定理可以視為抽屜原理的推廣，1947 年，匈牙利數(shù)學(xué)家把這一原理引進(jìn)到中學(xué)生數(shù)學(xué)競(jìng)賽中，當(dāng)年匈牙利全國(guó)數(shù)學(xué)競(jìng)賽有一道這樣的試題：“證明：任何六個(gè)人中，一定可以找到三個(gè)互相認(rèn)識(shí)的人，或者三個(gè)互不認(rèn)識(shí)的人.” 在 1958 年 67 月號(hào)美國(guó)《數(shù)學(xué)月刊》同樣也登載著這樣一個(gè)有趣的問題“任何六個(gè)人的聚會(huì)，總會(huì)有 3 人互相認(rèn)識(shí)或 3 人互相不認(rèn)識(shí).”這就是著名的Ramsey 問題.這個(gè)問題乍看起來，要證明這個(gè)問題是十分簡(jiǎn)單的： 我們用 A、B、C、D、E、F 代表六個(gè)人，從中隨便找一個(gè)，例如 A 吧，把其余五個(gè)人放到“與 A 認(rèn)識(shí)”和“與 A 不認(rèn)識(shí)”兩個(gè)“抽屜”里去，根據(jù)抽屜原理，至 少有一個(gè)抽屜里有三個(gè)人 .不妨假定在“與 A 認(rèn)識(shí)”的抽屜里有三個(gè)人，他們是 B、C、 B、C、D 三人互不認(rèn)識(shí)，那么我們就找到了三個(gè)互不認(rèn)識(shí)的人； 如果 B、C、D 三人中有兩個(gè)互相認(rèn)識(shí)，例如 B 與 C 認(rèn)識(shí)，那么，A、B、C ，本題的結(jié)論都是成立的. 6 個(gè)頂點(diǎn)分別代表 6 個(gè)人，如果兩人相識(shí)，則在相應(yīng)的兩點(diǎn)間連一條紅邊，否則在相應(yīng)的兩點(diǎn)間連一藍(lán)邊.命題 6 個(gè)頂點(diǎn)的完全圖 任意進(jìn)行紅、藍(lán)兩邊著色，都存在一個(gè)紅6K色三角形或藍(lán)色三角形.證明如下首先，把這 6 個(gè)人設(shè)為 A、B、C、D、E、F A 點(diǎn)可以引出AB、AC、AD、AE、AF 五條線段.設(shè)如果兩個(gè)人認(rèn)識(shí)，則設(shè)這兩個(gè)人組成的線段為紅色；如果兩個(gè)人不認(rèn)識(shí)，則設(shè)這兩個(gè)人組成的線段為藍(lán)色. AB、AC、AD 為 BC 或 CD 為紅色，則結(jié)論顯然成立.若 BC 和 CD 均為藍(lán)色，則若 BD 為紅色，則一定有三個(gè)人相互認(rèn)識(shí)；若 BD為藍(lán)色，則一定有三個(gè)人互相不認(rèn)識(shí).上述的 Ramsey 問題等價(jià)于下面的命題 1.命題 6 個(gè)頂點(diǎn)的完全圖 任意進(jìn)行紅、藍(lán)兩邊著色，都存在一個(gè)紅6K色三角形或藍(lán)色三角形.命題 1 1 推廣成下面的命題 2.命題 任意進(jìn)行紅、藍(lán)兩邊著色，都至少有兩個(gè)6K同色三角形.由于命題 2 是要證明至少存在兩個(gè)同色三角形的問題，而抽屜原理一般只局限在證明至少存在一個(gè)或必然存在一個(gè)的問題，所以對(duì)于上述命題抽屜原理就顯得無能為力，這時(shí)需要運(yùn)用 Ramsey 定理來解決問題. 證明 設(shè) 是 的六個(gè)頂點(diǎn)，由上面的命題 1 可知，對(duì),21v6543,vK任意進(jìn)行紅、藍(lán)兩邊著色都有一個(gè)同色三角形，不妨設(shè)△ 是紅色三角6K 32v(1)若 均為藍(lán)邊，如圖 1 所示，則若 之間有一藍(lán)邊，61541,v 654,v不妨設(shè)為 ，則三角形△ 為藍(lán)色三角形；否則，△ 圖 1 圖 2(2)若 中有一條紅邊，不妨設(shè) 為紅邊，此時(shí)若邊654,v41v中有一條紅邊，不妨設(shè) 是紅邊，則△ 是一紅色三角形，見圖342,v43v32.以下就 均為藍(lán)邊的情況對(duì)與 ,v4 (ⅰ)若 中有一藍(lán)邊，不妨設(shè) 為藍(lán)邊，如圖 3，此時(shí)，若654 5v均為紅邊，則△ 是紅色三角形；否則，△ 或△ 是藍(lán)352,v532 542v543色三角形. (ⅱ)若 均為紅邊，見圖 4，此時(shí)，若 之間有一條紅邊，不645, 651,v妨設(shè) 為紅邊，則△ 為紅色三角形；否則，△ 圖 3 圖 4