競賽數(shù)學(xué)中的組合數(shù)學(xué)問題

PAGE第1頁計(jì)數(shù)問題1、計(jì)數(shù)中求最大值：第一步：分類討論（1）情況一，推出目標(biāo)數(shù)f≤m1；（2）情況二，推出目標(biāo)數(shù)f≤m2；…（s）情況s，推出目標(biāo)數(shù)f≤ms；第二步：m0=max{m1，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=min{m1，m2，…，ms}，則f≥m0；第三步：構(gòu)造模型使計(jì)數(shù)恰好等于常數(shù)m0，則常數(shù)m0即為最小值。另一種敘述:第一步：由目標(biāo)數(shù)f≥m推出可以；第二步：由目標(biāo)數(shù)f=m－1推出不能；所以fmin=m。例1、由9位裁判給參加比賽的12名運(yùn)動員評分。每位裁判對他認(rèn)為的第一名運(yùn)動員給1分，第二名運(yùn)動員給2分，…，第12名運(yùn)動員給12分。最后評分結(jié)果顯示：每名運(yùn)動員所得的9個(gè)分?jǐn)?shù)中高低分之差都不大于3分。設(shè)各運(yùn)動員的得分總和分別為e1，e2，e3，…，e12，且e1≤e2≤e3≤…≤e12，求e1的最大值。分析：含1分的格子最多有4列，此4列的每格數(shù)字平均不超過22.5，3列呢？2列？1列？解：對9個(gè)1分布的列數(shù)進(jìn)行討論：（1）1分分布在同一列，該列的和為9，e1=9；（2）1分恰在兩列中，列中數(shù)字不超過4，兩列的和最大為5×9=45，較小的列和≤45÷2，是整數(shù)，則較小的列和≤22，故最小的列和e1≤22(21)；（3）1分恰在三列中，列中數(shù)字不超過4，三列的和最大為8×9=72，同理e1≤24；（4）1分恰在四列中，列中數(shù)字不超過4，四列的和最大為10×9=90，同理e1≤22；（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列中。故e1≤24。若前三列中，每列三個(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，和為9k≥54。則e1=24。所以e1的最大值為24。例2、有兩副撲克牌，每副牌的排列順序是：第一張是大王，第二張是小王，然后是黑桃、紅桃、方塊、梅花4種花色排列，每種花色的牌又按A，2，3，…，J，Q，K的順序排列。某人把按上述排列的兩副撲克牌上下疊在一起，然后從上到下把第一張丟掉，把第二張放在最底層，把第三張丟掉，把第四張放在最底層……，如此下去，直至最后剩下一張牌。則所剩的這張牌是什么？我們先來看下面這道題，是一個(gè)小學(xué)的競賽題，稱為“做數(shù)學(xué)”。依順時(shí)針方向?qū)?shù)字1，2，3，4，5，6，7寫在圓周上。首先將數(shù)字1刪除，然后每次跳過一個(gè)未刪除的數(shù)，刪除被跳到位置上的數(shù)，依此方法繼續(xù)進(jìn)行直到最后只剩下一個(gè)數(shù)為止。例如，刪除數(shù)字1，跳過數(shù)字2；刪除數(shù)字3，跳過數(shù)字4；刪除數(shù)字5，跳過數(shù)字6；刪除數(shù)字7，跳過數(shù)字2；刪除數(shù)字4，跳過數(shù)字6；刪除數(shù)字2，所以，剩下最后的一個(gè)數(shù)是6。圖4如果依順時(shí)針方向?qū)?，2，3，…，2004寫在圓周上，并依照上述規(guī)則操作，試問最后剩下的一個(gè)數(shù)為。解：第一圈:從1開始，刪去所有奇數(shù)，余下2k型數(shù)：2，4，6，8，…，2002，2004；第二圈:從2開始，刪去所有4k-2型數(shù)，余下4k型數(shù)：4，8，12，16，…，2000，2004；第三圈:從4開始，刪去所有8k+4型數(shù)，余下8k型數(shù)：8，16，24，…，1992，2000；第四圈:從16開始，刪去所有16k型數(shù)，余下16k-8型數(shù)：8，24，40，…，1976，1992；第五圈:從24開始，刪去所有32k-8型數(shù)，余下32k-24型數(shù)：8，40，72…，1960，1992；第六圈:從8開始，刪去所有64k-56型數(shù)，余下64k-24型數(shù)：40，104，…，1896，1960；第六圈:從8開始，刪去所有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ù)，余512k-88型數(shù)：424，936，1448，1960；第十圈:刪去424，1448，余下：936，1960；最后，刪去936，余下1960。分析：下面我們回顧剛才那道題，也來“做數(shù)學(xué)”。解：依次把牌編為1，2，3，…，108；第一圈:從1開始，刪去所有奇數(shù)，余下2k型數(shù)：2，4，6，8，…，108；第二圈:從2開始，刪去所有4k-2型數(shù)，余下4k型數(shù)：4，8，12，16，…，108；第三圈:從4開始，刪去所有8k-4型數(shù)，余下8k型數(shù)：8，16，24，…，104；第四圈:從8開始，刪去所有16k型型數(shù)，余下16k-8數(shù)：8，24，40，56，72，88，104；第五圈:從8開始，刪去8，40，72，104，余下24，56，88；第六圈:刪去56，余下24，88；再刪24，最后留88。88=54+2+13×2+6，第88號牌為第二副牌中的方塊6。有沒有更好的處理方法？我們發(fā)現(xiàn)，當(dāng)牌數(shù)為4張時(shí)，最后留下的是4號牌；當(dāng)牌數(shù)為8張時(shí)，最后留下的是8號牌；當(dāng)牌數(shù)為2k張時(shí)，最后留下的是2k號牌；現(xiàn)在共有108張牌，取掉44張時(shí)，恰好余64張；按約定先去掉44張牌，第44張是開始排列中的第87號牌，而第88號牌被放到余下的64張牌的最后，故最后留下的是第88號牌。請用此方法計(jì)算1，2，…，2004余下的最后的數(shù)？因?yàn)?004－1024=980，所以第980個(gè)被去掉的數(shù)是第一輪中的1959(980×2－1)，第981個(gè)被去掉的數(shù)是1961，從這兒按規(guī)則數(shù)最后的數(shù)是前面的1960。從1，2，3，…，2004中任選k個(gè)數(shù)，使得所選的k個(gè)數(shù)中，一定可以找到能構(gòu)成三角形邊長的3個(gè)數(shù)(這里要求三角形三個(gè)邊長互不相等)。試問：滿足條件的k的最小值?？紤]等價(jià)命題：1，2，3，…，2004中存在k－1個(gè)數(shù)，其中任意3個(gè)數(shù)均不能構(gòu)成一個(gè)三角形的3條邊長(這里要求三角形三個(gè)邊長互不相等)。求滿足此條件的k的最大值。分析：從小的數(shù)開始，找盡量多的數(shù)，使之不能構(gòu)成三角形——兩小邊之和不大于第3邊：1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，16個(gè)數(shù)！再增加數(shù)一定會有兩小邊之和大于第3邊了，所求的k的最大值為17?！鯓颖磉_(dá)？解：按條件an-2+an-1≤an≤2004構(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(i＜j＜k)，總有ai+aj≤ak-2+ak-1≤ak，兩小數(shù)之和大于第3數(shù)，不能成為三角形的3條邊。對于任意的、項(xiàng)數(shù)不少于17且每項(xiàng)值不超過2004的、遞增的正整數(shù)數(shù)列{bn}，若存在bi、bj、bk(i＜j＜k＜17)滿足bi+bj＞bk，則此3個(gè)數(shù)可以成為三角形的3邊邊長；否則，bk≥ak(k＜17)，b15+b16≥a15+a16＞2004≥b17，b15，b16，b17可以成為三角形的3邊邊長。即所求的k的最小值為17。例3、在2×3的矩形方格紙上，各個(gè)小正方形的頂點(diǎn)稱為格點(diǎn)。以格點(diǎn)為頂點(diǎn)的等腰直角三角形有（）個(gè)A．24B．38C．46D．解：（1）直角邊為1的三角形有4×6=24個(gè)；（2）直角邊為2的三角形有4×2=8個(gè)；（3）直角邊為的三角形有4×2+6=14個(gè)；圖5（4）直角邊為的三角形有4個(gè)；運(yùn)用分類計(jì)數(shù)原理與分步計(jì)數(shù)原理分類計(jì)數(shù)原理與分步計(jì)數(shù)原理（即加法原理與乘法原理）是關(guān)于計(jì)數(shù)的兩個(gè)基本原理，是解決競賽中計(jì)數(shù)問題的基礎(chǔ)。例4、已知兩個(gè)實(shí)數(shù)集合與，若從A到B的映射f使得B中每個(gè)元素都有原象，且，則這樣的映射共有（）個(gè)。（A）、（B）、（C）、（D）解：設(shè)按從小到大排列為（因集合元素具有互異性，故其中不含相等情形）。將A中元素分成50組，每組依次與B中元素對應(yīng)．這里，我們用，表示，，…考慮，容易得到，這就是說只能寫在的右邊，故只需在之間的99個(gè)空位“”中選擇49個(gè)位置并按從左到右的順序依次填上。從而構(gòu)成滿足題設(shè)要求的映射共有個(gè)。因此選D。例5、有人要上樓，此人每步能向上走1階或2階，如果一層樓有18階，他上一層樓有多少種不同的走法？解法1：此人上樓最多走18步，最少走9步。這里用分別表示此人上樓走18步，17步，16步，…，9步時(shí)走法（對于任意前后兩者的步數(shù)，因后者少走2步1階，而多走1步2階，計(jì)后者少走1步）的計(jì)數(shù)結(jié)果?？紤]步子中的每步2階情形，易得，，，…，。綜上，他上一層樓共有種不同的走法。解法2：設(shè)表示上n階的走法的計(jì)數(shù)結(jié)果。顯然，，（2步1階；1步2階）。對于起步只有兩種不同走法：上1階或上2階。因此對于，第1步上1階的情形，還剩階，計(jì)種不同的走法；對于第1步上2階的情形，還剩階，計(jì)種不同的走法?？傆?jì)。同理：，，…，。例6、在世界杯足球賽前，F(xiàn)國教練為了考察這七名隊(duì)員，準(zhǔn)備讓他們在三場訓(xùn)練比賽（每場90分鐘）都上場。假設(shè)在比賽的任何時(shí)刻，這些隊(duì)員中有且僅有一人在場上，并且每人上場的總時(shí)間（以分鐘為單位）均被7整除，每人上場的總時(shí)間（以分鐘為單位）均被13整除。如果每場換人次數(shù)不限，那么按每名隊(duì)員上場的總時(shí)間計(jì)算，共有多少種不同的情況。解：設(shè)上場的總時(shí)間分別為分鐘。根據(jù)題意，可設(shè)，，其中。令，，其中，，且。則。易得其一個(gè)整數(shù)特解為，又因，故其整數(shù)通解為。再由，得，故整數(shù)。從而其滿足條件的所有整數(shù)解為。對于的正整數(shù)解，可以寫一橫排共計(jì)33個(gè)1，在每相鄰兩個(gè)1之間共32個(gè)空位中任選3個(gè)填入“+”號，再把3個(gè)“+”號分隔開的4個(gè)部分里的1分別統(tǒng)計(jì)，就可得到其一個(gè)正整數(shù)解，故有個(gè)正整數(shù)解；同理有個(gè)正整數(shù)解；從而此時(shí)滿足條件的正整數(shù)解有個(gè)。因此滿足條件的所有正整數(shù)解有個(gè)，即按每名隊(duì)員上場的總時(shí)間計(jì)算，共有42244種不同的情況。2、運(yùn)用容斥原理容斥原理，又稱包含排斥原理或逐步淘汰原理。顧名思義，即先計(jì)算一個(gè)較大集合的元素的個(gè)數(shù)，再把多計(jì)算的那一部分去掉。它由英國數(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)一次，問這樣的n位數(shù)有多少個(gè)？解：設(shè)U是由1，2，3組成的n位數(shù)的集合，是U中不含數(shù)字1的n位數(shù)的集合，是U中不含數(shù)字2的n位數(shù)的集合，是U中不含數(shù)字3的n位數(shù)的集合，則；；；。因此。即符合題意的n位數(shù)的個(gè)數(shù)為。下面，我們再來看一個(gè)關(guān)于容斥原理應(yīng)用的變異問題。例8、參加大型團(tuán)體表演的學(xué)生共240名，他們面對教練站成一行，自左至右按1，2，3，4，5，…依次報(bào)數(shù)。教練要求全體學(xué)生牢記各自所報(bào)的數(shù)，并做下列動作：先讓報(bào)的數(shù)是3的倍數(shù)的全體同學(xué)向后轉(zhuǎn)；接著讓報(bào)的數(shù)是5的倍數(shù)的全體同學(xué)向后轉(zhuǎn)；最后讓報(bào)的數(shù)是7的倍數(shù)的全體同學(xué)向后轉(zhuǎn)。問：（1）此時(shí)還有多少名同學(xué)面對教練？（2）面對教練的同學(xué)中，自左至右第66位同學(xué)所報(bào)的數(shù)是幾？解：設(shè)，表示由U中所有i的倍數(shù)組成的集合。則；，，；，，；。從而此時(shí)有名同學(xué)面對教練。如果我們借助維恩圖進(jìn)行分析，利用上面所得數(shù)據(jù)分別填入圖6，注意按從內(nèi)到外的順序填。如圖1，此時(shí)面對教練的同學(xué)一目了然，應(yīng)有109+14+4+9=136名。⑵用上面類似的方法可算得自左至右第1號至第105號同學(xué)中面對教練的有60名?？紤]所報(bào)的數(shù)不是3，5，7的倍數(shù)的同學(xué)沒有轉(zhuǎn)動，他們面對教練；所報(bào)的數(shù)是3，5，7中的兩個(gè)數(shù)的倍數(shù)的同學(xué)經(jīng)過兩次轉(zhuǎn)動，他們?nèi)悦鎸叹殻黄溆嗤瑢W(xué)轉(zhuǎn)動了一次或三次，都背對教練。從106開始，考慮是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號開始，自左至右，面對教練的同學(xué)所報(bào)的數(shù)依次是：106，107，109，113，116，118，120，…由此可知面對教練的第66位同學(xué)所報(bào)的數(shù)是118。例9、在1，4，7，10，13，…，100中任選出20個(gè)數(shù)，其中至少有不同的兩組數(shù)，其和都等于104，試證明之。（第39屆美國普特南數(shù)學(xué)競賽題）證明：給定的數(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。評述：此例是根據(jù)某兩個(gè)數(shù)的和為104來構(gòu)造抽屜。一般地，與整數(shù)集有關(guān)的存在性問題也可根據(jù)不同的需要利用整數(shù)間的倍數(shù)關(guān)系、同余關(guān)系來適當(dāng)分組而構(gòu)成抽屜。例10、設(shè)ABC為一等邊三角形，E是三邊上點(diǎn)的全體.對于每一個(gè)把E分成兩個(gè)不相交子集的劃分，問這兩個(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、Q∈E1。如果BC邊上除P之外還有屬于E1的點(diǎn)，那么結(jié)論已明。 設(shè)BC的點(diǎn)除P之外全屬于E2，那么只要AB上有異于B的點(diǎn)S屬于E2，設(shè)S在BC上的投影點(diǎn)為Ｓ′，則△SS′B為直角三角形。 再設(shè)AB內(nèi)的每一點(diǎn)均不屬于E2，即除B之外全屬于E1，特別，R、A∈E1，于是A、Q、R∈E1，且AQR為一直角三角形。從而命題得證。評述：此例通過分割圖形構(gòu)造抽屜。在一個(gè)幾何圖形內(nèi)有若干已知點(diǎn)，我們可以根據(jù)問題的要求把圖形進(jìn)行適當(dāng)?shù)姆指?，用這些分割成的圖形作為抽屜，再對已知點(diǎn)進(jìn)行分類，集中對某一個(gè)或幾個(gè)抽屜進(jìn)行討論，使問題得到解決。映射與計(jì)數(shù)在解競賽題中的應(yīng)用內(nèi)容綜述

利用映射來解決計(jì)數(shù)問題，就是通過建立集合A與另一集合B之間的映射，把對集合A的計(jì)數(shù)轉(zhuǎn)移到對集合B的計(jì)數(shù)。實(shí)現(xiàn)這種轉(zhuǎn)移的關(guān)鍵是：（1）選擇適當(dāng)?shù)谋阌谟?jì)數(shù)的集合；（2）建立集合間的映射關(guān)系。

設(shè)f：是集合A到集合B上的映射，那么

（1）若f為單射，則。

（2）若f為滿射，則。

（3）若f為一一映射，則。【例題分析】

例1·從的棋盤中，取出一個(gè)由三個(gè)小方格組成的L形，有多少種不同取法？這里棋盤是指m條橫線與n條豎線所構(gòu)成的棋盤。

解：每種取法，都有一個(gè)點(diǎn)與它對應(yīng)，這個(gè)點(diǎn)就是所取L形中三個(gè)小方格的公共點(diǎn)（如圖1），它是棋盤上橫線與豎線的交點(diǎn)，且不在棋盤的邊界上。從圖2可看出，每個(gè)點(diǎn)對應(yīng)于4種不同取法，這4種取法構(gòu)成一個(gè)“田”字形。而每個(gè)“田”字形都有唯一的中心。（例如點(diǎn)B），即映射f：“田”字形→“田”字形中心，是棋盤上由小方格組成的“田”字集合到棋盤內(nèi)橫線與豎線的交點(diǎn)集（不包括邊界上的點(diǎn)）的一一映射。

顯然棋盤內(nèi)橫線與豎線的交點(diǎn)有個(gè)，所以，共有種不同取法。

說明：一般地，集合到集合的所有映射的個(gè)數(shù)為。

例2·中日圍棋擂臺賽，雙方各派6名隊(duì)員按預(yù)定順序出場，直到最后一方取勝，問可能出現(xiàn)的比賽過程種數(shù)有多少種？

解：設(shè)中國隊(duì)員對應(yīng)紅球，日方隊(duì)員對應(yīng)白球。將被淘汰隊(duì)員對應(yīng)的球按被淘汰的時(shí)間順序一一排列出來。負(fù)方隊(duì)員全部被淘汰，則相應(yīng)球全部排出，然后將勝方所剩隊(duì)員對應(yīng)的球依次排在后面。由于雙方隊(duì)員出場順序已定，故可設(shè)同色球之間無區(qū)別，于是一種比賽過程就對應(yīng)于6個(gè)紅球和6個(gè)白球的一種排列；反之，6個(gè)紅球和6個(gè)白球的一種排列對應(yīng)著一種比賽過程，即球的不同排列與不同比賽過程之間存在一一對應(yīng)關(guān)系。6個(gè)紅球和6個(gè)白球的不同排列數(shù)為，此即所求比賽過程種數(shù)。

說明在某種映射下，兩個(gè)集合元素間一一對應(yīng)，該映射即為一一映射，所以對于明顯的一一映射只須指出兩集合間的一一對應(yīng)關(guān)系，就可運(yùn)用對應(yīng)原理。

例3·求m元方程的正整數(shù)解的組數(shù)。

解法一：由于數(shù)組中各數(shù)可以重復(fù)，且大小無序，因此作如下映射：

顯然①

且一一對應(yīng)，所以，映射是一一映射。

因?yàn)?，滿足①的數(shù)組有個(gè)，所以所求方程解的組數(shù)為。

解法二：考慮長度為n的線段AB。方程的任一組解對應(yīng)于把線段分成m節(jié)的一種分法，其中第一節(jié)的長度為，第二節(jié)的長度為，…，第m節(jié)的長度為，而每一種分法又對應(yīng)于線段長n-1個(gè)分點(diǎn)中取出m-1個(gè)分點(diǎn)的一種取法。反過來，線段n-1個(gè)分點(diǎn)中取出m-1個(gè)分點(diǎn)的任一種取法，都把線段AB分成m節(jié)。令依次取m節(jié)的長度，就得到方程的一組解。所以，原方程解的組數(shù)就是線段AB上n-1個(gè)分點(diǎn)中取出m-1個(gè)的不同取法的種數(shù)。

說明：若把問題改為：求m元方程的非負(fù)整數(shù)解的組數(shù)，只要令，則化為求方程的正整數(shù)解的組數(shù)，由例4可知所求解的組數(shù)為。

例4·設(shè)為A的三元子集，若滿足為A的“好子集”，求A的“好子集”的個(gè)數(shù)。

解：令

作映射。

f是到上的一一映射。事實(shí)上，當(dāng)時(shí)，，那么即。

另一方面，若，則，即。

于是由對應(yīng)原理，，即A的“好子集”有個(gè)。

例5·設(shè)n為正整數(shù)，若的一個(gè)排列中存在，使成立，則稱該排列具有性質(zhì)P。證明：具有性質(zhì)P的排列比不具有性質(zhì)P的排列多。

證明設(shè)A是由不具有性質(zhì)P的排列構(gòu)成的集合，B是恰有一對滿足的排列構(gòu)成的集合，C是具有性質(zhì)P的所有排列構(gòu)成的集合，顯然，從而。設(shè)，其中必有一個(gè)，使，于是調(diào)整的位置如下，該排列僅有一對相鄰數(shù)滿足，從而。上述調(diào)整構(gòu)成了一個(gè)A到B的映射，因此，。又，故，即具有性質(zhì)P的排列比不具有性質(zhì)P的排列多。

例6·已知，，并且①②

求的個(gè)數(shù)。

解由②知中有n個(gè)+1，n個(gè)-1，這樣的有序數(shù)組有個(gè)。下面考慮這樣的有序數(shù)組中有多少不符合①，設(shè)其個(gè)數(shù)為。

如果不符合①，那么一定存在最小的自然數(shù)，滿足

（1）；

（2）將統(tǒng)統(tǒng)改變符號，這一對應(yīng)改為n+1個(gè)+1，n-1個(gè)-1組成的有序數(shù)組。

反之，對于任何一個(gè)n+1個(gè)+1，n-1個(gè)-1組成的有序數(shù)組，由于+1多于-1，必然存在一個(gè)最小的自然數(shù)s，滿足。

將變?yōu)?，就得到一個(gè)n個(gè)+1，n個(gè)-1組成的不符合①的有序數(shù)組，所以，f是一一映射，由對應(yīng)原理知等于n+1個(gè)+1，n-1個(gè)-1組成的有序數(shù)組的個(gè)數(shù)，即。

因此，符合題目條件的有序數(shù)組的個(gè)數(shù)為

例8已知數(shù)列滿足

。

對每一個(gè)整數(shù)，求滿足條件

的下標(biāo)n的個(gè)數(shù)。

解將滿足的自然數(shù)n用二進(jìn)制表示為，這里，可以證明

①

事實(shí)上，如果為偶數(shù)，則，均有為偶數(shù)，且；如果為奇數(shù)，則，均有為奇數(shù)，且所以①式成立。

反復(fù)利用①式可知

②

上式右邊為k個(gè)+1或-1的和。所以，當(dāng)k為奇數(shù)時(shí)，②的右邊為奇數(shù)，不會等于0，這表明，當(dāng)k為奇數(shù)時(shí)，滿足條件的下標(biāo)n的個(gè)數(shù)為0。

當(dāng)k為偶數(shù)時(shí)，若，則②式右邊恰有個(gè)+1，個(gè)-1。

設(shè)，n的二進(jìn)制表示為，，②式確定了一個(gè)A到B的映射：。

由于A中任意兩個(gè)元素的二進(jìn)制表示首位都為1，設(shè)。并設(shè)j為使的最大下標(biāo)。則。這說明是A到B的單射。又易知，所以又是A到B的滿射，從而是A到B的一一映射。

故滿足，且的下標(biāo)n的個(gè)數(shù)為B中恰有個(gè)-1的有序數(shù)組的個(gè)數(shù)，即。

綜上所述，當(dāng)為奇數(shù)時(shí)，滿足條件的下標(biāo)n的個(gè)數(shù)為0；當(dāng)k為偶數(shù)時(shí)，滿足條件的下標(biāo)n的個(gè)數(shù)為。

運(yùn)用映射法解決計(jì)數(shù)問題，關(guān)鍵在于建立映射關(guān)系，將難于計(jì)數(shù)的集合化為易于計(jì)數(shù)的集合來計(jì)數(shù)。這項(xiàng)工作具有較強(qiáng)的技巧性，需在平時(shí)學(xué)習(xí)中多體會，多實(shí)踐。計(jì)數(shù)和離散最值E2-002·在一次中學(xué)數(shù)學(xué)競賽中共出了A、B、C三題．在所有25個(gè)參加者中，每個(gè)學(xué)生至少解出一題，在沒有解出A的那些學(xué)生中，解出B的人數(shù)是解出C的人數(shù)的兩倍，只解出A的人數(shù)比余下的學(xué)生中解出A的人數(shù)多1．只解出一題的學(xué)生中，有一半沒有解出A．問有多少學(xué)生解出B？【題說】第八屆（1966年）國際數(shù)學(xué)奧林匹克題．由蘇聯(lián)提供．【解】設(shè)不僅解出A的為x人，僅解出B的為y人，解出B與C由（1）、（2）得由（3），x≤7．由（4），x=7，4，1．僅解出B的人數(shù)為6．E2-003·一個(gè)長方體盒子能用單位立方體填滿，如果我們改放盡可能多的體積是2的立方體，且使立方體的邊平行盒邊，則恰好能填到盒【題說】第十八屆（1976年）國際數(shù)學(xué)奧林匹克題．本題由荷蘭提供．40％×a1a2a3=2b1b當(dāng)a＞10時(shí)，b≥8，所以綜上所述，所求的盒子尺寸為2×3×5或2×5×6．E2-004·如圖，有10個(gè)村莊，分別用點(diǎn)A1，A2，…，A10表示，某人從A1出發(fā)，按箭頭所指的方向（不準(zhǔn)反向）可以選擇任意一條路徑走向其他某個(gè)村莊，試問：1．按圖中所示方向從A1到A5（不繞圈）有多少種不同的走法？2．從A1出發(fā)，按圖中所示方向，繞一圈后再回到A1，有多少種不同的走法？【題說】1979年湖北省賽二試題．【解】為方便計(jì)，設(shè)從A1到Ai的走法有ai種，這些走法分為兩類：一類是從A1出發(fā)，經(jīng)過Ai-2到達(dá)Ai（不經(jīng)過Ai-1），這時(shí)從A1到Ai-2的走法為ai-2，從Ai-2不經(jīng)過Ai-1到Ai的走法只有一種，所以這類走法共ai-2種．第二類是從A1出發(fā)，經(jīng)過Ai-1到達(dá)Ai，共ai-1種，而這兩類走法是互不相同的，所以，從A1到Ai的走法共ai=ai-1+ai-2（種）顯然a2=1，a3=2．于是a5=2a3+a2=5，a6，a7，a8，a9，a10，a11分別為8，13，21，34，55，89．所以從A1到A5有5種不同的走法，從A1出發(fā)，繞一圈回到A，有89種不同的走法．E2-005·在直角坐標(biāo)平面的第一象限中，把坐標(biāo)都是整數(shù)的點(diǎn)按以下方法編號：（0，0）點(diǎn)第1號，（1，0）點(diǎn)第2號，（1，1）點(diǎn)第3號，（0，1）點(diǎn)第4號，（0，2）點(diǎn)第5號，（1，2）點(diǎn)第6號，（2，2）點(diǎn)第7號，（2，1）點(diǎn)第8號，（2，0）點(diǎn)第9號，…按圖中箭頭的順序，求第2000號的點(diǎn)的坐標(biāo)．【題說】1979年北京市賽二試題1．【解】設(shè)k為正整數(shù)，則滿足條件：0≤x≤k，0≤y≤k的坐標(biāo)為整數(shù)的點(diǎn)（x，y）共有（k+1）2個(gè)，而滿足條件：（k+1）2＜2000的最大整數(shù)k=43．因此編號為2000的點(diǎn)的縱坐標(biāo)為44或橫坐標(biāo)為44．因44為偶數(shù)，故應(yīng)從點(diǎn)（0，44）往右數(shù)，又因2000-442=64＞44故第2000號的點(diǎn)的橫坐標(biāo)為44．其縱坐標(biāo)是44-（64-45）=25所以編號2000的點(diǎn)的坐標(biāo)是（44，25）．E2-006·散步時(shí)，每步長為1，向南、北、東、西任一方向均可，如果每一點(diǎn)不通過兩次，則稱這散步為自身回避的，設(shè)從原點(diǎn)開始的、n步的、自身回避的散步種數(shù)為f（n）．求f（1），f（2），f（3），f（4），并證明2n＜f（n）＜4·3n-1【題說】第十一屆（1979年）加拿大數(shù)學(xué)奧林匹克題．【解】容易算得f（1）=4f（2）=4×3=12f（3）=4×3×3=36對于4步的自身回避散步，則有f（4）=4×3×3×3-8=100假設(shè)每次均向北或西兩個(gè)方向走，當(dāng)然不會出現(xiàn)有一點(diǎn)通過兩次的情況，所以2n＜f（n）如果僅考慮不反過身來往回走，那么共有4×3n-1種（其中可能出一點(diǎn)通過兩次的情況），所以f（n）≤4×3n-1（當(dāng)n=1，2，3時(shí)取等號）．E2－007·設(shè)n和k是正整數(shù)，S是平面上n個(gè)點(diǎn)的集合，滿足：（1）S中任何三點(diǎn)不共線；（2）對S中的每一個(gè)點(diǎn)P，S中至少存在k個(gè)點(diǎn)與P距離相等．【題說】（1989年國際數(shù)學(xué)奧林匹克題，由荷蘭提供．條件（1）可以取消．【證】以S中的兩個(gè)點(diǎn)為端點(diǎn)的線段稱為“好線段”．另一方面，以S中任一點(diǎn)P為圓心，可以作一個(gè)圓，圓上至少有k計(jì)算在內(nèi)）．從而至少有條弦是好線段．E2－008·學(xué)校舉辦足球循環(huán)賽，每個(gè)參賽隊(duì)都與其他隊(duì)各賽一場，勝一場積2分，平一場積1分，負(fù)一場積0分，已知僅有一個(gè)隊(duì)積分最多，但他勝的場數(shù)最少，問至少有幾隊(duì)參賽，才有可能這樣？【題說】第十六屆（1990年）全俄數(shù)學(xué)奧林匹克九年級題．【解】稱積分最多的為冠軍，設(shè)冠軍勝n場，平m場，則他共積2n+m分，由題設(shè)，其余各隊(duì)勝的場數(shù)不少于n+1，即積分不少于2（n+1）．由2n+m＞2n+2得m≥3．從而有隊(duì)踢過平局，他們的積分不少于2（n+1）+1，由2n+m≥2n+3，得m≥4．冠軍隊(duì)至少勝1場，否則，它的積分不多于S-1（S是參賽的隊(duì)數(shù)）．其余隊(duì)的積分少于S-1，于是所有參賽隊(duì)積分之和少于S（S-1）．而每賽一場，雙方積分之和總是2分，因此所有隊(duì)積分之和應(yīng)是2·S（S-1）/2=S（S-1），矛盾．這樣，m≥4，n≥1，因此冠軍隊(duì)比賽場數(shù)不少于5，參賽隊(duì)數(shù)（包括冠軍隊(duì)）不少于6．下面的比賽積分表表明，有6個(gè)隊(duì)（分別用A、B、C、D、E、F表示）參賽且滿足題設(shè)要求的比賽結(jié)果．因此至少6隊(duì)參賽．E2－009·設(shè)n≥3．考慮在同一圓周上的2n-1個(gè)互不相同的點(diǎn)所成的集合E．將E中一部分點(diǎn)染成黑色，其余的點(diǎn)不染顏色．如果至少有一對黑點(diǎn)，以它們?yōu)槎它c(diǎn)的兩條弧中有一條的內(nèi)部（不包含端點(diǎn)）恰含E中n個(gè)點(diǎn)，則稱這種染色方式為好的．如果將E中k個(gè)點(diǎn)染黑的每一種染色方式都是好的，求k的最小值．【題說】1990年國際數(shù)學(xué)奧林匹克題．本題由捷克提供．【解】將E中的點(diǎn)依次記為1，2，3，…，2n-1，并將點(diǎn)i與i+（n-1）用一條邊相連（我們約定j+（2n-1）·k，k∈Z，表示同一個(gè)點(diǎn)j）．這樣得到一個(gè)圖G．G的每個(gè)點(diǎn)的次數(shù)均為2（即與兩個(gè)點(diǎn)相連），并且相差為3的兩個(gè)點(diǎn)與同一點(diǎn)相連．由于G的每個(gè)點(diǎn)的次數(shù)為2，G由一個(gè)或幾個(gè)圈組成．在32n-1時(shí)，1，2，…，2n-1中每一點(diǎn)j都可以表示成3k的形式（即方程3x≡j（mod2n-1）有解），因此圖G是一個(gè)長為2n-1的圈．在這圈上可以取出n-1個(gè)互不相鄰的點(diǎn)，而且至多可以取出n-1個(gè)互不相鄰的點(diǎn)．為共可取出n-2個(gè)點(diǎn)互不相鄰．綜上所述，在32n-1時(shí)，mink=n．在3|2n-1時(shí)，mink=n-1．E2－010·地面上有10只小鳥在啄食，其中任意5只鳥中至少有4只在一個(gè)圓周上，問有鳥最多的一個(gè)圓周上最少有幾只鳥？【題說】1991年中國數(shù)學(xué)奧林匹克題3．【解】9只鳥在同一圓周上，1只鳥不在這圓周上，滿足題目條件．設(shè)有鳥最多的圓上至少有l(wèi)只鳥，則4≤1≤9．首先證明，l≠4．由l≤9，必有4只鳥不在同一圓周上，過其中每3只作一個(gè)圓，共得4個(gè)圓，其余6只鳥中的每一只與上述4只鳥組成5元組，因而這只鳥必在（上述4個(gè)圓中）某一個(gè)圓上，6只鳥中必有2只在同一個(gè)圓上，從而這個(gè)圓上至少有5只鳥．其次，如果5≤l≤8，設(shè)圓C上有l(wèi)只鳥，則C外至少有兩只鳥b1、b2．對圓C上任三只鳥，其中必有兩只與b1、b2共圓，設(shè)C上的b3、b4與b1、b2共圓，b5、b6與b1、b2共圓，C上第5只鳥b7及b3、b5，這3只鳥中沒有兩只能與b1、b2共圓，矛盾．所以l=9．E2－011·給定空間中的9個(gè)點(diǎn)，其中任何4點(diǎn)都不共面，在每一對點(diǎn)都連著一條線段．試求出最小的n值，使得將其中任意n條線段中的每一條任意地染為紅、藍(lán)二色之一，在這n條線段的集合中都必然包含有一個(gè)各邊同色的三角形．【題說】1992年國際數(shù)學(xué)奧林匹克題，本題由中國提供．色的線段至多3條．若點(diǎn)A1引出不染色的線段，去掉A1及所引出的線段，若剩下的圖中，還有點(diǎn)A2引出不染色的線段，去掉A2及所引出的線段．依此進(jìn)行，由于不染色的線段至多3條，所以至多去掉3個(gè)頂點(diǎn)（及從它們引出的線段），即有6個(gè)點(diǎn)，每兩點(diǎn)之間的連線染上紅色及藍(lán)色．熟知這里存在一個(gè)同色三角形．如圖表明染色的邊少于33條時(shí)，未必有同色三角形（不染色的邊1—9、2—8、3—7、4—6沒有畫出），其中1、9與2、8間的虛線表明1—2、1—8、9—2、9－8均為虛線，5與4、6間的實(shí)線表明5—4、5—6均為實(shí)線等等．因此n=33．E2－012·10人到書店買書，如果已知（1）每人都買了三本書；（2）任二人所買書中都至少有一本相同，問最受歡迎的書（購買人數(shù)最多者）最少有幾人購得？為什么？【題說】1993年中國數(shù)學(xué)奧林匹克（第八屆數(shù)學(xué)冬令營）題．【解】設(shè)最受歡迎的書有k人購買．每人買3本書，共買30本書．若k≤4，由于430，不可能每種書均被4人購買．設(shè)第一個(gè)人購的書為a、b、c，并且買a的人≤3個(gè)，則與第一個(gè)人的公共圖書為a的，不超過2人；為b或c的，均不超過3人．從而總?cè)藬?shù)≤1+2+3+3=9，矛盾！因此k≥5．現(xiàn)給出一種k=5的購書法：因此，被購買人數(shù)最多的一種書，最少有5人購買。E2－013·若干個(gè)學(xué)校參加網(wǎng)球比賽，同一學(xué)校之間的選手不比賽，每兩個(gè)學(xué)校的每兩個(gè)選手都要比賽一場．在兩個(gè)男孩或兩個(gè)女孩之間進(jìn)行的比賽稱為單打；一個(gè)男孩和一個(gè)女孩之間的比賽稱為混合單打．男孩的人數(shù)與女孩的人數(shù)至多相差1．單打的場數(shù)和混合單打的場數(shù)也至多相差1．問有奇數(shù)個(gè)選手的學(xué)校至多有幾個(gè)？【題說】第二十五屆（1993）加拿大數(shù)學(xué)奧林匹克題．【解】設(shè)有n個(gè)學(xué)校，第i個(gè)學(xué)校派出xi個(gè)男選手、yi個(gè)女選手，i=1，2，…，n．由題意，有場．由題意，有≤1+2=3即在（xi-yi）（i=1，2，…，n）中至多只有三項(xiàng)不為零，而且這n項(xiàng)都應(yīng)為1．這就是說，至多3個(gè)學(xué)校的人數(shù)xi+yi為奇數(shù)。如果只有3個(gè)學(xué)校，其中2個(gè)各派1名男孩，另1個(gè)學(xué)校派1名女孩，那么題目中的條件全滿足，而奇數(shù)個(gè)選手的學(xué)校恰好3個(gè)。E2—015·設(shè)n、k∈N且k≤n并設(shè)S是含有n個(gè)互異實(shí)數(shù)的集合．設(shè)T是所有形如x1+x2+…+xk的實(shí)數(shù)的集合，其中x1，x2，…，xk是S中的k個(gè)互異元素．求證T至少有k（n-k）+1個(gè)互異的元素．【題說】1993年IMO預(yù)選題．本題由愛爾蘭提供．【證】n=k時(shí)結(jié)論顯然．假設(shè)命題對n-1（≥k）成立．考慮由s1＞s2＞…＞sn組成的n元集S．由歸納假設(shè)，對S0=｛s2，s3，…，sn｝存在k（n-1-k）+1個(gè)形如x1+x2+…+xk的互不相等的數(shù)，其中x1，x2，…，xk是S0中不同元素．顯然s1+s2+…+sk＞s1+s2+…+sk-1+sk+1＞s1+s2+…+sk-2+sk+sk+1＞…＞s1+s2+s4+…+sk+1＞s1+s3+s4+…+sk+1并且這k個(gè)數(shù)中最小的大于s2+s3+…+sk+1，即大于S0中任k個(gè)元素的和．所以對n元集S，相應(yīng)的集T至少有k（n-1-k）+1+k=k（n-k）+1個(gè)元素．于是，本題結(jié)論對一切自然數(shù)n≥k成立．E2-016·S是{1，2，…，1989}的一個(gè)子集，而且S中任意兩個(gè)數(shù)的差不能是4或7，那么S中最多可以有多少個(gè)元素？【題說】第七屆（1989年）美國數(shù)學(xué)邀請賽題．【解】將1，5，9，2，6，10，3，7，11，4，8順次放在圓周上．如果從中選出6個(gè)數(shù)，那么必有兩個(gè)在圓周上相鄰，即它們的差為4或7，所以從1，2，3，…，11中最多能選出5個(gè)數(shù)，每兩個(gè)的差不為4或7．這5個(gè)數(shù)可以是1，3，4，6，9．同理，在每11個(gè)連續(xù)自然數(shù)中最多能選出5個(gè)數(shù)，每兩個(gè)的差不為4或7．{1，2，…，1989}可分拆為181個(gè)子集{11j+1，11j+2，…，11j+11}（j=0，1，…，179）及{1981，1982，…，1989}，所以|S|≤5×181=905．11j+1，11j+3，11j+4，11j+6，11j+9（j=0，1，…，180）．這905個(gè)數(shù)中，每兩個(gè)的差不為4或7（若其中有（11j+b）-（11j+a）=4或7，則a-b=7或4）．因此S最多可以有905個(gè)元素．E2-017·整數(shù)1，2，…，n的排列滿足條件：每個(gè)數(shù)或者大于它之前的所有數(shù)，或者小于它之前的所有數(shù)，試問有多少個(gè)這樣的排列？【題說】1989年加拿大數(shù)學(xué)奧林匹克題．【解】設(shè)所求排列數(shù)為A（n），不難求得A（1）=1，A（2）=2，A（3）=4對自然數(shù)1，2，…，n，設(shè)n排在第k個(gè)位置（1≤k≤n），則在它之后只有一種排法：n-k，n-k-1，…，1；而在它之前有A（k-1）種排法，故A（n）=1+A（1）+A（2）+…+A（n-1）（n≥2）借助這遞推關(guān)系，由歸納法易知A（n）=2n-1．【別解】除第1位外，其余的位置有兩種選擇：在這位上的數(shù)大于它以前的數(shù)，或小于它以前的數(shù)，設(shè)第j1＜j2＜…＜jl位是前一種，則它對應(yīng)于排列：在這l個(gè)位上從右至左放n，n-1，…，n-l+1；在其余位上自左至右放n-l，n-l-1，…，2，1．選擇有2n-1種，排列也有2n-1種．E2-018·設(shè)n是正整數(shù)，我們說集合{1，2，…，2n}的一個(gè)排列（x1，x2，…，x2n）具有性質(zhì)p，如果在{1，2，…，2n-1}當(dāng)中至少有一個(gè)i使|xi-xi+1|=n成立．求證：對于任何n，具有性質(zhì)p的排列比不具有性質(zhì)p的排列個(gè)數(shù)多．【題說】第三十屆（1989年）國際數(shù)學(xué)奧林匹克題．【證】設(shè)（x1，x2，…，x2n）中k與k+n相鄰的排列的集合為Nk（1≤k≤n），則具有性質(zhì)p的排列個(gè)數(shù)而|Nk|=2×（2n-1）！，|Nk∩Nh|=22×（2n-2）！，將k與k+n、h與h+n并在一起，2n-2個(gè)“數(shù)”有（2n-2）！種排列，其中k與k+n，h與h+n并成的“數(shù)”可以將k+n與k，h+n與h的位置交換，各有兩種排列，所以＝（2n）！2n×2（n-1）×（2n-2）?。?n×（2n-2）！×nE2-019·在坐標(biāo)平面上，橫坐標(biāo)和縱坐標(biāo)均為整數(shù)的點(diǎn)稱為整點(diǎn)．對任意自然數(shù)n，連結(jié)原點(diǎn)O與點(diǎn)An（n，n+3），用f（n）表示線段OAn上除端點(diǎn)外的整點(diǎn)個(gè)數(shù)，求f（1）+f（2）+…+f（1990）的值．【題說】1990年全國聯(lián)賽一試題．原題為填空題．【解】OAn的方程是y=（n+3）x/n（0＜x＜n）．因?yàn)閚不能整除x，若x、y是整數(shù)，n不與n+3互素，必為3的倍數(shù)．設(shè)n=3m，則y=（m+1）x/m，x只可取m、2m兩個(gè)值．小于1990的3的倍數(shù)有663個(gè)，故所求的值是2×663=1326．E2-020·8個(gè)女孩和25個(gè)男孩圍成一圈，任意兩個(gè)女孩之間至少站兩個(gè)男孩，求共有多少種不同的排列方法？（只要把圓圈旋轉(zhuǎn)一下就重合的排法認(rèn)為是相同的．）【題說】1990年全國聯(lián)賽一試題．原題為填空題．【解】因旋轉(zhuǎn)重合認(rèn)為相同，可讓某女孩G固定不動，從25個(gè)男孩中任選16人，使每兩人隨一個(gè)女孩，這16人可任意排列；對每一種排列，除G外的7個(gè)女孩各與其后的兩個(gè)男孩看成一個(gè)“個(gè)體”，連同其余9個(gè)男孩，總共16個(gè)“個(gè)體”，又可任意排列，其總數(shù)為E2-021·一個(gè)正三角形，每邊被等分為n份，過各分點(diǎn)作其它兩邊的平行線．一共產(chǎn)生多少個(gè)三角形（包括原來的三角形在內(nèi)）？【題說】1990年中國集訓(xùn)隊(duì)測試題17．【解】設(shè)原三角形的邊長為n，記邊長為k（1≤k≤n）的“頭數(shù)為yl，則頭朝上的三角形共有：x1=2+2+…+n=n（n+1）/2x2=1+2+…+（n-1）…xn-1=1+2，xn=1頭朝下的三角形共有：y1=1+2+…+（n-1）=n（n-1）/2y2=1+2+…+（n-3）=（n-2）（n-3）/2…yl=1+2+…+（n-2l+1）=（n-2l+1）（n-2l+2）/2…（1）當(dāng)n為偶數(shù)時(shí)，由上式可知（2）當(dāng)n為奇數(shù)時(shí)，E2-022·在一次射擊比賽中，有8個(gè)泥制的靶子掛成如圖所示的三列（其中兩列3個(gè)，一列2個(gè)）．一位神槍手按下面的規(guī)則打中所有靶子：1．首先選擇一列；2．再打掉所選一列的最下面未打過的靶子，問打中這8個(gè)靶子共有多少種不同的順序？【題說】第八屆（1990年）美國數(shù)學(xué)邀請賽題．【解】隨意射擊8個(gè)靶子有8！種方法．由于每列靶子的順序已經(jīng)確定，所以現(xiàn)在的射法共有種不同的順序．E2-023·設(shè)S={1，2，…，n}，A為至少含有兩項(xiàng)的、公差為正的等差數(shù)列，其項(xiàng)都在S中，且添加S的其他元素于A后均不能構(gòu)成與A有相同公差的等差數(shù)列．求這種A的個(gè)數(shù)．（這里只有兩項(xiàng)的數(shù)列也看作等差數(shù)列．）【題說】1991年全國聯(lián)賽二試題．【解】對于n=2k，所述數(shù)列A必有連續(xù)兩項(xiàng)，一項(xiàng)在{1，2，…，k}中，另一項(xiàng)在{k+1，k+2，…，n}中。反之，從{1，2，…，k}中任取一個(gè)數(shù)，{k+1，k+2，…，n}中也任取一個(gè)數(shù)，以它們的差為公差、并以這兩數(shù)為該數(shù)列的連續(xù)兩項(xiàng)可作出一個(gè)A．此對應(yīng)是一一對應(yīng)，故這種A的個(gè)數(shù)為k2=n2/4．對于n=2k+1，情況完全類似，注意集合{k+1，k+2，…，n}中有k+1個(gè)數(shù)，故這種A的個(gè)數(shù)為k（k+1）=（n2-1）/4．兩式可統(tǒng)一為[n2/4]．（[x]表示不超過x的最大整數(shù)．）E2-024·下圖中將等邊三角形每邊3等分，過等分點(diǎn)作每邊平行線，這樣所形成的平行四邊形個(gè)數(shù)，記為f（3），則f（3）=15．將等邊三角形每邊n等分，過各分點(diǎn)作各邊平行線，所形成的平行四邊形個(gè)數(shù)記為f（n），求f（n）表達(dá)式．【題說】第二十三屆（1991年）加拿大數(shù)學(xué)奧林匹克題．【解】如圖所示的平行四邊形，由a、b、c、d四個(gè)數(shù)決定．這4個(gè)數(shù)滿足a≥1，b≥1，c≥0，d≥02≤a+b+c+d≤n即0≤a1+b1+c+d≤n-2其中a1=a-1，b1=b-1，c，d均為非負(fù)整數(shù)．因此平行四邊形的總數(shù)為【別解】在BA、BC的延長線上分別取E、F，使BE=BF=n+1，則EF=n+1．圖中的平行四邊形，每一邊恰好與EF相交于一點(diǎn)．這四點(diǎn)不同，都是EF上的格點(diǎn)（即將EF等分為n+1份的分點(diǎn)）．反之，從EF的n+2個(gè)格點(diǎn)（包括E、F在內(nèi)）中任取四點(diǎn)，過靠近E的兩點(diǎn)作AB的平行線，過另兩點(diǎn)作BC的平行線，便可得到一個(gè)圖中的平行四邊形，所以E2-025·若平面上有997個(gè)點(diǎn)，如果每兩點(diǎn)連成一條線段，且中點(diǎn)涂成紅色．證明：平面上至少有1991個(gè)紅點(diǎn)．你能找到一個(gè)正好是1991個(gè)紅點(diǎn)的特例嗎？【題說】1991年亞太地區(qū)數(shù)學(xué)奧林匹克題．【證】在給定的997個(gè)點(diǎn)中，設(shè)M、N兩點(diǎn)間的距離最大，分別以M、N為圓心，MN/2為半徑作圓，這兩個(gè)圓僅有一個(gè)公共點(diǎn)，即MN的中點(diǎn)E．于是MP的中點(diǎn)必在⊙M內(nèi)部或圓周上，這樣的995個(gè)點(diǎn)互不相同．同理，NP的中點(diǎn)必在⊙N內(nèi)部或圓周上，這樣的995個(gè)點(diǎn)互不相同，而且與上面的995個(gè)中點(diǎn)均不相同，加上點(diǎn)E，共有2×995+1=1991個(gè)紅點(diǎn)．x軸上橫坐標(biāo)分別為1，2，…，997的997個(gè)點(diǎn)就是滿足要求的例子。E2-026·A，B分別是坐標(biāo)平面上的格點(diǎn)的集合：A={（x，y）|x，y為正整數(shù)，1≤x≤20，1≤y≤20}B={（x，y）|x，y為正整數(shù)，2≤x≤19，2≤y≤19}A中的點(diǎn)分別染成紅色或藍(lán)色．染成紅色的點(diǎn)有219個(gè)，其中有180個(gè)包含于B中，又四個(gè)角上的點(diǎn)（1，1），（1，20），（20，1），（20，20）都染成藍(lán)色．將水平或垂直方向上相鄰兩點(diǎn)按下列要求用紅、藍(lán)、黑色的線段連接起來：兩點(diǎn)均為紅色時(shí)，用紅線連接；兩點(diǎn)均為藍(lán)色時(shí)，用藍(lán)線連結(jié)；兩點(diǎn)為一紅一藍(lán)時(shí)，用黑線連結(jié)．問：（長度為1的）黑線有237段時(shí)，（長度為1的）藍(lán)線有多少段？【題說】1992年日本數(shù)學(xué)奧林匹克預(yù)選賽題．【解】集合A中有400個(gè)點(diǎn)，其中紅點(diǎn)有219個(gè)，藍(lán)點(diǎn)有181個(gè)，在B內(nèi)有藍(lán)點(diǎn)144個(gè)．A的四周有76個(gè)點(diǎn)，其中紅點(diǎn)39個(gè)，藍(lán)點(diǎn)37個(gè)（包括四個(gè)角上的點(diǎn)）．每個(gè)角上的點(diǎn)引出2條線段；每個(gè)邊界上（除四個(gè)角）的點(diǎn)引出3條線段；每個(gè)B內(nèi)的點(diǎn)引出4條線段．因此，對于藍(lán)點(diǎn)共引出線段2×4+3×33+4×144=683（段）其中黑線有237段，所以藍(lán)線有683-237=446（段）這些藍(lán)線在上述計(jì)數(shù)時(shí)，被重復(fù)計(jì)算了一次，故實(shí)際上有藍(lán)線446÷2=223（段）E2-027·紅色和白色的椅子各有5張，圍成一個(gè)圓圈，共有多少種不同的排法？同色的椅子是沒有區(qū)別的，經(jīng)旋轉(zhuǎn)后排列的順序一致的排法只算1種．【題說】1994年日本數(shù)學(xué)奧林匹克預(yù)選賽題．【解】將椅子的位置編號為0～9．紅色椅子的位置是集合A={0，然有f(10)（R）=f（R）．從而使得f(n)（R）=R的最小正整數(shù)n0必是10的約數(shù)．每種這樣的排法R都被重復(fù)計(jì)算了n0次．r1+r2+…+r5≡（r1+5）+（r2+5）+…+（r5+5）（mod10）≡（r1+…+r5）+25（mod10）所以25≡0（mod10）這不可能．所以n0≠5．若n0=2，易知只有R={0，2，4，6，8}和{1，3，5，7，9}滿足要求．除此以外的250種R，其n0均為10．故所求的排法數(shù)為

E2-028·A={0，1，2，3，4，5，6，7，8，9}，滿足下列條件（1），（2）的子集S有多少個(gè)？（1）S的元素有5個(gè)；（2）S中任意兩個(gè)不同元素的和的個(gè)位數(shù)字恰好是0到9這10個(gè)整數(shù)．【題說】1994年日本數(shù)學(xué)奧林匹克預(yù)選賽題．【解】這樣的子集不存在，即滿足條件的S的個(gè)數(shù)為0．事實(shí)上，若存在滿足條件的子集S={a1，a2，a3，a4，a5}，由于4（a1+a2+a3+a4+a5）≡0+1+…+9（mod10）上式左邊為偶數(shù)，右邊為奇數(shù)，不可能．E2-029·設(shè)p是一個(gè)奇素?cái)?shù)，考慮集合{1，2，…，2p｝的滿足以下兩條件的子集A：（i）A恰有p個(gè)元素；（ii）A中所有元素之和可被p整除．試求所有這樣的子集A的個(gè)數(shù)．【題說】第三十六屆（1995年）國際數(shù)學(xué)奧林匹克題．與V={p+1，p+2，…，2p}外，每一個(gè)p子集與U、V的交均非空．將這些子集分類，如果子集S、T與V的交S∩V=T∩V，并且S∩U的每個(gè)元加上k（modp）就得到T∩U的每個(gè)元，這里k∈{0，1，2，…，p-1}，那么就將S與T歸入同一類．對于{0，1，2，…，p-1}中不同的k1、k2，由S得到的集T1、T2，元素和σ（T1）、σ（T2）的差≡（k1-k2）m（modp），這里m=S∩U的元素個(gè)數(shù)．由于S與U、V的交均非空，0＜m＜p，所以（k1-k2）m0（modp），即T1≠T2．因此，每一類中恰好有p個(gè)集，并且這些集的元素之和modp各不相同．于是其中恰有一個(gè)集元素之和被p整除．從而所求子集A的個(gè)數(shù)為

E2-030·4對夫婦去看電影，8個(gè)人坐成一排．若女性的鄰座只能是其丈夫或其他女性，共有幾種坐法？【題說】1995年日本數(shù)學(xué)奧林匹克預(yù)選賽題．【解】先將女性排定，有4！種方法．女性與女性之間若坐著男性（包括這些女性的丈夫）必不少于兩個(gè)．同樣，在男性與男性之間坐著的女性也必不少于兩個(gè)．把座位連在一起的女性視為一組，則4位女性的分組方式有4，3+1，2+2，2+1+1，1+1+1+1等五種．孤立坐著的女性必須在這一排座位的兩端，所以1+1+1+1的分組方式不合要求．女性分成2+1+1時(shí)，兩端必須坐著女性，這時(shí)男性只能分成2+2，即下表中的第1類，男性的排法只有1種．女性分成2+2時(shí)，有下表的2，3，4，5四類，男性的排法分別有2，1，1，1種．女性分成3+1時(shí)，有下表的6，7，8三類，男性的排法分別有2，1，1種．女性4人連排時(shí)，有下表的9，10，11三類，男性的排法分別有3！，2！，2！種．于是排法總數(shù)為4!×（1+2+2×1+2×1+1+2×2+2×1+2×1+2×3!+2×2!+2!）=24×34=8161．女男男女女男男女，2．女女男男男男女女，3．女女男男男女女男，或男女女男男男女女，4．女女男男女女男男，或男男女女男男女女，5．男女女男男女女男，6．女女女男男男男女，或女男男男男女女女，7．男男女女女男男女，或女男男女女女男男，8．男女女女男男男女，或女男男男女女女男，9．女女女女男男男男，或男男男男女女女女，10．男男男女女女女男，或男女女女女男男男11．男男女女女女男男E2-031·用六種不同顏色中幾種染一個(gè)正方體各面，要求相鄰兩面不同色，問有多少種不同的染色法？（兩個(gè)染色正方形，如果能通過轉(zhuǎn)動、翻身使二者各面顏色對應(yīng)相等，則認(rèn)為是染色法相同）【題說】1996年全國數(shù)學(xué)聯(lián)賽一試題，原為填空題．【解】分4種情況討論：1°用了6種顏色．將一種顏色染下底，則上底有5種染法．固定一種顏色朝東，其它三面有3！種染法．共有5×3！=30種．=90種．所以染色法共有30+90+90+20=230種。E2-032·在直角坐標(biāo)平面上，以（199，0）為圓心、以199為半徑的圓周上，整點(diǎn)的個(gè)數(shù)有多少個(gè)？【題說】1996年全國數(shù)學(xué)聯(lián)賽一試題，原為填空題．【解】該圓方程為（x-199）2+y2=1992

（1）顯然，（1）有4個(gè)整數(shù)解：（0，0），（199，199），（199，-199），（389，0）．當(dāng)y≠0、±199時(shí)，|y|與199互素，故由（1）知：|x-199|、|y|、199是一組基本勾股數(shù)．由勾股數(shù)基本公式知，存在二正整數(shù)m、n使199=m2+n2．由于平方數(shù)≡0或1（mod4），所以m2+n2≡0，1或2（mod4），但199=4×49+3≡3（mod4）矛盾．因此當(dāng)y≠0、±199時(shí)，（1）無整數(shù)解．綜上所述，在（1）圓周上的整點(diǎn)只有4個(gè)．E2-033·一個(gè)7×7的棋盤的2個(gè)方格著黃色，其余的方格著綠色．如果一種著色法可從另一種著色法經(jīng)過在棋盤的平面中的旋轉(zhuǎn)而得到，那么這兩種著色法看做同一種．可能有多少種不同的著色法？【題說】第十四屆（1996年）美國數(shù)學(xué)邀請賽題．如果這一對方格關(guān)于棋盤中心中心對稱，那么旋轉(zhuǎn)后可與另一對方不關(guān)于棋盤中心中心對稱，那么繞中心旋轉(zhuǎn)90°、180°、270°，分別與另外三對方格重合，經(jīng)過旋轉(zhuǎn)也只可能與這三對重合．因此不同的E2-034·兩個(gè)正數(shù)的調(diào)和平均是它們的倒數(shù)的算術(shù)平均的倒數(shù)．有多少個(gè)正整數(shù)的有序?qū)Γ▁，y），使得x＜y且x與y的調(diào)和平均等于620？【題說】第十四屆（1996年）美國數(shù)學(xué)邀請賽題．E2-035·有多少對正整數(shù)x、y滿足x≤y，并且最大公約數(shù)（x，y）=5！，最小公倍數(shù)[x，y]=50??？【題說】第二十九屆（1997年）加拿大數(shù)學(xué)奧林匹克題．【解】設(shè)x=5！a，y=5！b，a、b為互質(zhì)的自然數(shù)，則[x，y]=5！[a，b]=5！ab．所以其中a1，…，a15都是正整數(shù)．由于a、b互質(zhì)，所以每一因數(shù)pa（p∈{2，3，5，…，47}）或者是a的因數(shù)，或者是b的因數(shù)，兩種情況恰好出現(xiàn)一種，而a≤b，E2-036·平面上給定五個(gè)點(diǎn)，這些點(diǎn)兩兩之間的連線互不平行，又不垂直，也不重合，從任何一點(diǎn)開始，向其余四個(gè)點(diǎn)兩兩之間的聯(lián)線作垂線，如果不計(jì)已知的五個(gè)點(diǎn)，所有這些垂線間的交點(diǎn)數(shù)最多是多少？【題說】第六屆（1964年）國際數(shù)學(xué)奧林匹克題5．本題由羅馬尼亞提供．再因每三點(diǎn)構(gòu)成一個(gè)三角形，這個(gè)三角形的三條高共點(diǎn)，應(yīng)從中減所以，交點(diǎn)最多有E2-037·某委員會開了40次會議，每次有10人出席，而且委員會任意兩個(gè)成員都未在一起出席過一次以上的會議，證明：該委員會成員一定多于60．【題說】1965年全俄數(shù)學(xué)奧林匹克十年級題．會議，可以組成不同的兩人組共有45×40=1800個(gè)，但由60人最多只定多于60．次會議，與他同出席會議的人都不相同，從而人數(shù)≥7×9=63＞0，矛盾。E2-038·在平面上給出n（≥3）個(gè)點(diǎn)，其中任兩點(diǎn)的距離最大為d．距離為d的兩點(diǎn)間的線段稱為這組點(diǎn)的直徑．證明：直徑的數(shù)目至多n條．【題說】1965年國際數(shù)學(xué)奧林匹克題．本題由波蘭提供．【證】假定直徑多于n條．如果從某個(gè)點(diǎn)出發(fā)的直徑少于兩條，我們就把這點(diǎn)除去，剩下的n-1個(gè)點(diǎn)至少有n條直徑，顯然n-1≥3，故不妨假設(shè)從每一點(diǎn)都至少引出兩條直徑．因?yàn)橹睆綌?shù)目比點(diǎn)多，而每條直徑都連結(jié)兩個(gè)點(diǎn)，所以至少有一點(diǎn)A引出三條直徑AB、AC、AD，每兩條直徑的夾角不超過60°，否則另一端的距離大于d．不妨設(shè)AD在AB與AC之間，因此，⊙（A，d）（以A為圓心，d為半徑的圓）、⊙（B，d）、⊙（C，d）的公共部分覆蓋了整個(gè)點(diǎn)集，而與D距離為d的點(diǎn)只有A點(diǎn)一個(gè)（圖中，以DG＜CG=d．同理可證D到除A外的其它點(diǎn)距離＜d）．即D點(diǎn)只引出一條直徑，矛盾！故命題成立。E2-039·有20個(gè)隊(duì)參加全國足球冠軍決賽．為了使任何三個(gè)隊(duì)中都有兩個(gè)隊(duì)相互比賽過，問至少要進(jìn)行多少場比賽？【題說】第三屆（1969年）全蘇數(shù)學(xué)奧林匹克九年級題．【解】把20個(gè)隊(duì)分成兩個(gè)組，各有k個(gè)隊(duì)和20-k個(gè)隊(duì)，使每個(gè)組中的所有隊(duì)之間都比賽一次，這樣比賽的次數(shù)為由于任何三個(gè)隊(duì)中至少有兩個(gè)隊(duì)在同一組，而同一組的兩個(gè)隊(duì)都相互比賽過，所以至少需90場比賽，當(dāng)兩組各有10個(gè)隊(duì)時(shí)，恰好比賽90場。E2-040·網(wǎng)球協(xié)會為全體會員排定名次，最強(qiáng)的為第1號，其次為第2號等等．已知，在名次相差高于2的運(yùn)動員比賽時(shí)，總是高名次的運(yùn)動員獲勝．在由1024名最強(qiáng)的選手參加的循環(huán)賽中（即參加者為1號選手到1024號選手），按奧林匹克規(guī)則進(jìn)行：每一輪比賽的每對選手都由抽簽決定，勝者進(jìn)入下一輪．因此，每一輪比賽后參賽者將減少一半．這樣一來，第十輪后將決出勝者．試問，勝者的最大號碼是多少？【題說】第七屆（1973年）全蘇數(shù)學(xué)奧林匹克九年級題．【解】勝者的最大號碼是20號．因?yàn)椴挥?jì)比他強(qiáng)的選手時(shí)，k號選手只可能輸給k+1號和k+2號選手，所以，勝1號選手的號數(shù)至多為3，勝3號的號數(shù)至多為5，…．因此，冠軍的號數(shù)不可能低于1+2×10=21．但在冠軍號數(shù)為21時(shí)，第一輪比賽后應(yīng)淘汰1號和2號選手，他們分別敗于3號和4號選手；在第二輪中3號，4號被淘汰，5號、6號取勝，等等．依此類推，直到第九輪，在該輪比賽中19號和20號選手應(yīng)分別戰(zhàn)勝17號和18號選手，這樣，21號選手將不會進(jìn)入決賽．下面舉一個(gè)第20號選手獲勝的賽例，全體參賽者按每組512人分成兩組，第一組中包括第19號，20號及其他510名較弱的選手，該組的比賽使得第20號選手獲勝（顯然，這是可能的）．在第二組中有1號至18號選手及其余較弱的選手，在該組比賽中使第18號選手獲勝，這只要出現(xiàn)前面所說的情況，是可以作到的：第一輪中3號，4號分別戰(zhàn)勝1號，2號；第二輪中5號，6號戰(zhàn)勝3號，4號等等；到第八輪，第17號和18號選手戰(zhàn)勝15號和16號選手，在第九輪中18號選手戰(zhàn)勝17號選手．這樣，參加決賽的將是第20號選手和第18號選手，于是，20號選手可能獲勝．

E2-041·把一個(gè)8×8的棋盤（指國際象棋棋盤）剪成p個(gè)矩形，但不能剪壞任何一格，而且這種剪法還必須滿足如下條件：（1）每一個(gè)矩形中白格和黑格的數(shù)目相等；（2）令ai是第i個(gè)矩形中的白格的個(gè)數(shù)，則a1＜a2＜…＜ap求出使上述剪法存在的p的最大可能值，同時(shí)對這個(gè)p求出所有可能的a1，a2，…，ap．【題說】1974年國際數(shù)學(xué)奧林匹克題．本題由保加利亞提供．由此可知p≤7．p=7時(shí)只有五種可能的組合：第一種組合不可能在棋盤上實(shí)現(xiàn)，因?yàn)槠灞P上剪出的矩形不可能是22格的，其他四種情況都是可以實(shí)現(xiàn)的，如上圖所示（圖中數(shù)字表示該塊含方格數(shù)）．E2－042·某區(qū)學(xué)生若干人參加數(shù)學(xué)競賽，每個(gè)學(xué)生得分都是整數(shù)，總分為8250，前三名的分?jǐn)?shù)是88、85、80，最低是30分，得同一分?jǐn)?shù)的學(xué)生都不超過3人．問至少有多少學(xué)生得分不低于60分（包括前三名）？【題說】1979年全國聯(lián)賽二試題．【解】除了前三名外，得分為30～79，總分為8250-（88+85+80）=7997．其中分?jǐn)?shù)為30～59的人至多（每種分?jǐn)?shù)三人），共得（30+31+…+59）×3=4005分，因此至少有7997-4005=3992分分配給60～79分的人．由于（79+78+…+61）×3=3990＜3992，所以60～79的人數(shù)至少為3×（79-61+1）+1=58．故得分不低于60分的學(xué)生總數(shù)為61人（包括前三名）．E2－043·一個(gè)團(tuán)體有1982人，在任何4人的小組中，至少有一人認(rèn)識其他3人，問在此團(tuán)體中，認(rèn)識其他所有人的最少人數(shù)是多少？【題說】第十一屆（1982年）美國數(shù)學(xué)奧林匹克題．【解】認(rèn)識可能是雙方的，也可能是單方的．1．假設(shè)認(rèn)識按雙向性理解，作一個(gè)有1982個(gè)點(diǎn)的圖G，每點(diǎn)代表一個(gè)人，若兩人彼此不認(rèn)識，就將相應(yīng)兩點(diǎn)連一條邊，認(rèn)識者不連．于是，我們的問題變?yōu)椋阂阎诖藞D中，每四點(diǎn)所成之子圖，至少有一孤立點(diǎn)，問圖中最少有多少個(gè)孤立點(diǎn)？設(shè)G中有邊AB．若又有邊CD連結(jié)另兩點(diǎn)C、D，則A、B、C、D四點(diǎn)所成子圖中無孤立點(diǎn)，矛盾．因此G中任一點(diǎn)或者是孤立點(diǎn)，或者與A或B相連．設(shè)點(diǎn)C與A相連，則對任一點(diǎn)D，由于A、B、C、D所成子圖中有孤立點(diǎn)，所以D不與A、B相連，從而（根據(jù)上面所證）D為G的孤立點(diǎn)．于是G中至多有A、B、C三點(diǎn)非孤立點(diǎn)，至少有1979個(gè)孤立點(diǎn)，即該團(tuán)體中至少有1979個(gè)人認(rèn)識其他所有人．2．若認(rèn)識是單向的，設(shè)1982人圍成一圓圈，每人皆不認(rèn)識其右鄰，但認(rèn)識其余的人．容易證明，任4人中都至少有一人認(rèn)識其他三人，但團(tuán)體中無一人認(rèn)識其他所有人，即認(rèn)識所有其他人的人數(shù)最少是0．

E2－044設(shè)S是邊長為100的正方形，L是在S內(nèi)自身不相交的折線段A0A1，A1A2，…，An-1An（A0≠A有兩點(diǎn)X、Y，它們之間的距離不大于1，沿折線L，它們之間的距離不小于198．【題說】第二十三屆（1982年）國際數(shù)學(xué)奧林匹克題6．【解】根據(jù)題設(shè)，對于正方形的頂點(diǎn)S1，S2，S3，S4，在折線L在沿L由A0到An時(shí)，不妨假定先經(jīng)過L1，并且在L2與L4中，先出現(xiàn)的是L2．將S1S4上的點(diǎn)分為兩類：如果Q在A0L2這一段，P在第一類，如果Q在L2An上，P在第二類．顯然S1在第一類，S2在第二類，所以兩類都是非空的，這兩類可以有公共點(diǎn)（原因見后）．如果P0是公共點(diǎn)，那么另一方面，從Q1沿著L到Q2必須經(jīng)過L2，而Q1到L2這段長≥以Q1、Q2之間的L的長≥198．Q1、Q2就是要求的點(diǎn)X、Y．最后來說明上面定義的兩個(gè)類的公共點(diǎn)P0是存在的．設(shè)在邊S1S4的從S1到S4的方向上，第一類的點(diǎn)最遠(yuǎn)能延伸到P0，從S4到S1的方

E2－045在平面上畫出n（n≥2）條直線，將平面分成若干個(gè)區(qū)域，其中一些區(qū)域上涂了顏色，并且任何兩個(gè)涂色的區(qū)域沒有相鄰的邊界．證明：涂色的區(qū)域數(shù)不超過（n2+n）/3．【題說】第十九屆（1985年）全蘇數(shù)學(xué)奧林匹克十年級題4．只有一個(gè)公共點(diǎn)的兩個(gè)區(qū)域，不認(rèn)為是有相鄰接的邊界．【證】如果所畫的直線