1、組合數(shù)學(xué)論文競(jìng)賽數(shù)學(xué)中的組合數(shù)學(xué)問(wèn)題 競(jìng)賽數(shù)學(xué)中的組合數(shù)學(xué)問(wèn)題 組合數(shù)學(xué)是上個(gè)世紀(jì)五十年代后逐步建立和完善起來(lái)的一門數(shù)學(xué)分支，組合數(shù)學(xué)也稱為組合學(xué)、組合論，組合分析。教科書上對(duì)組合分析的定義：按某種要求把一些元素構(gòu)成有限集合的研究叫做組合分析。 這種研究比傳統(tǒng)的數(shù)學(xué)討論的對(duì)象更廣泛，在實(shí)際生活和實(shí)踐活動(dòng)中應(yīng)用性更大。這種研究一般討論以下問(wèn)題：在一定的約束條件下，對(duì)象構(gòu)成的存在性（有與沒(méi)有、能與不能）問(wèn)題；構(gòu)成的分類與計(jì)數(shù)；構(gòu)成的方法（構(gòu)造方法）及最優(yōu)化方法。 人們常把競(jìng)賽中某些問(wèn)題稱為雜題，又稱為組合數(shù)學(xué)問(wèn)題。為什么？ 中學(xué)數(shù)學(xué)競(jìng)賽中的一些問(wèn)題，很難把它們歸類為代數(shù)問(wèn)題或幾何問(wèn)題，但它們涉及到

2、的解題目標(biāo)和解題方法可以歸入組合問(wèn)題和組合分析；當(dāng)然一些組合數(shù)學(xué)的習(xí)題也直接用作競(jìng)賽題。初等數(shù)學(xué)競(jìng)賽中的組合問(wèn)題與組合分析常用的方法有抽屜原理、遞推（歸）原理、容斥原理、染色方法等，這些原理方法都很一般，重要的是經(jīng)驗(yàn)和技巧應(yīng)用的能力。本文重點(diǎn)研究競(jìng)賽數(shù)學(xué)中的組合數(shù)學(xué)計(jì)數(shù)問(wèn)題。計(jì)數(shù)問(wèn)題組合數(shù)學(xué)中的計(jì)數(shù)問(wèn)題，數(shù)學(xué)競(jìng)賽題中的熟面孔，看似司空見(jiàn)慣，不足為奇很多同學(xué)認(rèn)為只要憑借課內(nèi)知識(shí)就可左右逢源，迎刃而解其實(shí)具體解題時(shí)，時(shí)常會(huì)使你挖空心思，也無(wú)所適從。對(duì)于這類問(wèn)題往往首先要通過(guò)構(gòu)造法描繪出對(duì)象的簡(jiǎn)單數(shù)學(xué)模型，繼而借助在計(jì)數(shù)問(wèn)題中常用的一些數(shù)學(xué)原理方可得出所求對(duì)象的總數(shù)或其范圍。1、計(jì)數(shù)中求最大值： 第

3、一步：分類討論 （1）情況一，推出目標(biāo)數(shù) f m1；（2）情況二，推出目標(biāo)數(shù) f m2；（s）情況s，推出目標(biāo)數(shù) f ms；第二步：m0=maxm1，m2，ms，則f m0；第三步：構(gòu)造模型使計(jì)數(shù)恰好等于常數(shù) m0，則常數(shù) m0 即為最大值。另一種敘述:第1步：由目標(biāo)數(shù) f m推出可以符合條件； 第2步： 由f =m+1推出是不能符合條件；所以 fmax = m 。 2、計(jì)數(shù)中求最小值：第一步：分類討論（1）情況一，推出目標(biāo)數(shù) f m1；（2）情況二，推出目標(biāo)數(shù) f m2； （s）情況s，推出目標(biāo)數(shù) f ms；第二步：m0=minm1，m2，ms，則f m0；第三步：構(gòu)造模型使計(jì)數(shù)恰好等于常數(shù)

4、 m0，則常數(shù) m0 即為最小值。另一種敘述:第一步：由目標(biāo)數(shù) f m推出可以；第二步：由目標(biāo)數(shù)f =m1推出不能；所以 fmin =m 。下面我們從一道簡(jiǎn)單的組合問(wèn)題說(shuō)起：如圖，每個(gè)正方體的六個(gè)面上分別寫著數(shù)字1，2，3，4，5，6，并且任意兩個(gè)相對(duì)的面上所寫的兩個(gè)數(shù)字之和都等于7。把這樣的4個(gè)正方體一個(gè)挨著一個(gè)連接起來(lái)后，緊挨著的兩個(gè)面上的數(shù)字之和都等于8。圖中標(biāo)著 x 的那個(gè)面上所寫的數(shù)字是幾？分析： 拐角處正方體前后分別為4，3，則右側(cè)面可能是1或6，而1不能使x面的對(duì)面數(shù)字為7，故只能為6，所以x的對(duì)面數(shù)字為2，所以，x =5。著名的賽題 圖1證明：任意六個(gè)人中，總有三個(gè)人，要么相互

5、認(rèn)識(shí)，要么相互不認(rèn)識(shí)。同色分析三步：把實(shí)際問(wèn)題轉(zhuǎn)化為圖形染色；抽屜原理；二分法推理。證明：圓上六個(gè)點(diǎn)A1A2A3A4A5A6表示六個(gè)人，兩人相互認(rèn)識(shí)，相應(yīng)兩點(diǎn)間連紅線，兩人不相識(shí)，相應(yīng)兩點(diǎn)間連藍(lán)線，原命題即為證明存在三邊同色的三角形。與A1相連的5條線分別染兩種顏色，至少有三條線同色。不妨設(shè)至少有三條紅線，且為A1A2、A1A3、A1A4。若A2、A3、A4三點(diǎn)間的連線有一條紅線，則有紅色三角形；否則，三條連線都是藍(lán)線，存在藍(lán)色三角形。 圖2例1、由9位裁判給參加健美比賽的12名運(yùn)動(dòng)員評(píng)分。每位裁判對(duì)他認(rèn)為的第一名運(yùn)動(dòng)員給1分，第二名運(yùn)動(dòng)員給2分，第12名運(yùn)動(dòng)員給12分。最后評(píng)分結(jié)果顯示：每名

6、運(yùn)動(dòng)員所得的9個(gè)分?jǐn)?shù)中高低分之差都不大于3分。設(shè)各運(yùn)動(dòng)員的得分總和分別為e1，e2，e3，e12，且e1e2e3e12，求e1 的最大值。分析：含1分的格子最多有4列，此4列的每格數(shù)字平均不超過(guò)22.5，3列呢？2列？1列？解：對(duì)9個(gè)1分布的列數(shù)進(jìn)行討論：（1）1分分布在同一列，該列的和為 9，e1= 9；（2）1分恰在兩列中，列中數(shù)字不超過(guò)4，兩列的和最大為5×9=45，較小的列和45÷2，是整數(shù)，則較小的列和22， 故最小的列和e122(21)；（3）1分恰在三列中，列中數(shù)字不超過(guò)4，三列的和最大為8×9=72，同理 e124；（4）1分恰在四列中，列中數(shù)字不

7、超過(guò)4，四列的和最大為10×9=90，同理 e122； 圖3（5）1分恰在5列中，5列45個(gè)數(shù)都只能取1、2、3、4，9個(gè)裁判只能給出9個(gè)1、2、3、4，共36個(gè)，填不滿5列；同理，1分不能分布在比5更多的列中。所以，1最多能在4列中。故 e124。若前三列中，每列三個(gè)1、三個(gè)3、三個(gè)4，每列的和都是24，第四列5個(gè)2，4個(gè)5，和為30；第五列4個(gè)2，5個(gè)5，和為33；以后第k列填9個(gè)k，和為9k54。則 e1=24。所以e1 的最大值為24。例2、有兩副撲克牌，每副牌的排列順序是：第一張是大王，第二張是小王，然后是黑桃、紅桃、方塊、梅花4種花色排列，每種花色的牌又按A，2，3，J，

8、Q，K的順序排列。某人把按上述排列的兩副撲克牌上下疊在一起，然后從上到下把第一張丟掉，把第二張放在最底層，把第三張丟掉，把第四張放在最底層，如此下去，直至最后剩下一張牌。則所剩的這張牌是什么？我們先來(lái)看下下面這道題，是一個(gè)小學(xué)的競(jìng)賽題，稱為“做數(shù)學(xué)”。依順時(shí)針?lè)较驅(qū)?shù)字1，2，3，4，5，6，7寫在圓周上。首先將數(shù)字1刪除，然后每次跳過(guò)一個(gè)未刪除的數(shù)，刪除被跳到位置上的數(shù)，依此方法繼續(xù)進(jìn)行直到最后只剩下一個(gè)數(shù)為止。例如，刪除數(shù)字1，跳過(guò)數(shù)字2；刪除數(shù)字3，跳過(guò)數(shù)字4； 刪除數(shù)字5，跳過(guò)數(shù)字6； 刪除數(shù)字7，跳過(guò)數(shù)字2； 刪除數(shù)字4，跳過(guò)數(shù)字6； 刪除數(shù)字2，所以，剩下最后的一個(gè)數(shù)是6。 圖4

9、如果依順時(shí)針?lè)较驅(qū)?，2，3，2004寫在圓周上，并依照上述規(guī)則操作，試問(wèn)最后剩下的一個(gè)數(shù)為 。解：第一圈:從1開(kāi)始，刪去所有奇數(shù)，余下2k型數(shù)：2，4，6，8，2002，2004；第二圈:從2開(kāi)始，刪去所有4k-2型數(shù)，余下4k型數(shù)：4， 8，12，16，2000，2004；第三圈:從4開(kāi)始，刪去所有8k+4型數(shù)，余下8k型數(shù)： 8，16，24，1992，2000；第四圈:從16開(kāi)始，刪去所有16k型數(shù)，余下16k-8型數(shù)： 8，24，40，1976，1992；第五圈:從24開(kāi)始，刪去所有32k-8型數(shù)，余下32k-24型數(shù)： 8， 40，72，1960，1992；第六圈:從8開(kāi)始，刪去所有

10、64k-56型數(shù)，余下64k-24型數(shù)： 40，104，1896，1960；第六圈:從8開(kāi)始，刪去所有64k-56型數(shù)，余64k-24型數(shù)： 40，104，1896，1960；第七圈:從104起，刪去所有128k-24型數(shù)，余128k-88型數(shù)：40，168，296，424，552，680，808，936，1064，1192，1320，1448，1576，1704，1832，1960；第八圈:從40起，刪去所有256k-216型數(shù)，余256k-88型數(shù)：168， 424， 680， 936， 1192， 1448， 1704， 1960；第九圈:從168起,刪去所有512k-344型數(shù)，余51

11、2k-88型數(shù)：424， 936， 1448， 1960；第十圈:刪去424，1448，余下：936， 1960；最后，刪去936，余下1960 。分析：下面我們回顧剛才那道題，也來(lái)“做數(shù)學(xué)”。解：依次把牌編為1，2，3，108；第一圈:從1開(kāi)始，刪去所有奇數(shù)，余下2k型數(shù)：2，4，6，8，108；第二圈:從2開(kāi)始，刪去所有4k-2型數(shù)，余下4k型數(shù)：4，8，12，16，108；第三圈:從4開(kāi)始，刪去所有8k-4型數(shù)，余下8k型數(shù)： 8，16，24，104；第四圈:從8開(kāi)始，刪去所有16k型型數(shù)，余下16k-8數(shù)：8，24，40，56，72，88，104；第五圈:從8開(kāi)始，刪去8，40，72，

12、104，余下 24， 56，88；第六圈:刪去56，余下24，88；再刪24，最后留88。88=54+2+13×2+6，第88號(hào)牌為第二副牌中的方塊6。有沒(méi)有更好的處理方法？我們發(fā)現(xiàn)，當(dāng)牌數(shù)為4張時(shí)，最后留下的是4號(hào)牌； 當(dāng)牌數(shù)為8張時(shí)，最后留下的是8號(hào)牌； 當(dāng)牌數(shù)為2k張時(shí)，最后留下的是2k號(hào)牌；現(xiàn)在共有108張牌，取掉44張時(shí)，恰好余64張；按約定先去掉44張牌，第44張是開(kāi)始排列中的第87號(hào)牌，而第88號(hào)牌被放到余下的64張牌的最后，故最后留下的是第88號(hào)牌。請(qǐng)用此方法計(jì)算1，2，2004余下的最后的數(shù)？因?yàn)?0041024=980，所以第980個(gè)被去掉的數(shù)是第一輪中的1959

13、(980×21) ，第981個(gè)被去掉的數(shù)是1961，從這兒按規(guī)則數(shù)最后的數(shù)是前面的1960。從1，2，3，2004中任選k個(gè)數(shù)，使得所選的k個(gè)數(shù)中，一定可以找到能構(gòu)成三角形邊長(zhǎng)的3個(gè)數(shù)(這里要求三角形三個(gè)邊長(zhǎng)互不相等)。試問(wèn)：滿足條件的k的最小值?？紤]等價(jià)命題：1，2，3，2004中存在k1個(gè)數(shù)，其中任意3個(gè)數(shù)均不能構(gòu)成一個(gè)三角形的3條邊長(zhǎng) (這里要求三角形三個(gè)邊長(zhǎng)互不相等)。求滿足此條件的k的最大值。 分析：從小的數(shù)開(kāi)始，找盡量多的數(shù)，使之不能構(gòu)成三角形兩小邊之和不大于第3邊：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597， 16

14、個(gè)數(shù)！再增加數(shù)一定會(huì)有兩小邊之和大于第3邊了，所求的k的最大值為17。怎樣表達(dá)？ 解：按條件an-2+ an-1an2004構(gòu)造遞增的正整數(shù)數(shù)列an ，并使得an值最小n最大：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，共16個(gè)數(shù)！其中任意3個(gè)數(shù) ai、aj、ak (ijk )，總有 ai+ ajak-2+ ak-1ak ，兩小數(shù)之和大于第3數(shù)，不能成為三角形的3條邊。 對(duì)于任意的、項(xiàng)數(shù)不少于17且每項(xiàng)值不超過(guò)2004的、遞增的正整數(shù)數(shù)列bn ，若存在bi、bj、bk (ijk 17)滿足bi+ bjbk，則此3個(gè)數(shù)可以成為三角形的3邊邊

15、長(zhǎng)；否則，bkak (k17)， b15+ b16 a15+ a162004 b17，b15，b16，b17可以成為三角形的3邊邊長(zhǎng) 。即所求的k的最小值為17。 例3、在2×3的矩形方格紙上，各個(gè)小正方形的頂點(diǎn)稱為格點(diǎn)。以格點(diǎn)為頂點(diǎn)的等腰直角三角形有（ ）個(gè)A24 B38 C46 D50解： （1）直角邊為1的三角形有4×6=24個(gè)；（2）直角邊為2的三角形有4×2=8個(gè)；（3）直角邊為的三角形有4×2+6=14個(gè)； 圖5（4）直角邊為的三角形有4個(gè)；1、運(yùn)用分類計(jì)數(shù)原理與分步計(jì)數(shù)原理分類計(jì)數(shù)原理與分步計(jì)數(shù)原理（即加法原理與乘法原理）是關(guān)于計(jì)數(shù)的兩個(gè)基

16、本原理，是解決競(jìng)賽中計(jì)數(shù)問(wèn)題的基礎(chǔ)。下面提出的三個(gè)問(wèn)題，注意結(jié)合排列與組合的相關(guān)知識(shí)，構(gòu)造出相應(yīng)的模型再去分析就可順利求解。例4、已知兩個(gè)實(shí)數(shù)集合與，若從A到B的映射f使得B中每個(gè)元素都有原象，且，則這樣的映射共有（ ）個(gè)。（A）、 （B）、 （C）、 （D）解：設(shè)按從小到大排列為（因集合元素具有互異性，故其中不含相等情形）。將A中元素分成50組，每組依次與B中元素對(duì)應(yīng)這里，我們用，表示，考慮，容易得到，這就是說(shuō)只能寫在的右邊，故只需在之間的99個(gè)空位“”中選擇49個(gè)位置并按從左到右的順序依次填上。從而構(gòu)成滿足題設(shè)要求的映射共有個(gè)。因此選D。例5、有人要上樓，此人每步能向上走1階或2階，如果一

17、層樓有18階，他上一層樓有多少種不同的走法？解法1：此人上樓最多走18步，最少走9步。這里用分別表示此人上樓走18步，17步，16步，9步時(shí)走法（對(duì)于任意前后兩者的步數(shù)，因后者少走2步1階，而多走1步2階，計(jì)后者少走1步）的計(jì)數(shù)結(jié)果?？紤]步子中的每步2階情形，易得，。綜上，他上一層樓共有種不同的走法。解法2：設(shè)表示上n階的走法的計(jì)數(shù)結(jié)果。顯然，（2步1階；1步2階）。對(duì)于起步只有兩種不同走法：上1階或上2階。因此對(duì)于，第1步上1階的情形，還剩階，計(jì)種不同的走法；對(duì)于第1步上2階的情形，還剩階，計(jì)種不同的走法?？傆?jì)。同理：，。例6、在世界杯足球賽前，F(xiàn)國(guó)教練為了考察這七名隊(duì)員，準(zhǔn)備讓他們?cè)谌龍?chǎng)訓(xùn)

18、練比賽（每場(chǎng)90分鐘）都上場(chǎng)。假設(shè)在比賽的任何時(shí)刻，這些隊(duì)員中有且僅有一人在場(chǎng)上，并且每人上場(chǎng)的總時(shí)間（以分鐘為單位）均被7整除，每人上場(chǎng)的總時(shí)間（以分鐘為單位）均被13整除。如果每場(chǎng)換人次數(shù)不限，那么按每名隊(duì)員上場(chǎng)的總時(shí)間計(jì)算，共有多少種不同的情況。解：設(shè)上場(chǎng)的總時(shí)間分別為分鐘。根據(jù)題意，可設(shè)，其中。令，其中，且。則。易得其一個(gè)整數(shù)特解為，又因，故其整數(shù)通解為。再由，得，故整數(shù)。從而其滿足條件的所有整數(shù)解為。對(duì)于的正整數(shù)解，可以寫一橫排共計(jì)33個(gè)1，在每相鄰兩個(gè)1之間共32個(gè)空位中任選3個(gè)填入“+”號(hào)，再把3個(gè)“+”號(hào)分隔開(kāi)的4個(gè)部分里的1分別統(tǒng)計(jì)，就可得到其一個(gè)正整數(shù)解，故有個(gè)正整數(shù)解；同

19、理有個(gè)正整數(shù)解；從而此時(shí)滿足條件的正整數(shù)解有個(gè)。因此滿足條件的所有正整數(shù)解有個(gè)，即按每名隊(duì)員上場(chǎng)的總時(shí)間計(jì)算，共有42244種不同的情況。2、運(yùn)用容斥原理容斥原理，又稱包含排斥原理或逐步淘汰原理。顧名思義，即先計(jì)算一個(gè)較大集合的元素的個(gè)數(shù)，再把多計(jì)算的那一部分去掉。它由英國(guó)數(shù)學(xué)家J.J.西爾維斯特首先創(chuàng)立。這個(gè)原理有多種表達(dá)形式，其中最基本的形式為：設(shè)是任意n個(gè)有限集合，則例7、由數(shù)字1，2，3組成n位數(shù)，且在這個(gè)n位數(shù)中，1，2，3的每一個(gè)至少出現(xiàn)一次，問(wèn)這樣的n位數(shù)有多少個(gè)？解：設(shè)U是由1，2，3組成的n位數(shù)的集合，是U中不含數(shù)字1的n位數(shù)的集合，是U中不含數(shù)字2的n位數(shù)的集合，是U中不含

20、數(shù)字3的n位數(shù)的集合，則；。因此。即符合題意的n位數(shù)的個(gè)數(shù)為。下面，我們?cè)賮?lái)看一個(gè)關(guān)于容斥原理應(yīng)用的變異問(wèn)題。例8、參加大型團(tuán)體表演的學(xué)生共240名，他們面對(duì)教練站成一行，自左至右按1，2，3，4，5，依次報(bào)數(shù)。教練要求全體學(xué)生牢記各自所報(bào)的數(shù)，并做下列動(dòng)作：先讓報(bào)的數(shù)是3的倍數(shù)的全體同學(xué)向后轉(zhuǎn)；接著讓報(bào)的數(shù)是5的倍數(shù)的全體同學(xué)向后轉(zhuǎn)；最后讓報(bào)的數(shù)是7的倍數(shù)的全體同學(xué)向后轉(zhuǎn)。問(wèn)：此時(shí)還有多少名同學(xué)面對(duì)教練？面對(duì)教練的同學(xué)中，自左至右第66位同學(xué)所報(bào)的數(shù)是幾？解：1 設(shè)，表示由U中所有i的倍數(shù)組成的集合。則；，；，；。從而此時(shí)有名同學(xué)面對(duì)教練。如果我們借助維恩圖進(jìn)行分析，利用上面所得數(shù)據(jù)分別填入

21、圖6，注意按從內(nèi)到外的順序填。如圖1，此時(shí)面對(duì)教練的同學(xué)一目了然，應(yīng)有109+14+4+9=136名。用上面類似的方法可算得自左至右第1號(hào)至第105號(hào)同學(xué)中面對(duì)教練的有60名?？紤]所報(bào)的數(shù)不是3，5，7的倍數(shù)的同學(xué)沒(méi)有轉(zhuǎn)動(dòng)，他們面對(duì)教練；所報(bào)的數(shù)是3，5，7中的兩個(gè)數(shù)的倍數(shù)的同學(xué)經(jīng)過(guò)兩次轉(zhuǎn)動(dòng)，他們?nèi)悦鎸?duì)教練；其余同學(xué)轉(zhuǎn)動(dòng)了一次或三次，都背對(duì)教練。從106開(kāi)始，考慮是3、5、7的倍數(shù)：3的倍數(shù)（由105依次加3）：108，111，114，117，120，5的倍數(shù)（由105依次加5）：110，115，120，7的倍數(shù)（由105依次加7）：112，119，因此，從106號(hào)開(kāi)始，自左至右，面對(duì)教練的同

22、學(xué)所報(bào)的數(shù)依次是：106，107，109，113，116，118，120，由此可知面對(duì)教練的第66位同學(xué)所報(bào)的數(shù)是118。三、抽屜原則10個(gè)蘋果放入9個(gè)抽屜中，無(wú)論怎么放，一定有一個(gè)抽屜里放了2個(gè)或更多個(gè)蘋果。這個(gè)簡(jiǎn)單的事實(shí)就是抽屜原則。由德國(guó)數(shù)學(xué)家狄利克雷首先提出來(lái)的。因此，又稱為狄利克雷原則。將蘋果換成信、鴿子或鞋，把抽屜換成信筒、鴿籠或鞋盒，這個(gè)原則又叫做信筒原則、鴿籠原則或鞋盒原則。抽屜原則是離散數(shù)學(xué)中的一個(gè)重要原則，把它推廣到一般情形就得到下面幾種形式：原則一：把m個(gè)元素分成n類（m > n），不論怎么分，至少有一類中有兩個(gè)元素。原則二：把m個(gè)元素分成n類（m>n）（1）

23、當(dāng)n|m時(shí)，至少有一類中含有至少個(gè)元素；（2）當(dāng)n|m時(shí)，至少有一類中含有至少+1個(gè)元素。其中n m表示n是m的約數(shù)，n m表示n不是m的約數(shù)，表示不超過(guò)的最大整數(shù)。原則三：把個(gè)元素分成n類，則存在一個(gè)k，使得第k類至少有個(gè)元素。原則四：把無(wú)窮多個(gè)元素分成有限類，則至少有一類包含無(wú)窮多個(gè)元素。以上這些命題用反證法極易得到證明，這里從略。一般來(lái)說(shuō)，適合應(yīng)用抽屜原則解決的數(shù)學(xué)問(wèn)題具有如下特征：新給的元素具有任意性。如10個(gè)蘋果放入9個(gè)抽屜，可以隨意地一個(gè)抽屜放幾個(gè)，也可以讓抽屜空著。問(wèn)題的結(jié)論是存在性命題，題目中常含有“至少有”、“一定有”、“不少于”、“存在”、“必然有”等詞語(yǔ)，其結(jié)論只要存在，

24、不必確定，即不需要知道第幾個(gè)抽屜放多少個(gè)蘋果。對(duì)一個(gè)具體的可以應(yīng)用抽屜原則解決的數(shù)學(xué)問(wèn)題還應(yīng)搞清三個(gè)問(wèn)題：（1）什么是“蘋果”？（2）什么是“抽屜”？（3）蘋果、抽屜各多少？用抽屜原則解題的本質(zhì)是把所要討論的問(wèn)題利用抽屜原則縮小范圍，使之在一個(gè)特定的小范圍內(nèi)考慮問(wèn)題，從而使問(wèn)題變得簡(jiǎn)單明確。用抽屜原則解題的基本思想是根據(jù)問(wèn)題的自身特點(diǎn)和本質(zhì)，弄清對(duì)哪些元素進(jìn)行分類，找出分類的規(guī)律。用抽屜原則解題的基本思想是根據(jù)問(wèn)題的自身特點(diǎn)和本質(zhì)，弄清對(duì)哪些元素進(jìn)行分類，找出分類的規(guī)律。用抽屜原則解題的關(guān)鍵是利用題目中的條件構(gòu)造出與題設(shè)相關(guān)的“抽屜”。例9、在1，4，7，10，13，100中任選出20個(gè)數(shù)，其

25、中至少有不同的兩組數(shù)，其和都等于104，試證明之。 （第39屆美國(guó)普特南數(shù)學(xué)競(jìng)賽題）證明：給定的數(shù)共有34個(gè)，其相鄰兩數(shù)的差均為3，我們把這些數(shù)分成如下18個(gè)不相交的集合：1，52，4，100，7，97，49，55。且把它們分作是18個(gè)抽屜，從已知的34個(gè)數(shù)中任取20個(gè)數(shù)，即把前面兩個(gè)抽屜中的數(shù)1和52都取出，則剩下的18個(gè)數(shù)在后面的16個(gè)抽屜中至少有不同的兩個(gè)抽屜中的數(shù)全被取出，這兩個(gè)抽屜中的數(shù)互不相同，每個(gè)抽屜中的兩個(gè)數(shù)的和都是104。評(píng)述：此例是根據(jù)某兩個(gè)數(shù)的和為104來(lái)構(gòu)造抽屜。一般地，與整數(shù)集有關(guān)的存在性問(wèn)題也可根據(jù)不同的需要利用整數(shù)間的倍數(shù)關(guān)系、同余關(guān)系來(lái)適當(dāng)分組而構(gòu)成抽屜。例10

26、、設(shè)ABC為一等邊三角形，E是三邊上點(diǎn)的全體. 對(duì)于每一個(gè)把E分成兩個(gè)不相交子集的劃分，問(wèn)這兩個(gè)子集中是否至少有一個(gè)子集包含著一個(gè)直角三角形的三個(gè)頂點(diǎn)？（第24屆IMO第4題）證明：如圖 7，在邊BC、CA、AB上分別取三點(diǎn)P、Q、R，使顯然ARQ，BPR，CQP都是直角三角形. 它們的銳角是30°及60°。設(shè)E1，E2是E的兩個(gè)非空子集，且由抽屜原則P、Q、R中至少有兩點(diǎn)屬于同一子集，不妨設(shè)P、QE1。如果BC邊上除P之外還有屬于E1的點(diǎn)，那么結(jié)論已明。設(shè)BC的點(diǎn)除P之外全屬于E2，那么只要AB上有異于B的點(diǎn)S屬于E2，設(shè)S在BC上的投影點(diǎn)為，則SSB為直角三角形。再設(shè)A

27、B內(nèi)的每一點(diǎn)均不屬于E2，即除B之外全屬于E1，特別，R、AE1，于是A、Q、RE1，且AQR為一直角三角形。從而命題得證。評(píng)述：此例通過(guò)分割圖形構(gòu)造抽屜。在一個(gè)幾何圖形內(nèi)有若干已知點(diǎn)，我們可以根據(jù)問(wèn)題的要求把圖形進(jìn)行適當(dāng)?shù)姆指睿眠@些分割成的圖形作為抽屜，再對(duì)已知點(diǎn)進(jìn)行分類，集中對(duì)某一個(gè)或幾個(gè)抽屜進(jìn)行討論，使問(wèn)題得到解決。4、割補(bǔ)法的應(yīng)用計(jì)算幾何中的割補(bǔ)法在組合數(shù)學(xué)中即表現(xiàn)為計(jì)數(shù)上的“割補(bǔ)”：欲求解一定范圍內(nèi)滿足條件的元素個(gè)數(shù)，不妨擴(kuò)大限定范圍求解，例如減法原理；抑或在統(tǒng)計(jì)中分別求解，再將多余部分刪去，例如容斥原理?？傊艘徊胶ｉ熖炜?，先放寬條件，再解決問(wèn)題就方便多了。（1）減法原理這只是

28、一個(gè)簡(jiǎn)單的數(shù)學(xué)問(wèn)題而已，可以看成是加法原理和乘法原理的一個(gè)引申：假設(shè)A地到B，C，D地分別有5條路，但到E地只有3條路，B，C，D，E地與F都有3條路相通，于是不妨假設(shè)AE也有5條路相通，于是AF道路總數(shù)為5×4×3=60條，其中有2×3=6條是我們“杜撰”出來(lái)的，于是實(shí)際上AF道路總數(shù)應(yīng)為606=54條。（2）有禁區(qū)的排列問(wèn)題我們先介紹有關(guān)棋盤多項(xiàng)式的概念。設(shè)C是一個(gè)棋盤，Rk(C)表示把k個(gè)相同的棋子布到C中的方案數(shù)。在布棋時(shí)我們規(guī)定：當(dāng)一個(gè)棋子放到C中的某個(gè)格以后，這個(gè)格所在的行和列就不能再放其他棋子了，并規(guī)定對(duì)任意的棋盤C有R0(C)=1。不難得到以下的結(jié)

29、果：R1( )=1，R1()=R1（）=2，R2()=R2（）=0，R2()=1，可以證明布棋方案數(shù)Rk（C）具有下面的性質(zhì)：對(duì)于任意的棋盤C和正整數(shù)k，如果k大于C中的方格總數(shù)，則R（C）=0。R1（C）等于C中的方格數(shù)。設(shè)C1和C2是兩個(gè)棋盤，如果C1經(jīng)過(guò)旋轉(zhuǎn)或者翻轉(zhuǎn)變成了C2，則Rk(C1)= Rk(C2)。設(shè)Ci是從棋盤C中去掉指定的方格所在的行和列以后剩余的棋盤，Cl是從棋盤C中去掉指定的方格以后剩余的棋盤，則有Rk(C)= Rk-1(Ci)+ Rk(Cl) (k>=1)。設(shè)棋盤C由兩個(gè)子棋盤C1和C2組成，如果C1和C2的布棋方案是互相獨(dú)立的，則有。定義1：設(shè)C是棋盤，則叫做

30、棋盤多項(xiàng)式。顯然，在上述定義中當(dāng)k大于棋盤的格子數(shù)時(shí)Rk（C）=0，所以R（C）一般只有有限項(xiàng)。例如：R（）=R0（）+R1（）x+ R 2（）X2=1+2X+X2根據(jù)Rk（C）的性質(zhì)不難得到R（C）的性質(zhì)。R（C）=xR(Ci)+R(Cl)，其中Ci和Cl的定義如前所述。R（C）=R(Ci)×R(Cl) ，其中Ci和Cl的定義如前所述。利用這兩條性質(zhì)可以計(jì)算棋盤多項(xiàng)式。例11、 計(jì)算R（）。解：R（）=X*R（）+R（）=X（1+X）+（1+2X）=1+3X+X2 。下面我們就可以利用棋盤多項(xiàng)式來(lái)解決有禁區(qū)的排列問(wèn)題。首先可以看到X=1，2，3，n的一個(gè)排列恰好對(duì)應(yīng)了n個(gè)棋子在棋盤上的一種排布。在圖8中，我們以棋盤的n行表示X中的元素，列表示位置，則這種放置方案就對(duì)應(yīng)了排列2143。如果在排列中限制元素i不能放在第j個(gè)位置，則相應(yīng)的布棋方案中的棋盤第行第j列就不能放置棋子。我們把所有這些不許放置棋的方格稱作禁區(qū)。定理1 設(shè)C是的具有給定禁區(qū)的棋盤，這個(gè)禁區(qū) 圖 8對(duì)應(yīng)集合1，2，n中的元素在排列中不允許出現(xiàn)的位置。則這種有禁區(qū)的排列數(shù)