備戰2021年高中數學聯賽之歷年真題匯編(1981-2020)

專題30圖論與對策

施雷國氟題:

1.12020高中數學聯賽A卷(第02試)】給定凸20邊形P.用P的17條在內部不相交的對角線將P分割成18

個三角形,所得圖形稱為P的一個三角剖分圖.對P的任意一個三角剖分圖T,P的20條邊以及添加的17條對角線

均稱為7的邊.7的任意10條兩兩無公共端點的邊的集合稱為T的一個完美匹配.當T取遍尸的所有三角剖分圖時,

求T的完美匹配個數的最大值.

【答案】89

【解析】將20邊形換成2n邊形，考慮一般的問題.

對凸2〃邊形P的一條對角線，若其兩側各有奇數個P的頂點，稱其為奇弦，否則稱為偶弦.首先注意下述基本事實：

對P的任意三角剖分圖的完美匹配不含奇弦.(*)

如果完美匹配中有一條奇弦馬,因為7的一個完美匹配給出了P的頂點集的一個配對劃分，而e1兩側各有奇數個頂

點,故該完美匹配中必有7的另一條邊ez，端點分別在勺的兩側，乂尸是凸多邊形，故g與e2在P的內部相交，這與T

是三角剖分圖矛盾.

記f(T)為T的完美匹配的個數.設&=1,F2=2,對k>2,&+2=Fk+1+&提Fibonacci數列.

下面對n歸納證明:若7是凸2n邊形的任意一個三角剖分圖，則f(T)<Fn.

設P=AJA2…42n是凸2”邊形.從P的In條邊中選n條邊構成完美匹配，恰有兩種方法,…，或

4①，^4^5>>"2n-2^2n-l'42n4]

當〃=2時，凸四邊形P的三角剖分圖T沒有偶弦，因此T的完美匹配只能用P的邊，故f(T)=2=F2.

當〃=3時，凸六邊形P的三角剖分圖7至多有一條偶弦.若7沒有偶弦，同上可知f(T)=2.

若T含有偶弦，不妨設是①①，選用44的完美匹配是唯一的，

另兩條邊只能是424,4546,此時/'(T)=3.總之f(T)<3=F3.

結論在〃=2,3時成立.假設論4,且結論在小于〃時均成立.考慮凸2〃邊形P=ArA2…&?的一個三角剖分圖T.若T

沒有偶弦，則同上可知/(7)=2.

對于偶弦e,記e兩側中P的頂點個數的較小值為w(e).若T含有偶弦，取其中一條偶弦e使w(e)達到最小.

設w(e)=2k不妨設e為42n42k+i，則每個40=1,2,-,2k)不能引出偶弦.

事實上，假設44?是偶弦，若/G{2k+2,2k+3,-,2n一1},則從4?與e在P的內部相交,矛盾.

若jG{1,2,…,2k+l,2n}廁w(44)<2k,與w(e)的最小性矛盾.

又由(*)知完美匹配中沒有奇弦，故4,&，??,，4K只能與其相鄰頂點配對,特別地，4只能與%或42n配對?下面分兩

第1頁共42頁

種情況.

情形1:選用邊$4」4_2$.則必須選用邊4344，-，42/￡-142心注意到42/2〃+1的兩側分別有2y2幾-2卜-2個頂點，

2n-2/c-2>w{A2nA2k^i)=2k,而n>4,

因此2n-2k>6.在凸2，*2K邊形％=A2k+1A2k+2…42n上，7的邊給出了打的三角剖分圖A，在T中再選取，M條邊

0送2…enf,與…&k-i&k一起構成T的完美匹配，

當且僅當…en-k是A的完美匹配.故情形1中的7■的完美匹配個數等于/(A).

情形2：選用邊442n?則必須選用邊443,…，42/2從1-在凸2〃-2h2邊形「2=4"242"3…4n-i中構造如下的三

角剖分圖72：對2k+2<i<j<2n-1,若線段44?是T的邊，則也將其作為72的邊,由于這些邊在內部互不相交，因

此可再適當地添加一些P2的對角線，得到一個P2的三角剖分圖72?它包含了7的所有在頂點42k+2，&k+3,…，&n-l

之間的邊.因此每個包含邊公腦1M24，…，(》?』的7的完美匹配，其余的邊必定是72的完美匹配?故情形2中的

T的完美匹配個數不超過八72).

由歸納假設得f(Tl)<Fn-k,fg<Fn-k-1，

結合上面兩種情形以及應1,有f(T)4/(A)+/(T2)<Fn_k+&_"_I=Fn_k+1<Fn.

下面說明等號可以成立.考慮凸2"邊形44???&n的三角剖分圖分：

?^n+3^n-^n^n+2-

重復前面的論證過程,「(4)=2,/(zl3)=3.對>4,考慮偶弦4nA3.

情形1,用必慶，由于在凸2”-2邊形44…&m中的三角剖分圖恰是4—1，此時有/'(4n-i)個T的完美匹配.

情形2,用442n，由于在凸2"-4邊形4名…42M-1中T的邊恰構成三角剖分圖4-2,不用添加任何對角線，故這一情

形下7"的完美匹配個數恰為/'(4_2).

從而對“為,有f(4)=f(4吁1)+f(4.2).

由數學歸納法即得f(4)=4,.結論得證.

因此，對凸20邊形只/(T)的最大值等于Fl。=89.

2.12019高中數學聯賽B卷(第02試)】將一個凸2019邊形的每條邊任意染為紅、黃、藍三種顏色之一，每種

顏色的邊各673條.證明:可作這個凸2019邊形的2016條在內部互不相交的對角線將其剖分成2017個三角形，并

將所作的每條對角線也染為紅、黃、藍三種顏色之一，使得每個三角形的三條邊或者顏色全部相同或者顏色互不

相同.

【答案】證明見解析

【解析】我們對""歸納證明加強的命題:如果將凸〃邊形的邊染為三種顏色mb,c,并且三種顏色的邊均至少

有一條，那么可作滿足要求的三角形剖分.

當，=5時，若三種顏色的邊數為1、1、3,由對稱性，只需考慮如下兩種情形，分別可作圖①中所示的三角形剖

第2頁共42頁

分.

圖①

若三種顏色的邊數為1、2、2,由對稱性，只需考慮如卜三種情形，分別可作圖②中所示的三角形剖分.

圖②

假設結論對〃（，侖5）成立，考慮”+1的情形，將凸"+1邊形記為4出…力n+r

情形1：有兩種顏色的邊各只有一條.不妨設。、6色邊各只有一條.由于〃+1次，故存在連續兩條邊均為c色，不妨

設是4"4”+14.作對角線&4n，并將414n染為C色,則三角形44+14的三邊全部同色.此時凸n邊形&&…A.的

三種顏色的邊均至少有一條，由歸納假設，可對其作符合要求的三角形剖分.

情形2:某種顏色的邊只有一條，其余顏色的邊均至少兩條.不妨設。色邊只有一條，于是可以選擇兩條相鄰邊均

不是?色，不妨設414n+1,4+141均不是?色，作對角線44，則414有唯一的染色方式，使得三角形44+14的

三邊全部同色或互不同色.此時凸n邊形…4n的三種顏色的邊均至少有一條，由歸納假設，可對其作符合要

求的三角形剖分.

情形3：每種顏色的邊均至少兩條.作對角線44,,則44n有唯一的染色方式，使得三角形的三邊全部同

色或互不同色.此時凸〃邊形414…4的三種顏色的邊均至少有一條由歸納假設，可對其作符合要求的三角形剖

分.

綜合以上3種情形，可知〃+1的情形下結論也成立.

由數學歸納法，結論獲證.

3.12017高中數學聯賽A卷（第02試）】將33x33方格紙中每個小方格染三種顏色之一，使得每種顏色的小方

格的個數相等.若相鄰兩個小方格的顏色不同，則稱它們的公共邊為“分隔邊”試求分隔邊條數的最小值.

【答案】56

【解析】記分隔邊的條數為L首先，將方格紙按如圖分成三個區域，分別染成三種顏色，粗線上均為分隔邊，此

時共有56條分隔邊,即L=56.

第3頁共42頁

II

11

II

下面證明LN56.將方格紙的行從上至下依次記為4,4,???433,列從左至右依次記為a,B2,…，％3?行4中方格出現

的顏色個數記為n(4),列瓦中方格出現的顏色個數記為n(Bi).三種顏色分別記為Q,C2，C3.

對于一種顏色cP設Mg)是含有q色方格的行數與列數之和.

1,若Ai行含有q色方格

記6(4,q)=

0,否則,

類似地定義6(即引.于是

33

33X13

W【n(4)+n(Bj)]=>56(4同+6(%。)]

i=]六]

t=l

=WjTG+c,)]=S/=1n(q).

由于染g色的方格有3332=363個，設含有q色方格的行有a個，列有〃個，則盯色的方格一定在這。行和。列

的交叉方格中，因此出侖363,

從而n(q)=Q+b>2>fab>2、363>38,

故n(q)>39,;=1,2,3①

由于在行4?中有以4)種顏色的方格，因此至少有n(4)-1條分隔邊.

同理在列號中，至少有幾(鳥)-1條分隔邊.于是

3333

L>{[九(4)-1]+W1n(/)-I〕

1=1i=l

=￡名[以4)+n(Ff)]-66②

=Zj=i九(。)-66③

下面分兩種情形討論.

情形1有一行或一列全部方格同色不妨設有一行全為G色，從而方格紙的33列中均含有q色的方格，由于J色方

格有363個，故至少有11行中含有q色方格，于是n(q)》11+33=44.

由①、③及④即得L>九(R)+n(c2)+n(c3)-66)44+39+39-66=56.

第4頁共42頁

情形2沒有一行也沒有一列的全部方格同色.則對任意10433,均有n(4)>2,71(瓦)》2.

從而由②知L>X匿1皿(4)+n(Bj-66>33x4-66=66>56.

綜上所述，分隔邊條數的最小值等于56.

4.【2016高中數學聯賽(第02試)】給定空間中10個點，其中任意四點不在一個平面上將某些點之間用線段相

連，若得到的圖形中沒有三角形也沒有空間四邊形，試確定所連線段數目的最大值.

【答案】所求邊數的最大值為15

【解析】以這10個點為頂點，所連線段為邊，得到一個10階簡單圖G.我們證明G的邊數不超過15.

設G的頂點為巧,w，…，%0,共有A條邊，用deg(%)表示頂點匕的度.若deg"。43對用1,2,…，10都成立，

則％=)巴deg(%)<|x10x3=15.

假設存在匕滿足deg(%)》4.不妨設de或%)=n>4,且也與以，…,“n+i均相鄰?于是與，…,%+i之間沒有邊，否

則就形成三角形.

所以巧,外，…，/i+i之間恰有n條邊.

對每個/(“+20410),牛至多與“2，%,…，Vn+l中的一個頂點相鄰(否則設馬，與%,%(24S<t(幾+1)相鄰，

則%,%、町%就對應了一個空間四邊形的四個頂點這與題設條件矛盾.)，

從而“2,…，%i+i與"n+2,…，%o之間的邊數至多10—(n+l)=9—n條.

在外+2,…，匕。這9—W個頂點之間，由于沒有三角形，由托蘭定理，至多［7］條邊?

如圖給出的圖共有15條邊，且滿足要求.綜上所述，所求邊數的最大值為15.

5.12011高中數學聯賽(第02試)】設A是一個3x9的方格表，在每一個小方格內各填一個正整數.稱A中的一

個機x〃(19E3,19W9)方格表為“好矩形；若它的所有數的和為10的倍數.稱A中的一個1x1的小方格為“壞格；

若它不包含于任何一個“好矩形”.求A中“壞格”個數的最大值.

【答案】25

【解析】首先證明A中“壞格”不多于25個.

用反證法.假設結論不成立，則方格表A中至多有1個小方格不是“壞格”由表格的對稱性，不妨假設此時第1行都

是“壞格”.

第5頁共42頁

設方格表A第i列從上到下填的數依次為即瓦,q,i=l,2........9.

記品=?=1q，7k=￡3(d+q)(fc=0,1,2,---,9),這里So=To=O.

我們證明：三組數So,Si，…,59,To,J,…,79及So+ToS+T”…,S9+1都是模10的完全剩余系.

事實上，假如存在n,0<m<n<9,使5三5n(mod10),

則￡%n+l%=S”—Sm三0(mod10),

即第1行的第"計1列至第"列組成一個“好矩形與第1行都是“壞格”矛盾.

又假如存在〃?，"，叱，"<悵9,使加三Tn(modlO),

則于小+曲+Q)=Tn-Tm=O(mod10),

即第2行至第3行、笫"計1列至第n列組成一個“好矩形；從而至少有2個小方格不是“壞格；矛盾.

類似地,也不存在m,n,0<m<n<9,使隊+Tm=Sn+Tn(mod10),

因此上述結論得證.

故X2=oSk=流7丁卜=4=o(Sk+4)=0+l+2+-+9=5(mod10).

所以4=o(Sk+TQ=k=oS〃+式為晨=5+5=0(mod10),矛盾.

故假設不成立.即“壞格”不可能多于25個.

另一方面，構造如下一個3x9的方格表，可驗證每個不填10的小方格都是“壞格；此時有25個“壞格”.

1112111110

111111111

1111011112

綜上所述,“壞格”個數的最大值是25.

6.【2010高中數學聯賽(第02試)】一種密碼鎖的密碼設置是在正〃邊形a&…力"的每個頂點處賦值0和1兩

個數中的一個，同時在每個頂點處涂染紅、藍兩種顏色之一，使得任意相鄰的兩個頂點的數字或顏色中至少有一

個相同.問：該種密碼鎖共有多少種不同的密碼設置？

【答案】答案見解析

【解析】對于該種密碼鎖的一種密碼設置，如果相鄰2個頂點上所賦值的數字不同，在它們所在的邊上標上小

如果顏色不同，則標上從如果數字和顏色都相同，則標上c.于是對于給定的點4上的設置(共有4種)，按照邊

上的字母可以依次確定點心,43,…，力”上的設置?為了使得最終回到4時的設置與初始時相同，標有。和〃的邊都

是偶數條.所以這種密碼鎖的所有不同的密碼設置方法數等于在邊上標記小b,c,使得標有a和萬的邊都是偶數

條的方法數的4倍.

第6頁共42頁

設標有a的邊有2,條，04i(目，

標有b的邊有〃條，0《/<［嚶卜

選取2/條邊標記a的有Cf種方法，在余下的邊中取出寺條邊標記b的有——種方法，其余的邊標記C.

由乘法原理，此時共有比仁京2i種標記方法?對，，/求和，密碼鎖的所有不同的密碼設置方法數為

4①

i=0

這里我們約定C&=1.

--2i]

當”為奇數時n-2i>0,此時S2C匕i=2nTi②

乙刃=0

代入式①中，得4,12I2j=45”=25"?i2n-2i)

vn-2i

/=0—HO=i=0

1=0

〉a2"-〃+〉C*2n-k(-l)fc=(2+l)n+(2-l)n=3n+1,

右k=o-k=0

當〃為偶數時，若則式②仍然成立;

若i=p則正〃邊形的所有邊都標記a,此時只有1種標記方法.

于是，當“為偶數時，所有不同的密碼設置的方法數為

fnl

=4X(1+2且1(*2ndi))=2+4^2(C?2n=3n+3.

綜上所述，這種密碼鎖的所有不同的密碼設置方法數是：當〃為奇數時，有3"+1種；當”為偶數時，有3"+3種.

7.12009高中數學聯賽(第02試)】在非負數構成的3x9數表

XX

/XllX12x13x14xlsx16x171819

XXXXX

Pj2122%23%24252627X28X29

\X31X32X33X34X35X36X37%38X39

中每行的數互不相同，前六列中每列的三個數之和為1,X17=X28=X39=0,&7/37,與8，X38，/9/29均大于

如果P的前三列構成的數表

/Xllx12X13\

XX

S=j2122%23

Vsi%32X33)

滿足下面的性質(O)：對于數表P中的任意一列，，(k=12…,9)均存在某個01,2,3}使得%認《3=

\x3k/

min{%i，x⑵々3}①

求證：

第7頁共42頁

(。最小值以=mn[xiltxi2txi3],i=1,2,3一定取自數表S的不同列.

/xlk*\/xllx12xlk*\

(ii)存在數表P中唯一的一列,k*。1,2,3使得3x3數表S'=x21x22x2k-仍然具有性質(O).

\x3k*/\x31x32x3ka/

【答案】證明見解析

【解析】(1)假設最小值%=min{?x⑵項3}。=1,2,3),

不是取自數表S的不同列.則存在一列不含任何u,

不妨設七.H項2123),由于數表P中同一行中的任何兩個元素都不等，于是以〈項2?=123),

另一方面，由于數表S具有性質(。)，在式①中取上2,則存在某個%€{1,2,3}使得修。24七。?矛盾.

(2)由抽屜原理知min{xii，%i2}，min{%2i，%22}，min{x3i，%32}中至少有兩個值取在同.列?

不妨設min{%2i，%22}=X22，min(x3i，X32)=%32，

由前面的結論知數表S的第一列一定含有某個如所以只能是%I1=%,

同樣，第二列中也必含某個〃/，=1,2.不妨設%22=〃2，『是〃3=》33.

X12%13

即處是數表S中的對角線上的數字S=(%21X22X23

\X31X32X33

記”{1,2,???,9},

令集合/={fceM\xik>mn{xilfxi2}ti=1,3),

顯然/={kEM\xlk>xllfx3k>x32}f且1,2,3g/.

因為%18，%38>1>XllfX32>所以8G7.故/00.

于是存在攵*￡/使得》2公=max{x2k|fcG/},顯然,1*32,3.

/xllx12xlk*\

下面證明3X3數表S'=%21%22具有性質(。)

\x31X32X3k*/

從上面的選法可知*=mn(xi1,xi2，xik-}=min{Xi1,xi2)。=L3),

這說明％>min{xn,x12}>unx3k*>min{x31,x32}>%，

又由S滿足性質(O),在式①中取七K,推得X2k*4的，

于是達=min{x21,x22,x2fc,}=x2k>

下證對任意的存在某個工1,2,3使得小?%ik，

假若不然，則％塊>mn{xiltxi2},i=1,3且％2k>%2k*-

%

這與X*的最大性矛盾.因此，數表V滿足性質(。).

第8頁共42頁

/xllx12xlk\

下證唯一性.設有k￡M使得數表S=IX21X22%2k)具有性質(O).

\^31%32X3kJ

不失一般性，我們假定〃i=min{xlpx12,Xi3)=

u

2=min{x21，%22,%23)=%22'“3=ITlin{X31,X32,X33}=X33,②

x32VX311由于％32V%31，％22V尤21及情形(1)，

有%=mn{xllfx12fxlk}=xn,

又由情形(1)知：或者(a)?3=min{%3i，%32，%3〃}=%3k，

或者(b)%=min{%2i，*22,％2/c}=

如果情形(a)成立，由數表S具有性質(。)，則喋=min{%u，%i2，Xnc}=%ii，

&=min{x21,x22,x2fc}=x22,u3=n\\n[x31fx32>x3k}=x3k③

由數表S滿足性質(O),則對于3￡M至少存在一個，￡{1,2,3}使得用>勺3,

又由式②與知IZ]—V%13,“2=無22<%23，

所以只能有。3=X3k>第33，

同樣由數表S滿足性質(。)，可推得X33)工3上，于是七3,

即數表S=Sf

如果情形S)成立，則Qi=mn{xlltx12,xlk}=%n，

u2=min{x21/x22,x2/c}=刖，u3=min{%3i，%32，%3k}=x32④

由數表*滿足性質(。)，對于A*WM,存在某個U1,2,3使得

由及式②和④知》償*>%n=Ui，X3k=>X32=

于是只能有%2k，<“2=X?k，

類似地，由S，滿足性質(O)及kSM可推得%2k4也=X2k,

從而k*=k.

8.12007高中數學聯賽(第02試)】如圖，在7x8的長方形棋盤的2個小方格的中心點各放1個棋子.如果2個

棋子所在的小方格共邊或共頂點，那么稱這2個棋子相連.現從這56個棋子中取出一些，使得棋盤上剩下的棋子，

沒有5個在一條直線(橫、豎、斜方向)上依次相連.問最少取出多少個棋子才可能滿足要求?并說明理由.

12345678

第9頁共42頁

【答案】11

【解析】最少要取出II個機子，才可能滿足要求.其原因如下：

如果1個方格在第，?行第j列，則記這個方格為(i,./).

第1步，證明若任取10個棋子，則余下的棋子必有1個五子連珠，即5個棋子在1條直線(橫、豎、斜方向)上依

次相連.用反證法.假設可取出10個棋子，使余下的棋子沒有一個五子連珠.如圖，在每一行的前五格中必須各取出

1個棋子，后三列的前五格中也必須各取出1個棋子.這樣，10個被取出的棋子不會分布在右下角的陰影部分同理，

由對稱性，也不會分布在其他角上的陰影部分.第1,2行必在每行取出1個，且只能分布在(1,4),(1,5),(2,

4),(2,5)這些方格.同理，(6,4),(6,5),(7,4),(7,5)這些方格上至少要取出2個棋子.在第1,2,3歹每

列至少要取出1個棋子，分布在(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(5,1),(5,2),(5,3)所在區

域，同理(3,6),(3,7),(3,8),(4,6),(4,7),(4,8),(5,6),(5,7),(5,8)所在區域內至少要取出3個棋

子這樣，在這些區域內至少已取出10個棋子因此，在中心陰影區域內不能取出棋子.由于①，②，③，④這4個

棋子至多被取出2個，從而，從斜的方向看必有五子連珠了矛盾.

第2步，構造1種取法，共取走II個棋子，余下的棋子沒有五子連珠.如圖2,只要取出有標號位置的棋子，則

余下的棋子不可能五子連珠.

9.【2002高中數學聯賽(第02試)】在世界杯足球賽前，F國教練為了考察公，這七名隊員，準備讓

他們在三場訓練比賽(每場90分鐘)都上場假設在比賽的任何時刻，這些隊員中有且僅有一人在場上，并且

42,4,4每人上場的總時間(以分鐘為單位)均被7整除，45,4,47每人上場的總時間(以分鐘為單位)均被13

第10頁共42頁

整除如果每場換人次數不限，那么按每名隊員上場的總時間計算，共有多少種不同的情況.

【答案】52244

【解析】設第i名隊員上場的時間為即分鐘(i=l,2,7),

問題即求不定方程%+血+…+丫7=270①

在條件7|爸(14，44)且13|勺(54/47)下的正整數解的組數.

若(右,?，…，不)是滿足條件①的一組正整數解，則應有E3Xj=7m,&=5鼠=13n(m,n6N+),

于是m,〃是不定方程7m+13n=270②

在條件m>4且n>3下的一組正整數解.

由于7(m-4)+13(n-3)=203,

令M=m-4,n'=n—3,有7m'+13n'=203③

所以，求式②滿足條件m>4,n>3的正整數解等價于求式③的非負整數解.

易觀察到7X2+13x(-1)=1,故有7x406+13x(-203)=203,

即=406,他=一203是式③的整數特解，

從而式③的整數同解為加=406-13k,n'=-203+7k(fceZ),

令m'>0,n>0.解得26<<31,

取629,30,31,得到式③滿足條件的三組非負整數解

(mr=29(mr=16(mr=3

t=0'1nz=7'Ui'=14'

從而得到式②滿足條件的三組正整數解

(m=33(m=20(m=7

(九=3'In=10?ln=17f

(1)當m=33,n=3時，顯然會=x6=x7=13僅有一種可能.

又設々=7%(i=l,2,3,4),

于是由不定方程%+y2+y3+y4=33有c宏1=島=4960組正整數解.

可知此時式①有滿足條件的4960組正整數解.

(2)當m=20,n=10時，設項=7%(i=1,2,3,4),巧=7力。=5,6,7),

由%+>2+%+%=20有C：9組正整數解，

以及丁5+y6+y7=10有點解組正整數解.

可知此時式①有滿足條件的盤9番=34884組正整數解.

(3)在m=7,n=17時，設％=7%(i=1,2,3,4),X)=7y,(j=5,6,7),

由yi+y2+y3+y4=7與y5+y6+/=17分別有C熊器組正整數解可知此時式①有滿足條件的ac”2400

第11頁共42頁

組正整數解.

綜上，式①滿足條件的正整數解的組數為：

C32++Ci6C1=4960+34884+2400=42244.

10.12001高中數學聯賽(第02試)】將邊長為正整數機，〃的矩形劃分成若干邊長均為正整數的正方形，每個

正方形的邊均平行于矩行的相應邊，試求這些正方形邊長之和的最小值.

Di-------------------|C

【答案】答案見解析

【解析】記所求最小值為?)>可以證明=m+n—(m,n)①

其中("7,〃)表示於和〃的最大公約數，事實上，不妨設"侖:"，則：

(1)關于m歸納，可以證明存在一種合乎題意的分法，使所得正方形邊長之和恰為rn+n-(m,n),

當切=1時，命題顯然成立

假設當，於人時，結論成立(后1).當m=A+l時，

若”=61,則命題顯然成立.若"4+1,從矩形A8C/)中切去正方形A&D1D,得到矩形A/CDi，有一種分法使得

所得正方形邊長之和恰為D,

得到矩m-n+n—(m-n,n)=m—(m,n),

于是原矩形ABCD有一種分法使得所得正方形邊長之和為rn+n-(m,n).

D,-----------------，c

n

AmA,B

(2)關于M歸納可以證明式①成立.

當〃日時，由于顯然=rn+九一

假設當m<k時，對任意\<n<m有=rn+n—(m,n),

若m=k+\,當n=k+1時，顯然/(m,九)=k4-l=rn+n-(m,n),

當IS?女，設矩形ABC。按要求分成了〃個正方形，其邊長分別為的,右，???，。□?

不妨%>a2>…>%，顯然由=/或%<n.

若四<n,則在AD與BC之間的與AD平行的任一直線至少穿過兩個分成的正方形(或其邊界).

于是%+02+…+%不小于AB與CD之和.

第12頁共42頁

所以由4-a24----FQp>2m>rn4-n—(m,n).

若％=",則一個邊長分別為小一〃和〃的矩形可按題目要求分成邊長分別為的,…,密的正方形，

由歸納假設。2-----h%>m—n+n—(m—n,n)=rn—(m,n),

從而為+a2-1-----FQp>rn+n—(m,n).

于是當rn=k+1時>rn+n—(m,n),

再由情形(1)可知f(m,n)=rn+n-(mfri).

11.12000高中數學聯賽(第02試)】有〃個人，已知他們中的任意兩個人至多通電話一次，他們中的任意〃一2

個人之間通電話的總次數相等，都是3&次，其中％是自然數，求〃的所有可能值.

【答案】答案見解析

【解析】顯在,論5.不妨設〃個人是4,42,…Mn，

又設A?通話的次數為與％之間通話的次數為兒〃14i,j<n.

k

有磯+嗎一Aitj=|E?=ims-3=C①

c為常數，且!</,j<n.

由上式知|g-mJ=|(7nt+ms)-(m7+ms)|=\Ais-AjiS\<1(1<i,j,s<n),

HP|mf-m;|<1(1<i,j<n),

設m,=max{ms,1<s<n),嗎=min{ms,1<s<n},

有叫-77ly<1,

當nii—m/=l時，對任意的$r八),l<5<n,均有

m

(i+ms-A,s)一(嗎+rns-乙戶)=1一Cks-乙s)=0?

即4,s-%,s=1，

有As=1，入i，s=0(sHi,j,1<s<n).

所以強>n—2,m;<1.

可知成一m,》九一2-1》2,矛盾，

故叫—嗎=0,即〃?式1%9)恒為常數.

又由式①知兒)=0或；Ijj=1.

當；I?」=0時，有ms=0,1<s<n與已知條件矛盾.

所以：n(n-1)-(2n-3)=3fe,E|J(n-2)(n-3)=2x3k,

設幾一2=2x3"i,n-3=3&>fc2),有2x3右一33=1,

所以3%(2x33f2-1)=1,有33=1,2x3勺一心-1=1.

第13頁共42頁

所以ki=0,k2=0,但這與fel矛盾.

所以設n-2=3%,n—3=2x3。(比>fc2+1),有3%—2x3牝=1,

同上作法，有心=l,k2=0,n=5.

當5個人中每2個人之間都通話一次時，其中任意3個人之間通話的總次數是3'次.故n=5為所求.

12.11999高中數學聯賽(第02試)】給定正整數小已知用克數都是正整數的4塊祛碼和一臺天平可以稱出質

量為1,2,3....咫的所有物品.

⑴求々的最小值加)；

(2)當且僅當n取什么值時，上述.火”)塊祛碼的組成方式是唯一確定的?并證明你的結論.

【答案】(1)f(n)=巾(二二)；(2)答案見解析.

【解析】(1)設這女塊祛碼的質量數分別為由,做，…，以，且14的《&《融，/WZ,14i4k.

因為天平兩端都可以放祛碼，故可稱質量為E3陽即項日一1,0,1).

若利用這攵塊祛碼可以稱出質量為1,2,〃，由對稱性易知也含有0,—1,—2,…，一〃,

即{比1英即々€{-1,0,1}}={0,±L…，土九},

所以2n+1=|{0,±1,…，±n}|<|{￡3/auxtE{-1,0,1}}}|43"，即n<-y-.

?am-Qm_i

設—--V?14---(zn)1,mEZ)t

則k>m,且&=加時，可取臼=1,◎2=3,…，=3巾-1.

由數的三進制表示可知，對任意0<P<3m-1都有p=

其中以40,1,2}.則「一中=濯1%31-鄧］31=￡巴小一1)31,

令石=y(-1>有芍e{-1,0,1},

故對一切一等<n(=二的整數1,都有2=工乜1%3?-1,其中xd{-l,0.1).

由于714寧，

因此對一切-n4I<n的整數1,也有上述表示.

綜上，可知k的最小值/'(")=m<n422一)

(2)⑺當一〈九4號」時，由情形(1)可知1,3,…，3巾-1,3m就是一種祛碼的組成方式.

下面相應證明13…,3m-\3m-1也是一種方式.

3lf1-1

若14IV2由情形(1)可知，=E胃1陽3(%j6(—1,0,1)),

第14頁共42頁

則有1=￡%1々3'-1+0(3"*-1)，

當生！<Un<之士時，有吐！<，+i《九〈竺士,

2222

由情形⑴可知/+1=其中々e{-1,0,1).

所以知4n+i=1.(否則，《2213(-1-1=等一1矛盾).

i1m

JUiJ/=SiliXi3-+l-(3-l),

所以當71H三二時，#〃)塊祛碼的組成方式不唯一.

(〃)當n=T二時，,火〃)=小塊硅碼的組成方式是唯一的，即4=3"i(1<i<m),

若對每個一等<I<等都有2=￡隘即修(X；e{-1,0,1)).

即{理€{-1,0.1})2{0,±1,-,±^}.

由于左邊的集合中至多有3"'個元素.故必有{￡色1看見黑￡[-1,0,1})={。,±1,…，土當斗

?jzn1?tini

從而，對每個It有-----4I《---都可以唯一的表示為/=X之其中％iE{-1,0,1).

所以￡%心=等，

有虎式々+1)&=溫Xiat+at=￡21Xiat+言之

令%=題+1，有/w{0,1,2},

由上可知，對每個04/43巾一1,都可以唯一的表示為/=￡曙1%田(%W{0,1,2}).

特別地，易知14”1<0.2<…VQm，

用歸納法證明%?=3，-T(l<i<m).

當i=l時，易知￡壽1%心中最小的正整數是內，故％=1.

假設當l<i<p時Qj=3，T,

由于EL%七=3—(%E{0,1,2})就是數的三進制表示，

易知它們正好是0,1,…，3P-1.

故Qp+1應是除上述表示外{￡*1丫104％E{0,1,2}}中最小的數，

因此知+i=3P.

綜合情形⑺與(")可知，當且僅當幾=早時，上述人")塊祛碼的組成方式是唯一確定的.

13.【1997高中數學聯賽(第02試)】在100x25的長方形表格中每一格填入一個非負實數，第，?行第7列中填入

的數為Mi=l,2,100；j=l,2，…，25)(表1).然后將表1沒列中的數按由大到小的次序從上到下重新排列為

第15頁共42頁

x[lj>X%>…》x[00j(j=1,2,…,25)(表2).

求最小的自然數A使得只要表1中填入的數滿足l(i=1,2,-100),

^—125

則當立人時，在表2中就能保證〉x[j<1(i=1,2,…100)成立.

表1

xl,lXl,2…Xl,25

X2,lX2,2…X2,25

X1OO,1X100,2X100,25

表2

Xl,lXl,2…后,25

X2,lX2,2…X2,25

………

X100,lX100,2…注00,25

【答案】97

【解析】A的最小值為97.

(0(40-1)+1<i<47)

⑴取知以其余的。(/=1,2,…25),

這時=0+24X或(i=1,2,-,100),滿足題設條件,

￡(l4i《96)

重排后有=0=1,2,…,25)

0(974i《100)

25i

x'ij=25x—>1(l《i496),故《的最小值不小于97.

Z/=i'24

(2)首先證明：表1中必有一行(設為第/?行)的所有數X"i，X"2，%r,25必在重排后所得表2的前97行中都出現.

事實上，若上述結論不成立.則表1的第一行中至少有一個數不在表2的前97行中出現，即表2的前97行中至多

共有表1中100x24=2400個數.這與表2的前97行共有個數25x97=2425矛盾.

其次，由重排要求知表2中每列的數從上到下是由大到小排列的，故當297時,*j4溫力《xrJ(j=1,2,…,25),

故當近97時W：(2；：產刀(1，

綜合情形(1)與(2)知k的最小值為97.

第16頁共42頁

14.【1996高中數學聯賽（第02試）】有〃（論6）個人聚會,已知:

（1）每人至少同其中冏個人互相認識；

（2）對于其中任意同個人，或者其中有2個人相識，或者余下的人中有2個人相識.

證明：這N個人中必有3個人兩兩相識.

【答案】證明見解析

【解析】假設這“個人中無3人彼此認識不妨設a,b是這〃個人中互相認識的2個人，可由假設推出余下的〃

一2個人中，無1個人與a,b都認識因此，至少有2［皆個不同的人，其中每個人或與a相識，或與6相識.

當〃為偶數時，由討論可知，這〃個人中恰有一半人與a相識，而另一半人則與匕相識.所以，由題設可推出在某

一半人中必含2個相互認識的人，這與假設矛盾.

當”為奇數時n=2冏+1,

若這"個人中每人都與。或萬相識，與假設矛盾.

不然，若存在c,他不認識。和江則〃個人中除了c之外的2［耳個人中必有一半是與a互相認識的，另一半是

與。互相認識的，且所有與。相認識的人互不認識，所有與。相認識的人也互不認識此時，假設有8個人同a,c

都認識，1個人與b,c都認識.可由題設推出但1且這人個人構成與c相識的人的全部.

因而k+c》［胃.

可設行1,由于，仝6，有Q2.

因此，可設?同江。都認識，仇與仇和“，，?都認識因為〃個人中同al相識的人至少為冏個他們中除c?外，同

”都相識，故?必與"，灰之一相識，不妨設與加相識，則力和c是彼此相識的人，與假設矛盾，綜上，

命題為真.

15.11995高中數學聯賽（第02試）】將平面上的每個點都以紅，藍兩色之一著色.證明：存在這樣兩個相似的三

角形，它們的相似比為1995,并且每一個三角形的三個頂點同色.

【答案】證明見解析

【解析】首先證明平面上一定存在三頂點同色的直角三角形.如圖2,在平面上任作直線I,則/上必有兩點同色，

設此兩點為8',C.過"，C分