數(shù)學(xué)奧林匹克題解E組合數(shù)學(xué) E2計數(shù)和離散最值071-080)

1、E2071 設(shè)n和k是正整數(shù)，S是平面上n個點的集合，滿足：（1）S中任何三點不共線；（2）對S中的每一個點P，S中至少存在k個點與P距離相等【題說】 第三十屆（1989年）國際數(shù)學(xué)奧林匹克題3，本題由荷蘭提供條件（1）可以取消【證】 以S中的兩個點為端點的線段稱為“好線段”另一方面，以S中任一點P為圓心，可以作一個圓，圓上至少有k計算在內(nèi)）從而至少有條弦是好線段 E2072 學(xué)校舉辦足球循環(huán)賽，每個參賽隊都與其他隊各賽一場，勝一場積2分，平一場積1分，負(fù)一場積0分，已知僅有一個隊積分最多，但他勝的場數(shù)最少，問至少有幾隊參賽，才有可能這樣？【題說】 第十六屆（1990年）全俄數(shù)學(xué)奧林

2、匹克九年級題5【解】 稱積分最多的為冠軍，設(shè)冠軍勝n場，平m場，則他共積2n+m分，由題設(shè)，其余各隊勝的場數(shù)不少于n+1，即積分不少于2（n+1）由2n+m2n+2得m3從而有隊踢過平局，他們的積分不少于2（n+1）+1，由2n+m2n+3，得m4冠軍隊至少勝1場，否則，它的積分不多于S-1（S是參賽的隊數(shù)）其余隊的積分少于S-1，于是所有參賽隊積分之和少于S（S-1）而每賽一場，雙方積分之和總是2分，因此所有隊積分之和應(yīng)是2·S（S-1）/2=S（S-1），矛盾這樣，m4，n1，因此冠軍隊比賽場數(shù)不少于5，參賽隊數(shù)（包括冠軍隊）不少于6下面的比賽積分表表明，有6個隊（分別用A、B、

3、C、D、E、F表示）參賽且滿足題設(shè)要求的比賽結(jié)果因此至少6隊參賽 E2073 設(shè)n3考慮在同一圓周上的2n-1個互不相同的點所成的集合E將E中一部分點染成黑色，其余的點不染顏色如果至少有一對黑點，以它們?yōu)槎它c的兩條弧中有一條的內(nèi)部（不包含端點）恰含E中n個點，則稱這種染色方式為好的如果將E中k個點染黑的每一種染色方式都是好的，求k的最小值【題說】 第三十一屆（1990年）國際數(shù)學(xué)奧林匹克題2本題由捷克提供【解】 將E中的點依次記為1，2，3，2n-1，并將點i與i+（n-1）用一條邊相連（我們約定j+（2n-1）·k，kZ，表示同一個點j）這樣得到一個圖GG的每個點的次數(shù)均

4、為2（即與兩個點相連），并且相差為3的兩個點與同一點相連由于G的每個點的次數(shù)為2，G由一個或幾個圈組成在3 2n-1時，1， 2，2n-1中每一點j都可以表示成3k的形式（即方程3xj（mod2n-1）有解），因此圖G是一個長為2n-1的圈在這圈上可以取出n-1個互不相鄰的點，而且至多可以取出n-1個互不相鄰的點為共可取出n-2個點互不相鄰綜上所述，在3 2n-1時，mink=n在3|2n-1時，mink=n-1 E2074 地面上有10只小鳥在啄食，其中任意5只鳥中至少有4只在一個圓周上，問有鳥最多的一個圓周上最少有幾只鳥？【題說】 1991年中國數(shù)學(xué)奧林匹克題3【解】 9只鳥在同

5、一圓周上，1只鳥不在這圓周上，滿足題目條件設(shè)有鳥最多的圓上至少有l(wèi)只鳥，則419首先證明，l4由l9，必有4只鳥不在同一圓周上，過其中每3只作一個圓，共得4個圓，其余6只鳥中的每一只與上述4只鳥組成5元組，因而這只鳥必在（上述4個圓中）某一個圓上，6只鳥中必有2只在同一個圓上，從而這個圓上至少有5只鳥其次，如果5l8，設(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 E2075 給定空間中的9個

6、點，其中任何4點都不共面，在每一對點都連著一條線段試求出最小的n值，使得將其中任意n條線段中的每一條任意地染為紅、藍二色之一，在這n條線段的集合中都必然包含有一個各邊同色的三角形【題說】 第三十三屆（1992年）國際數(shù)學(xué)奧林匹克題3，本題由中國提供色的線段至多3條若點A1引出不染色的線段，去掉A1及所引出的線段，若剩下的圖中，還有點A2引出不染色的線段，去掉A2及所引出的線段依此進行，由于不染色的線段至多3條，所以至多去掉3個頂點（及從它們引出的線段），即有6個點，每兩點之間的連線染上紅色及藍色熟知這里存在一個同色三角形如圖表明染色的邊少于33條時，未必有同色三角形（不染色的邊19、28、37

7、、46沒有畫出），其中1、9與2、8間的虛線表明12、18、92、98均為虛線，5與4、6間的實線表明54、56均為實線等等因此n=33 E2076 10人到書店買書，如果已知（1）每人都買了三本書；（2）任二人所買書中都至少有一本相同，問最受歡迎的書（購買人數(shù)最多者）最少有幾人購得？為什么？【題說】 1993年中國數(shù)學(xué)奧林匹克（第八屆數(shù)學(xué)冬令營）題5【解】 設(shè)最受歡迎的書有k人購買每人買3本書，共買30本書若k4，由于4 30，不可能每種書均被4人購買設(shè)第一個人購的書為a、b、c，并且買a的人3個，則與第一個人的公共圖書為a的，不超過2人；為b或c的，均不超過3人從而總?cè)藬?shù)1+2+

8、3+3=9，矛盾！因此k5現(xiàn)給出一種k=5的購書法：因此，被購買人數(shù)最多的一種書，最少有5人購買 E2077 某市發(fā)出車牌號碼均由6個數(shù)字（從0到9）組成，但要求任意2個車牌至少有2位不同（如車牌038471和030471不能同時使用）試求該市最多能發(fā)出多少個不同車牌？并證明【題說】 第三屆（1993年）澳門數(shù)學(xué)奧林匹克第三輪題5【證】 最多發(fā)出100000個事實上，若發(fā)出了100001個車牌，則由抽屜原則知至少有10001個號碼首位相同，同理這10001個號碼中至少有1001個號碼第2位亦相同，依此類推，至少有2個號碼前5位均相同，違反規(guī)定另一方面，可發(fā)出100000個車牌并符合規(guī)

9、定；號碼的后5位任意填寫但沒有兩個完全相同（有105種填法），首位則為后5位數(shù)字之和的個位數(shù)字若有2個號碼后5位數(shù)字僅有1位不同，則其首位也必不同所以這100000個號碼符合規(guī)定 E2078 若干個學(xué)校參加網(wǎng)球比賽，同一學(xué)校之間的選手不比賽，每兩個學(xué)校的每兩個選手都要比賽一場在兩個男孩或兩個女孩之間進行的比賽稱為單打；一個男孩和一個女孩之間的比賽稱為混合單打男孩的人數(shù)與女孩的人數(shù)至多相差1單打的場數(shù)和混合單打的場數(shù)也至多相差1問有奇數(shù)個選手的學(xué)校至多有幾個？【題說】 第二十五屆（1993）加拿大數(shù)學(xué)奧林匹克題4【解】 設(shè)有n個學(xué)校，第i個學(xué)校派出xi個男選手、yi個女選手，i=1，2

10、，n由題意，有場由題意，有1+2=3即在（xi-yi）（i=1，2，n）中至多只有三項不為零，而且這n項都應(yīng)為1這就是說，至多3個學(xué)校的人數(shù)xi+yi為奇數(shù)如果只有3個學(xué)校，其中2個各派1名男孩，另1個學(xué)校派1名女孩，那么題目中的條件全滿足，而奇數(shù)個選手的學(xué)校恰好3個 E2079 用水平和垂直的直線網(wǎng)把一塊正方形黑板分成邊長為1的n2個小方格，試問對于怎樣的最大自然數(shù)n，一定可以選出n個小方格，使得任意面積不小于n的矩形中都至少包含有上面選出的一個小方格？（矩形的邊是沿著直線網(wǎng)的）【題說】 第十九屆（1993年）全俄數(shù)學(xué)奧林匹克十年級二試題7【解】 顯然，如果選出n個小方格滿足問題的

11、條件，那么，在每一行、每一列都恰有一個選定的小方格右圖表明n=7時，有滿足要求的選法設(shè)n7，稱第一個方格被選定的行為A若A是第一行，則稱第二、三行為B、C若A是第n行，則稱第n-1、n-2行為B、C若A不是第一行與第n行，則稱與A相鄰的兩行為B，C兩個長方形中都不含有A、B兩行中選定的小方格而C這行中只能有一個選定的小方格，所以這兩個長方形中必定有一個是不包含有選定的小方格的因此，所求的最大值為n=7【注】 n=6時，符合問題要求的選法不存在 E2080 設(shè)n、kN且kn并設(shè)S是含有n個互異實數(shù)的集合設(shè)T是所有形如x1+x2+xk的實數(shù)的集合，其中x1，x2，xk是S中的k個互異元素

12、求證T至少有k（n-k）+1個互異的元素【題說】 第三十四屆（1993年）IMO預(yù)選題本題由愛爾蘭提供【證】 n=k時結(jié)論顯然假設(shè)命題對n-1（k）成立考慮由s1s2sn組成的n元集S由歸納假設(shè)，對S0=s2，s3，sn存在k（n-1-k）+1個形如x1+x2+xk的互不相等的數(shù)，其中x1，x2，xk是S0中不同元素顯然                    s1+s2+sks1+s2+sk-1+sk+1&

13、#160;                                             s1+s2+sk-2+sk+sk+1  

14、                                            s1+s2+s4+sk+1