競賽數學中的組合數學問題

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

利用映射來解決計數問題，就是通過建立集合A與另一集合B之間的映射，把對集合A的計數轉移到對集合B的計數。實現這種轉移的關鍵是：（1）選擇適當的便于計數的集合；（2）建立集合間的映射關系。

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

（1）若f為單射，則。

（2）若f為滿射，則。

（3）若f為一一映射，則?！纠}分析】

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

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

顯然棋盤內橫線與豎線的交點有個，所以，共有種不同取法。

說明：一般地，集合到集合的所有映射的個數為。

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

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

說明在某種映射下，兩個集合元素間一一對應，該映射即為一一映射，所以對于明顯的一一映射只須指出兩集合間的一一對應關系，就可運用對應原理。

例3·求m元方程的正整數解的組數。

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

顯然①

且一一對應，所以，映射是一一映射。

因為，滿足①的數組有個，所以所求方程解的組數為。

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

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

例4·設為A的三元子集，若滿足為A的“好子集”，求A的“好子集”的個數。

解：令

作映射。

f是到上的一一映射。事實上，當時，，那么即。

另一方面，若，則，即。

于是由對應原理，，即A的“好子集”有個。

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

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

例6·已知，，并且①②

求的個數。

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

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

（1）；

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

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

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

因此，符合題目條件的有序數組的個數為

例8已知數列滿足

。

對每一個整數，求滿足條件

的下標n的個數。

解將滿足的自然數n用二進制表示為，這里，可以證明

①

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

反復利用①式可知

②

上式右邊為k個+1或-1的和。所以，當k為奇數時，②的右邊為奇數，不會等于0，這表明，當k為奇數時，滿足條件的下標n的個數為0。

當k為偶數時，若，則②式右邊恰有個+1，個-1。

設，n的二進制表示為，，②式確定了一個A到B的映射：。

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

故滿足，且的下標n的個數為B中恰有個-1的有序數組的個數，即。

綜上所述，當為奇數時，滿足條件的下標n的個數為0；當k為偶數時，滿足條件的下標n的個數為。

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

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

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

（1）顯然，（1）有4個整數解：（0，0），（199，199），（199，-199），（389，0）．當y≠0、±199時，|y|與199互素，故由（1）知：|x-199|、|y|、199是一組基本勾股數．由勾股數基本公式知，存在二正整數m、n使199=m2+n2．由于平方數≡0或1（mod4），所以m2+n2≡0，1或2（mod4），但199=4×49+3≡3（mod4）矛盾．因此當y≠0、±199時，（1）無整數解．綜上所述，在（1）圓周上的整點只有4個．E2-033·一個7×7的棋盤的2個方格著黃色，其余的方格著綠色．如果一種著色法可從另一種著色法經過在棋盤的平面中的旋轉而得到，那么這兩種著色法看做同一種．可能有多少種不同的著色法？【題說】第十四屆（1996年）美國數學邀請賽題．如果這一對方格關于棋盤中心中心對稱，那么旋轉后可與另一對方不關于棋盤中心中心對稱，那么繞中心旋轉90°、180°、270°，分別與另外三對方格重合，經過旋轉也只可能與這三對重合．因此不同的E2-034·兩個正數的調和平均是它們的倒數的算術平均的倒數．有多少個正整數的有序對（x，y），使得x＜y且x與y的調和平均等于620？【題說】第十四屆（1996年）美國數學邀請賽題．E2-035·有多少對正整數x、y滿足x≤y，并且最大公約數（x，y）=5！，最小公倍數[x，y]=50?。俊绢}說】第二十九屆（1997年）加拿大數學奧林匹克題．【解】設x=5！a，y=5！b，a、b為互質的自然數，則[x，y]=5！[a，b]=5！ab．所以其中a1，…，a15都是正整數．由于a、b互質，所以每一因數pa（p∈{2，3，5，…，47}）或者是a的因數，或者是b的因數，兩種情況恰好出現一種，而a≤b，E2-036·平面上給定五個點，這些點兩兩之間的連線互不平行，又不垂直，也不重合，從任何一點開始，向其余四個點兩兩之間的聯線作垂線，如果不計已知的五個點，所有這些垂線間的交點數最多是多少？【題說】第六屆（1964年）國際數學奧林匹克題5．本題由羅馬尼亞提供．再因每三點構成一個三角形，這個三角形的三條高共點，應從中減所以，交點最多有E2-037·某委員會開了40次會議，每次有10人出席，而且委員會任意兩個成員都未在一起出席過一次以上的會議，證明：該委員會成員一定多于60．【題說】1965年全俄數學奧林匹克十年級題．會議，可以組成不同的兩人組共有45×40=1800個，但由60人最多只定多于60．次會議，與他同出席會議的人都不相同，從而人數≥7×9=63＞0，矛盾。E2-038·在平面上給出n（≥3）個點，其中任兩點的距離最大為d．距離為d的兩點間的線段稱為這組點的直徑．證明：直徑的數目至多n條．【題說】1965年國際數學奧林匹克題．本題由波蘭提供．【證】假定直徑多于n條．如果從某個點出發(fā)的直徑少于兩條，我們就把這點除去，剩下的n-1個點至少有n條直徑，顯然n-1≥3，故不妨假設從每一點都至少引出兩條直徑．因為直徑數目比點多，而每條直徑都連結兩個點，所以至少有一點A引出三條直徑AB、AC、AD，每兩條直徑的夾角不超過60°，否則另一端的距離大于d．不妨設AD在AB與AC之間，因此，⊙（A，d）（以A為圓心，d為半徑的圓）、⊙（B，d）、⊙（C，d）的公共部分覆蓋了整個點集，而與D距離為d的點只有A點一個（圖中，以DG＜CG=d．同理可證D到除A外的其它點距離＜d）．即D點只引出一條直徑，矛盾！故命題成立。E2-039·有20個隊參加全國足球冠軍決賽．為了使任何三個隊中都有兩個隊相互比賽過，問至少要進行多少場比賽？【題說】第三屆（1969年）全蘇數學奧林匹克九年級題．【解】把20個隊分成兩個組，各有k個隊和20-k個隊，使每個組中的所有隊之間都比賽一次，這樣比賽的次數為由于任何三個隊中至少有兩個隊在同一組，而同一組的兩個隊都相互比賽過，所以至少需90場比賽，當兩組各有10個隊時，恰好比賽90場。E2-040·網球協(xié)會為全體會員排定名次，最強的為第1號，其次為第2號等等．已知，在名次相差高于2的運動員比賽時，總是高名次的運動員獲勝．在由1024名最強的選手參加的循環(huán)賽中（即參加者為1號選手到1024號選手），按奧林匹克規(guī)則進行：每一輪比賽的每對選手都由抽簽決定，勝者進入下一輪．因此，每一輪比賽后參賽者將減少一半．這樣一來，第十輪后將決出勝者．試問，勝者的最大號碼是多少？【題說】第七屆（1973年）全蘇數學奧林匹克九年級題．【解】勝者的最大號碼是20號．因為不計比他強的選手時，k號選手只可能輸給k+1號和k+2號選手，所以，勝1號選手的號數至多為3，勝3號的號數至多為5，…．因此，冠軍的號數不可能低于1+2×10=21．但在冠軍號數為21時，第一輪比賽后應淘汰1號和2號選手，他們分別敗于3號和4號選手；在第二輪中3號，4號被淘汰，5號、6號取勝，等等．依此類推，直到第九輪，在該輪比賽中19號和20號選手應分別戰(zhàn)勝17號和18號選手，這樣，21號選手將不會進入決賽．下面舉一個第20號選手獲勝的賽例，全體參賽者按每組512人分成兩組，第一組中包括第19號，20號及其他510名較弱的選手，該組的比賽使得第20號選手獲勝（顯然，這是可能的）．在第二組中有1號至18號選手及其余較弱的選手，在該組比賽中使第18號選手獲勝，這只要出現前面所說的情況，是可以作到的：第一輪中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·把一個8×8的棋盤（指國際象棋棋盤）剪成p個矩形，但不能剪壞任何一格，而且這種剪法還必須滿足如下條件：（1）每一個矩形中白格和黑格的數目相等；（2）令ai是第i個矩形中的白格的個數，則a1＜a2＜…＜ap求出使上述剪法存在的p的最大可能值，同時對這個p求出所有可能的a1，a2，…，ap．【題說】1974年國際數學奧林匹克題．本題由保加利亞提供．由此可知p≤7．p=7時只有五種可能的組合：第一種組合不可能在棋盤上實現，因為棋盤上剪出的矩形不可能是22格的，其他四種情況都是可以實現的，如上圖所示（圖中數字表示該塊含方格數）．E2－042·某區(qū)學生若干人參加數學競賽，每個學生得分都是整數，總分為8250，前三名的分數是88、85、80，最低是30分，得同一分數的學生都不超過3人．問至少有多少學生得分不低于60分（包括前三名）？【題說】1979年全國聯賽二試題．【解】除了前三名外，得分為30～79，總分為8250-（88+85+80）=7997．其中分數為30～59的人至多（每種分數三人），共得（30+31+…+59）×3=4005分，因此至少有7997-4005=3992分分配給60～79分的人．由于（79+78+…+61）×3=3990＜3992，所以60～79的人數至少為3×（79-61+1）+1=58．故得分不低于60分的學生總數為61人（包括前三名）．E2－043·一個團體有1982人，在任何4人的小組中，至少有一人認識其他3人，問在此團體中，認識其他所有人的最少人數是多少？【題說】第十一屆（1982年）美國數學奧林匹克題．【解】認識可能是雙方的，也可能是單方的．1．假設認識按雙向性理解，作一個有1982個點的圖G，每點代表一個人，若兩人彼此不認識，就將相應兩點連一條邊，認識者不連．于是，我們的問題變?yōu)椋阂阎诖藞D中，每四點所成之子圖，至少有一孤立點，問圖中最少有多少個孤立點？設G中有邊AB．若又有邊CD連結另兩點C、D，則A、B、C、D四點所成子圖中無孤立點，矛盾．因此G中任一點或者是孤立點，或者與A或B相連．設點C與A相連，則對任一點D，由于A、B、C、D所成子圖中有孤立點，所以D不與A、B相連，從而（根據上面所證）D為G的孤立點．于是G中至多有A、B、C三點非孤立點，至少有1979個孤立點，即該團體中至少有1979個人認識其他所有人．2．若認識是單向的，設1982人圍成一圓圈，每人皆不認識其右鄰，但認識其余的人．容易證明，任4人中都至少有一人認識其他三人，但團體中無一人認識其他所有人，即認識所有其他人的人數最少是0．

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

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