高中數(shù)學(xué)聯(lián)賽2015-2021年真題分類(lèi)匯編-排列組合與圖論【含解析】

高中數(shù)學(xué)聯(lián)賽2015-2021年真題分類(lèi)匯編

專題40排列組合與圖論第三緝

1.【2020年吉林預(yù)賽】若(1+x+Myo]。的展開(kāi)式為劭++a2/4-----F?2020%202°，

則劭+?3+°6+…+02019=()

A.3670B,3669c,31009D,31100

【答案】C

【解析】令x=1,得+%+a?+…+<12020=31010;①

令x=a)(a)=-1+ji),貝U

a?3=1且a)2+a>+1=0,

23a,202

a0+與3+a2a>+a3a)4-----Fa2020°=°；②

令x=a>2,得

Cig+a】e?++&3口6+…+azozO3'。'。=。，(§)

1010

①+②+③得3(劭+a3+a64-…+a20i9)=3

=劭+。3+念+…+02019=31009.

2.[2019年貴州預(yù)賽】在RtAABC中,NB=9(r,AB=15,BC=20.則頂點(diǎn)B與斜邊各點(diǎn)的連線中(含邊AB,BC)

長(zhǎng)度為整數(shù)的線段的條數(shù)是()

A.9B.10C.llD.12

【答案】D

【解析】因?yàn)轫旤c(diǎn)B到斜邊AC的距離12,所以頂點(diǎn)B與斜邊各點(diǎn)的連線中長(zhǎng)度為13、14、15的線段各有

兩條,長(zhǎng)度為12、16、17、18、19、20的線段各有一條，故滿足條件的線段共有12條.

3.[2019年吉林預(yù)賽】將1,2,3,--,9這9個(gè)數(shù)全部填入下圖的3x3方格內(nèi)，每個(gè)格內(nèi)填一個(gè)數(shù)，則使得每行中

的數(shù)從左至右遞增，每列中的數(shù)從上至下遞減的不同填法共有()種

(A)12(B)24(C)42(D)48

【答案】c

【解析】1只能填在左下角格內(nèi),9只能填在右上角格內(nèi).中心格內(nèi)的數(shù)字可能為4,5,6,現(xiàn)分3種情

形討論：

(1)若中心格內(nèi)填4,則2和3只能填在與1相鄰的兩個(gè)位置，易知此時(shí)共有房盤(pán)=12種填法：

(2)若中心格內(nèi)填6,與上述情形類(lèi)似，共有12種填法

(3)若中心格內(nèi)填5,則與1相鄰的兩個(gè)位置可能填寫(xiě)2和3或者2和4,若填寫(xiě)2和3,則4有兩個(gè)位置可以選

擇，此時(shí)共有/6瑪=12種填法；若填寫(xiě)2和4,則3只能填在與2相鄰的位置,此時(shí)共有朗瑪=6種填法.

綜合上述情形，表格共有12+12+12+6=42種填法.

4.【2017年四川預(yù)賽】在(x+y+z＞的展開(kāi)式中，所有形如/yaz.a,/,eN)的項(xiàng)的系數(shù)之和是()

(A)112(B)448(C)1792(D)14336

【答案】C

【解析】提示：因?yàn)?x+y+z)8=淺=0或迪-氣丫+2)匕故所有形如產(chǎn)丫。2/(1/eN)的項(xiàng)的系數(shù)之和為

若x26=1792.

5.[2017年黑龍江預(yù)賽】形如45132這樣的數(shù)稱為“波浪數(shù)”，即十位數(shù)字,千位數(shù)字均比與它們各自相鄰的數(shù)

字大，則由1、2,3、4、5可構(gòu)成數(shù)字不重復(fù)的五位“波浪數(shù)”個(gè)數(shù)為()

(A)20(B)18(C)16(D)ll

【答案】C

【解析】提示:分兩類(lèi)，

第一類(lèi):千位和十位是5和4,則有掰用，

第二類(lèi)千位和十位是5和3,則有掰鹿.

所以總共有12+4=16種.

6.[2017年貴州預(yù)賽】將1,2,…,9這九個(gè)數(shù)字填在如圖所示的九個(gè)空格中,要求每一行從左到右，每一列從上

到下分別依次增大.當(dāng)5固定在圖中中央位置時(shí)，則填寫(xiě)空格的方法種數(shù)為()

(A)12(B)15(C)16(D)18

【答案】D

【解析】提示：由題意知，左上角空格只能填1,右下角空格只能填9,

第一行例)可填1,2,3;1,2,4;1,3,4.其中每一種情況對(duì)應(yīng)第三行(列)可填6,7,9;6,8,9;7,8,9.

故所有填法種數(shù)為6x3=18.

故選C.

7.[2016年遼寧預(yù)賽】將2、3、4、6、8、9、12、15共八個(gè)數(shù)排成一行，使得任意相鄰兩個(gè)數(shù)的最大公約

數(shù)均大于1.則所有可能的排法共有()種

A.720B.1014C.576D.1296

【答案】D

【解析】

先將八個(gè)數(shù)分成三組：

1(2,4,8),11(3,9,15),111(6,12)由I組中與H組中的數(shù)無(wú)公因子，知滿足條件的排列必為：

⑴取出6、12兩數(shù)以后，剩余數(shù)分成三部分排列(依次)1、II、I或II、I、此時(shí)，這六個(gè)數(shù)的排列有

2x3!x3!x2=144種.而6、12放在不同部分相交的地方有兩種不同的放法，共有2x144=288種

⑵取出6、12兩數(shù)以后，剩余數(shù)分成兩部分排列I、II或II、I,此時(shí)，這六個(gè)數(shù)有2x3!x3!種排列方式，而6、12

若全部在I組與II組的交界處，有兩種排法，否則，只有一個(gè)在交界處，另一個(gè)位置有六種選法，共有2x3!x3!x

(2+2x6)=1008.

故所求的排法數(shù)為1008+288=1296.

8.[2016年湖南預(yù)賽】在某次乒乓球單打比賽中，原計(jì)劃每?jī)擅x手各比賽一場(chǎng)，但有三名選手各比賽兩

場(chǎng)之后就退出了，這樣全部比賽只進(jìn)行了50場(chǎng).則上述三名選手之間比賽的場(chǎng)數(shù)為()

A.0B.1C.2D.3

【答案】B

【解析】

試題分析：設(shè)一共有n個(gè)選手，故總場(chǎng)次鬣.3+6-x=⑴-號(hào)=旬+6一%=50,其中x為上述3名選手之間

比賽的場(chǎng)數(shù)，則X=m-3,）_44,經(jīng)驗(yàn)證，當(dāng)n=13時(shí)，x=l.

考點(diǎn)：排列組合.

9.[2015年四川預(yù)賽】已知n為正整數(shù)，二項(xiàng)式+或的展開(kāi)式中含有一的項(xiàng)，則n的最小值為（）.

A.4B.5C.6D.7

【答案】C

【解析】

注意到，所求二項(xiàng)式展開(kāi)式的通項(xiàng)公式為〃+1=。（公尸-（點(diǎn)丫=Crx2n-5r

由2n—5r=7（reN）,知當(dāng)r=l時(shí)，n有最小值6.

10.【2021年廣西預(yù)賽】某校n名同學(xué)通過(guò)選拔進(jìn)入學(xué)校的數(shù)學(xué)討論班，在一次討論班上他們討論A、B和

C三個(gè)問(wèn)題.已知壽位同學(xué)都和班里的其他所有同學(xué)討論了其中的一個(gè)問(wèn)題.每?jī)晌煌瑢W(xué)只討論一個(gè)問(wèn)題.若

至少有3名同學(xué)互相之間討論的是同一個(gè)問(wèn)題，求n的最小值，并給出證明.

【答案】n的最小值為17.證明見(jiàn)解析

【解析】n的最小值為17.

設(shè)所求的最小值為m.

（1）先考慮般=17的情形.將17名同學(xué)表示為由,a?，…,a17.

因?yàn)?>5，根據(jù)抽屈原理知的與其他16名同學(xué)中至少有6人討論的是同一個(gè)問(wèn)題，

不妨設(shè)的與…，討論的是問(wèn)題4.

若這6人中有2個(gè)人（不妨是（X2和）討論的是問(wèn)題4,

則由以2和。3這3名同學(xué)互相之間討論的是問(wèn)題4

否則，問(wèn)題轉(zhuǎn)化為這6名同學(xué)之間只討論問(wèn)題B或C的情形.

下面證明至少有3名同學(xué)互相討論的是同一個(gè)問(wèn)題.

因?yàn)閨>2，根據(jù)抽屜原理知a?與其他5名同學(xué)中至少有3人（不妨是。3，。4和。5）討論的是同一個(gè)問(wèn)題，不

妨設(shè)所討論的是問(wèn)題B.

若這3人中有2人（不妨是（13和）討論的是問(wèn)題B，則、。3和這3名同學(xué)互相之間討論的是問(wèn)題B.

否則。3，。4和討論的是問(wèn)題C.

因此，m<17.

（2）當(dāng)n=16時(shí)，考慮二進(jìn)制下的集合G={0000,0001,,一,1111}，集合中每一個(gè)數(shù)表示一名同學(xué)。對(duì)集合

中的元素施以“按位加”（+）運(yùn)算,即不考慮進(jìn)位,同位相同則為0,同位相異則1.例如:1010+1100=0110.

設(shè):

Ki={1100,0011,1001,1110,1000),

V2={1010,0101,0110,1101,0100},

V3={0001,0010,0111,1011,1111).

若%,yeG.易知x+y€G.FOx+y€匕(i=1,2,3)表示同學(xué)x和同學(xué)y討論第i個(gè)問(wèn)題；

用xG匕(i=1,2,3)表示同學(xué)0000與同學(xué)x討論第i個(gè)問(wèn)題.

按照上述規(guī)定，沒(méi)有3位同學(xué)互相之間討論同一個(gè)問(wèn)題.

因此m>17.

綜上所述，m=17，即n的最小值為17.

11.12020高中數(shù)學(xué)聯(lián)賽A卷(第02試)】給定凸20邊形P.用P的17條在內(nèi)部不相交的對(duì)角線將「分割

成18個(gè)三角形,所得圖形稱為P的一個(gè)三角剖分圖.對(duì)P的任意一個(gè)三角剖分圖T,P的20條邊以及添加的17

條對(duì)角線均稱為T(mén)的邊7的任意10條兩兩無(wú)公共端點(diǎn)的邊的集合稱為T(mén)的一個(gè)完美匹配.當(dāng)T取遍P的所

有三角剖分圖時(shí)，求T的完美匹配個(gè)數(shù)的最大值.

【答案】89

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

對(duì)凸2n邊形P的一條對(duì)角線，若其兩側(cè)各有奇數(shù)個(gè)P的頂點(diǎn)，稱其為奇弦，否則稱為偶弦.首先注意下述基本事

實(shí)：

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

如果完美匹配中有一條奇弦e1,因?yàn)門(mén)的一個(gè)完美匹配給出了P的頂點(diǎn)集的一個(gè)配對(duì)劃分，而ei兩側(cè)各有奇數(shù)

個(gè)頂點(diǎn)，故該完美匹配中必有7"的另一條邊02,端點(diǎn)分別在內(nèi)的兩側(cè)，又尸是凸多邊形，故e1與e2在尸的內(nèi)部相交,

這與T是三角剖分圖矛盾.

記/'(7)為7的完美匹配的個(gè)數(shù).設(shè)&=L尸2=2,對(duì)k>2,醍+2=Fk+i+是Fibonacci數(shù)列.

卜.面對(duì)"歸納證明:若T是凸2n邊形的任意一個(gè)三角剖分圖，則/(7)<Fn.

設(shè)P=&&…4”是凸2"邊形.從P的2〃條邊中選n條邊構(gòu)成完美匹配，恰有兩種方

法，4遇2,4344,…，At-iAi或色燈叢彳再，…，^2n-2^2n-l>^2n^l-

當(dāng)n=2時(shí)，凸四邊形P的三角剖分圖7沒(méi)有偶弦，因此T的完美匹配只能用P的邊，故/\7)=2=F2.

當(dāng)〃=3時(shí)，凸六邊形P的三角剖分圖T至多有一條偶弦.若7沒(méi)有偶弦，同上可知/(T)=2.

若丁含有偶弦，不妨設(shè)是選用的完美匹配是唯一的，

另兩條邊只能是&&，4546,此時(shí)f(T)=3.總之/(7)<3=F3.

結(jié)論在"=2,3時(shí)成立.假設(shè)論4,且結(jié)論在小于〃時(shí)均成立.考慮凸2n邊形P=A,A2…42n的一個(gè)三角剖分圖

r若T沒(méi)有偶弦,則同上可知/'(T)=2.

對(duì)于偶弦e,記e兩側(cè)中P的頂點(diǎn)個(gè)數(shù)的較小值為w(e).若7?含有偶弦，取其中一條偶弦e使w(e)達(dá)到最小.

設(shè)w(e)=2/c,不妨設(shè)e為42nA2k+i，則每個(gè)=1,2,…,2k)不能引出偶弦.

事實(shí)上，假設(shè)?是偶弦，若/6{2k+2,2k+3,-,2n-1},則4網(wǎng)?與e在P的內(nèi)部相交,矛盾.

若jG[1,2,—,2k+l,2n},則w(44j)<2/c,與w(e)的最小性矛盾.

又由(*)知完美匹配中沒(méi)有奇弦，故兒醺…，&k只能與其相鄰頂點(diǎn)配對(duì)，特別地，4只能與%或42n配對(duì).下面

分兩種情況.

情形1:選用邊$4」4_2$.則必須選用邊心44，“?，42142心注意到4/2丘1的兩側(cè)分別有湍271-24-2個(gè)頂

點(diǎn)，2n-2k-22w(&n&k+i)=2k,而n>4,

因此2n-2k>6.在凸2小2k邊形Pi=142k+2…42n上，了的邊給出了B的三角剖分圖A，在7中再選取〃/

條邊0送2-0f,與心①…々kT&k一起構(gòu)成T的完美匹配，

當(dāng)且僅當(dāng)02…e.T是口的完美匹配?故情形?中的丁的完美匹配個(gè)數(shù)等于/(n).

情形2：選用邊為A2n?則必須選用邊4A3,…,&〃2上+1?在凸2〃-2k-2邊形P2=4k+242k+3-M2n-l中構(gòu)造如下

的三角剖分圖△：對(duì)2k+2<i<j<2n—1,若線段44?是7的邊，則也將其作為72的邊,由于這些邊在內(nèi)部互

不相交，因此可再適當(dāng)?shù)靥砑右恍㏄2的對(duì)角線，得到一個(gè)22的三角剖分圖72，它包含了7的所有在頂點(diǎn)

&k+2,42k+3,…，42口-1之間的邊?因此每個(gè)包含邊42n4，&43,…，&k&k+i的T的完美匹配，其余的邊必定是

久的完美匹配?故情形2中的T的完美匹配個(gè)數(shù)不超過(guò)

由歸納假設(shè)得/(A)<Fn-k,/(T2)<F…T，

結(jié)合上面兩種情形以及Q1,有f(T)<fg+/(0)<Fn_k+叫-i=Fn-k+i<Fn.

下面說(shuō)明等號(hào)可以成立.考慮凸2〃邊形&&n的三角剖分圖為：

添加對(duì)角線424271，42睛3,43A2n-l，4271-14,4d&n-Z，…，An+3，n，，n4ri+2?

重復(fù)前面的論證過(guò)程，/'(/)=2J(Z13)=3.對(duì)>4,考慮偶弦41A3.

情形1,用4〃2,由于在凸2〃-2邊形①①…4m中的三角剖分圖恰是4t-i，此時(shí)有個(gè)7的完美匹配.

情形2,用&&"，山于在凸2"-4邊形4/…中7的邊恰構(gòu)成三角剖分圖4-2,不用添加任何對(duì)角線，故這

一情形下T的完美匹配個(gè)數(shù)恰為/(/_2).

從而對(duì)佗4,有/(4)=/(/_])+f(4_2).

由數(shù)學(xué)歸納法即得/(4)=?結(jié)論得證.

因此，對(duì)凸20邊形P,f(7)的最大值等于Fl。=89.

12.【2020年福建預(yù)賽】將一個(gè)2020x2020方格表的每個(gè)格染黑、白兩種顏色之一，滿足以下條件：方格表

中的任意一個(gè)格A,它所在的行與列的所有格中，與A異色的格多于與A同色的格.證明：染色后，方格表

中每行每列兩種顏色的格一樣多

【答案】證明見(jiàn)解析

【解析】對(duì)黑格與白格分別標(biāo)記為-1與1.對(duì)于任意的4i,)(2020)，設(shè)第i行各數(shù)之和為*,第/列

各數(shù)之和為弓，第i行與第j列交叉格中的數(shù)為a”，則位于第i行或第/列上的全部數(shù)之和為其+弓-四廠

由條件，知Sj+弓一a“與叼異號(hào).

則(1口(5(+tj—ctiy)W-l.

又昭=1，于是

k2。2。2。20

/Z.aijG+tj)

atj(si+t;)<0,<0.

J=1jl

2020

「2020

〉CL[j(S[+ty)

Zz=ij]

%12020—1202012020

V，22002V20002n

￡=1sf+Z/J"

&<2020

\1「202052020

則與("+切=7』n7n

ZW/=]2s:+W/=]4=0.

故對(duì)于任意的i、j,均有Sj—0,tj—0.

從而，每行、每列中的兩種顏色的格一樣多.

13.[2019年上海預(yù)賽】設(shè)n為正整數(shù)，稱〃X”的方格表7“的網(wǎng)格線的交點(diǎn)(共(n+1)2個(gè)交點(diǎn))為格點(diǎn).現(xiàn)將數(shù)

1,2,…,("+1)2分配給7；的所有格點(diǎn)，使不同的格點(diǎn)分到不同的數(shù)稱7；的一個(gè)1X1格子S為“好格”:若從S的某

個(gè)頂點(diǎn)起按逆時(shí)針?lè)较蜃x出的四個(gè)頂點(diǎn)上的數(shù)依次遞增(例如，圖中是將數(shù)1,2,…,9分配給T2的格點(diǎn)的一種方

式，其中,8、C為好格，而A、。不為好格)設(shè)T”中好格個(gè)數(shù)的最大值為式初

⑴求42)的值；

(2)求負(fù)〃)關(guān)于正整數(shù)〃的表達(dá)式

【答案】⑴3；⑵/⑺=［號(hào)斗

【解析】⑴

如圖所示，將T2的四個(gè)1X1格子(以下簡(jiǎn)稱“格子”)分別記為A、B、C、。，將九個(gè)格點(diǎn)上的數(shù)分別記為a力,..工

當(dāng)〃也…i,依次取為1,2,...,9時(shí),易驗(yàn)證8、C、。均為好格，這表明次2巨3.

現(xiàn)假設(shè)火2)=4,即存在一種數(shù)的分配方式，使A、B、C、。均為好格.

由對(duì)稱性,不妨設(shè)邊界上八個(gè)數(shù)a,h,...,h中的最小數(shù)為a或〃.此時(shí)，由A為好格，知要么a<b<i<h要么b<i<h<a.

故txi<h總成立.進(jìn)而，由B、C為好格，知必有i<f<g<h,b<c<d<i但此時(shí)d<i<f，與D為好格矛盾.

綜上32)=3.

(2)設(shè)7“的各格點(diǎn)的數(shù)已被分配好，此時(shí)，好格有k個(gè)稱格子的一條邊為一段“格線”.對(duì)7“的每段格線標(biāo)記一個(gè)

箭頭:若格線連接了兩個(gè)格點(diǎn)U、V(U上的數(shù)小于V上的數(shù))，則對(duì)格線UV標(biāo)上一個(gè)指向而順時(shí)針旋轉(zhuǎn)90。

后所得方向的箭頭.

稱一個(gè)格子S及S的一條邊UV所構(gòu)成的有序?qū)?S,UV)為一個(gè)“對(duì)子”:若UV上所標(biāo)的箭頭由S內(nèi)指向S外.

設(shè)對(duì)子總數(shù)為N.

一方面，每個(gè)格子S至少貢獻(xiàn)一個(gè)對(duì)子(否則，沿逆時(shí)針?lè)较蜃xS頂點(diǎn)上的數(shù)將永遠(yuǎn)遞減,矛盾)，而據(jù)好格的定義,

每個(gè)好格貢獻(xiàn)三個(gè)對(duì)子，于是N>3/c+1-(n2—/c)=2/c+n2.

另一方面Z的每段格線至多貢獻(xiàn)一個(gè)對(duì)子，且7；邊界上至少有一段格線標(biāo)有向內(nèi)的箭頭(否則，沿逆時(shí)針?lè)较?/p>

讀7“邊界上的數(shù)將永遠(yuǎn)遞增,矛盾)，從而，不貢獻(xiàn)對(duì)子.

注意到,7；的格線段數(shù)為2"("+1).于是,NW2”(”+1)-1.

綜合兩方面得2Hn2<2/?(n+l)-l,

即好格個(gè)數(shù)k4安二.

最后，對(duì)〃為奇數(shù)和〃為偶數(shù)的情況，分別如圖所示

將12…,（〃+1）2按粗線經(jīng)過(guò)的次序依次分配給所有格點(diǎn).對(duì)圖中標(biāo)有“▲”記號(hào)的每個(gè)格子，易驗(yàn)證，按被粗線經(jīng)

過(guò)的先后次序排列其4個(gè)頂點(diǎn)，恰為一種逆時(shí)針排列，因而，這些格子均為好格

左圖中好格數(shù)為等?n+亨=注二

右圖中好格數(shù)為受《+管一1）?1+.號(hào)二=件等二

其中,團(tuán)表示不超過(guò)實(shí)數(shù)x的最大整數(shù).

綜上/（“）=［號(hào)匚］

14.［2019年貴州預(yù)賽】我們知道,目前最常見(jiàn)的骰子是六面骰，它是一顆正立方體，上面分別有一到六個(gè)洞（或

數(shù)字），其相對(duì)兩面之?dāng)?shù)字和必為七.顯然，擲一次六面骰,只能產(chǎn)生六個(gè)數(shù)之一（正上面）。現(xiàn)欲要求你設(shè)計(jì)一個(gè)

“十進(jìn)制骰”，使其擲一次能產(chǎn)生0~9這十個(gè)數(shù)之一，而且每個(gè)數(shù)字產(chǎn)生的可能性一樣。請(qǐng)問(wèn):你能設(shè)計(jì)出這樣的

骰子嗎?若能，請(qǐng)寫(xiě)出你的設(shè)計(jì)方案;若不能，寫(xiě)出理由。

【答案】答案見(jiàn)解析

【解析】因?yàn)椴淮嬖谡骟w，所以直接產(chǎn)生“十進(jìn)制骰是辦不到的。但要實(shí)現(xiàn)“十進(jìn)制骰”的要求，這樣的骰子

是也是能設(shè)計(jì)的。即把骰子做成正二十面體,使其相對(duì)兩面標(biāo)同一個(gè)數(shù)字，這樣0~9這十個(gè)數(shù)字就均勻分布在

骰子上，當(dāng)擲一次骰子時(shí)，最上面出現(xiàn)的數(shù)字必然是0~9這十個(gè)數(shù)字之一，顯然，每個(gè)數(shù)字出現(xiàn)的可能性是一樣

的。故"個(gè)位骰''即為"二十面骰”

（注:答案不唯一，只要解答合情合理合法，均可適當(dāng)給分。就以二十面骰為例，將0~9中的每個(gè)數(shù)字放在相鄰兩

個(gè)面上或者任意兩個(gè)面上,也是可以的。）

15.12019高中數(shù)學(xué)聯(lián)賽B卷（第02試）】將一個(gè)凸2019邊形的每條邊任意染為紅、黃、藍(lán)三種顏色之一,

每種顏色的邊各673條.證明:可作這個(gè)凸2019邊形的2016條在內(nèi)部互不相交的對(duì)角線將其剖分成2017個(gè)

三角形，并將所作的每條對(duì)角線也染為紅、黃、藍(lán)三種顏色之一，使得每個(gè)三角形的三條邊或者顏色全部

相同或者顏色互不相同.

【答案】證明見(jiàn)解析

【解析】我們對(duì)〃云歸納證明加強(qiáng)的命題:如果將凸”邊形的邊染為三種顏色a,b,c,并且三種顏色的邊

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

當(dāng)〃=5時(shí)，若三種顏色的邊數(shù)為1、1、3,由對(duì)稱性，只需考慮如下兩種情形，分別可作圖①中所示的三角

形剖分.

圖①

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

圖②

假設(shè)結(jié)論對(duì)"（論5）成立，考慮n+1的情形，將凸n+1邊形記為4遇2-Al+i-

情形1：有兩種顏色的邊各只有一條.不妨設(shè)心〃色邊各只有一條.由于"+G6,故存在連續(xù)兩條功均為c色,

不妨設(shè)是4714n+14?作對(duì)角線44，并將44染為C色，則三角形4（+14的三邊全部同色?此時(shí)凸〃邊形

為乙…An的三種顏色的邊均至少有一條，由歸納假設(shè)，可對(duì)其作符合要求的三角形剖分.

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

邊均不是a色，不妨設(shè)(dt+iMn+iA均不是“色，作對(duì)角線人4，則必心有唯一的染色方式，使得三角

形A儲(chǔ)n+i&的三邊全部同色或互不同色?此時(shí)凸〃邊形&①…(的三種顏色的邊均至少有一條，由歸納假

設(shè)，可對(duì)其作符合要求的三角形剖分.

情形3：每種顏色的邊均至少兩條.作對(duì)角線則44n有唯一的染色方式，使得三角形4nAi+14的三邊

全部同色或互不同色.此時(shí)凸“邊形4遇2…4的三種顏色的邊均至少有一條由歸納假設(shè)，可對(duì)其作符合要求

的三角形剖分.

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

由數(shù)學(xué)歸納法，結(jié)論獲證.

16.【2018年安徽預(yù)賽】在正2018邊形的每?jī)蓚€(gè)頂點(diǎn)之間均連一條線段，并把每條線段染成紅色或藍(lán)色.求

此圖形中三邊顏色都相同的三角形的最小個(gè)數(shù).

【答案】N=2此oo9

【解析】

設(shè)N是此圖形中三邊顏色都相同的三角形數(shù)目，M是此圖形中三邊顏色不全相同的三角形數(shù)目，%是以第

i個(gè)頂點(diǎn)為端點(diǎn)的紅色線段數(shù)目，則有M+N=廢oi8，S/=l8x,(2017-Xi)=2M.當(dāng)且僅當(dāng)每個(gè)々=1008或

2

1009時(shí)，N取得最小值廢018-1009x1008=2C^009.

N=2盤(pán)oo9是可以取到的，例如：把線段i-i士Jmod2018(1<i<2018,1<;<504)染成紅色，其他

線段染成藍(lán)色.

17.[2018年浙江預(yù)賽】如圖所示將同心圓環(huán)均勻分成n(n>3)格.在內(nèi)環(huán)中固定數(shù)字1~〃.問(wèn)能否將數(shù)字1~"

填入外環(huán)格內(nèi)，使得外環(huán)旋轉(zhuǎn)任意格后有且僅有一個(gè)格中內(nèi)外環(huán)的數(shù)字相同？

【答案】見(jiàn)解析

【解析】

設(shè)對(duì)應(yīng)于內(nèi)環(huán)1,2,”的外環(huán)數(shù)字為八，h,i,?它是數(shù)字1,2,”的一個(gè)排列.對(duì)上1,2,

〃，記外環(huán)數(shù)字立在按順時(shí)針?lè)较蜣D(zhuǎn)動(dòng)人格時(shí)，和內(nèi)環(huán)數(shù)字相同，即

ik—k=ykmodn,fc=l,2,…，n.

根據(jù)題意，力，力，…，./〃應(yīng)是0,1,2,…，〃-1的排列.求和

2￡=式。一k)=a=1jimodn=(0+1+2H----卜(n—l))modn=|n(n—l)modn.

于是n必須是奇數(shù).

對(duì)于奇數(shù)〃，我們?nèi)”=〃，itn=n-m,(m=\,2,…，〃-1),可以驗(yàn)證九一k三/kmodn

jft=0,j?l=2,/〃-2=4,,/71n-1=71-1,

/i=n-2,y.|=^-4?j3=n6…，jn-i=1,

w2

符合題目要求.

18.【2017高中數(shù)學(xué)聯(lián)賽A卷(第02試)】將33x33方格紙中每個(gè)小方格染三種顏色之一，使得每種顏色

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

值.

【答案】56

【解析】記分隔邊的條數(shù)為L(zhǎng)首先，將方格紙按如圖分成三個(gè)區(qū)域，分別染成三種顏色，粗線上均為分隔

邊，此時(shí)共有56條分隔邊，即L=56.

下面證明LN56.將方格紙的行從上至下依次記為乙,…，&3，列從左至右依次記為當(dāng),/3.行4?中方

格出現(xiàn)的顏色個(gè)數(shù)記為n(A)列與中方格出現(xiàn)的顏色個(gè)數(shù)記為MB)三種顏色分別記為q,C2，C3.

對(duì)于一種顏色q,設(shè)n(g)是含有勺色方格的行數(shù)與列數(shù)之和.

記通㈤J】'部斤含的色方?

[〃(0,否則

類(lèi)似地定義6(8")).于是

33

33\.3

W［n（4）+n（B。］=）乏忸⑶勺）+

i=lj=l

1=1

=2ZjS（4，Cj）+6（Bi，Cj）］=￡%in（cj）

由于染勺色的方格有3332=363個(gè)，設(shè)含有q色方格的行有。個(gè)，列有〃個(gè)，則勺色的方格一定在這。行和

b列的交叉方格中，因此岫2363,

從而n(q)=a+b>2\[ab>2,363>38,

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

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

同理在列當(dāng)中，至少有n(Bj)-1條分隔邊,于是

3333

八W-3)-1]+2依砧-1]

1=14=1

=SfJjnUi)+n(B;)]-66②

=S；=in(q)-66③

下面分兩種情形討論.

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

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

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

情形2沒(méi)有一行也沒(méi)有一列的全部方格同色.則對(duì)任意1</<33,均有n(4)>2,n(B。>2.

從而由②知L》Xi=iln(At)+n(Bi)]-66>33X4-66=66>56.

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

19.(2017年山東預(yù)賽】求最大的正整數(shù)凡將正整數(shù)1到400任意填入20x20的400個(gè)方格中，則總有一行

或一列，其中兩數(shù)之差不小于九

【答案】證明見(jiàn)解析

【解析】將正方形表格分為20X10的兩個(gè)矩形表格,然后將1到200依次逐行按照從小到大的順序填入左側(cè)

表格,同理將201到400填人右側(cè)表格，則在此表格中，每行中兩數(shù)之差不大于209,每列中兩數(shù)之差不大于190,

所以n<209.

令M={1,2，…,91},N={300,301,…,400}易知,若集合M、N中各有一個(gè)數(shù)位于表格的同一行或同一列，則該

兩數(shù)之差不小于209,因此只需證明在表格的每一行及每一列中必有集合M、N中各一個(gè)數(shù).

設(shè)表格已經(jīng)任意填好，表格中共有i行/列含有M中的數(shù)，表格中共有k行，列含有N中的數(shù)，則i+j22西2

2V91>19即i+;>20.同理k+I>2例>2V101>20.因此i+j+k+l>41.

利用抽屜原理，必有一行或一列，同時(shí)含有兩個(gè)集合的各一個(gè)數(shù)，命題得證.

綜上所述,n=209.

20.[2017年江蘇預(yù)賽】平面上2n個(gè)點(diǎn)5>l,n6N),無(wú)三點(diǎn)共線，任意兩點(diǎn)間連線段，將其中任意彥+1條線

段染成紅色.求證：三邊都為紅色的三角形至少有n個(gè).

【答案】證明見(jiàn)解析

【解析】首先證明一定存在紅色三角形(三邊均為紅色的三角形為紅色三角形,下同).設(shè)從頂點(diǎn)4出發(fā)的紅色線

段最多，由4引出的紅色線段為481,482,…上取,則k>n+l.

I

若Bi，B2,-,為中存在兩點(diǎn)，不妨設(shè)為B，B2使線段B/2為紅色線段，則△48/2為紅色三角形.若名,&，???，Bk

相互之間沒(méi)有紅色線段相連，則從=1,2,…,k)出發(fā)的紅色線段最多有前-k條.所以這2n個(gè)點(diǎn)紅色線段最

多有

|[fc+/c(2n-k)+(2n-1—k)k]=k(2n—k)《，"+之；")=兀2<+].

與題設(shè)矛盾.

所以存在以A為頂點(diǎn)的紅色三角形.

(1)當(dāng)n=2時(shí)，平面上有四個(gè)點(diǎn)4、B、C、。中兩兩連線共有6條,其中有5條為紅色，只有一條非紅色，設(shè)為AB.

則4ACD與小BCD均為紅色三角形，命題成立.

(2)假設(shè)n=k時(shí)，命題成立，即至少存在k個(gè)紅色三角形.

當(dāng)〃=k+1時(shí)，有2k+2個(gè)點(diǎn)，且有(k+I)2+1條紅色線段，一定存在一個(gè)紅色三角形屋設(shè)為△ABC.

考查從4、B、C引出的紅色線段分別記為d(4),d(B),d(C)條,不妨設(shè)d(4)Wd(B)Wd(C).

若d(4)+d(B)<2k+2,則除去點(diǎn)4、B余下的2k個(gè)點(diǎn)之間至少有(k+l)2+1-(2k+1)=k2+1,

由歸納假設(shè)可知存在至少k個(gè)紅色三角形，再加上△ABC至少有k+1個(gè)紅色三角形.

若d(4)+d(B)>2k+3,則d(4)+d(B)+d(C)>3fc+5,故從4、B、C出發(fā)向其他2k-1個(gè)點(diǎn)引出紅色線

段至少有3k-1條.

因?yàn)?3k-1)-(2fc-1)=k.這(3k-1)線段至少有k對(duì)線段有公共點(diǎn)(不包括48,C),故至少存在k個(gè)紅色三

角形，再加上工ABC,則至少有k+1個(gè)紅色三角形，所以ri=k+1時(shí)命題也成立.

由⑴(2)可知，當(dāng)n>l,neN時(shí),2n點(diǎn)之間的層+1條紅色線段至少可組成n個(gè)紅色三角形.

21.【2017年新疆預(yù)賽】有一9個(gè)人參加乒乓球單打比賽，每2個(gè)人之間最多比賽1場(chǎng).已知比賽共舉辦了28場(chǎng).

求證：必然有4個(gè)人，他們之間都互相比賽過(guò).

【答案】證明見(jiàn)解析

【解析】用點(diǎn)火42,…，為代表參加乒乓球單打比賽的9個(gè)人.

構(gòu)造一個(gè)圖G=(V,E)如下：點(diǎn)集V—{%,上…,為},《和環(huán)連一條邊(記作女竹eE)當(dāng)且僅當(dāng)q和V/打過(guò)比賽.

由題意,G中含有28條邊.稱{叼|,…,/J構(gòu)成一個(gè)k一團(tuán)(2<k<9),如果該集合中任意兩點(diǎn)之間都有邊相連.

稱圖G所包含的最大團(tuán)中點(diǎn)的數(shù)目為圖G的團(tuán)數(shù).

這樣，問(wèn)題轉(zhuǎn)化為證明：圖G中必然存在一個(gè)4-團(tuán),即團(tuán)數(shù)至少為4.

用反證法,假設(shè)圖G的團(tuán)數(shù)e<3.因?yàn)閳DG中有邊，故3>2.只需考慮以下兩種情況：

情況1：3=3.

不妨設(shè)4={巧,“2，%}為圖G的一個(gè)3-團(tuán)，令B=V\A={v4,v5,v6,v7,v8,v9),

則4中含有3條邊,B中的每個(gè)點(diǎn)最多與A中的2個(gè)點(diǎn)相連，否則G中就會(huì)產(chǎn)生一個(gè)4-團(tuán),與假設(shè)矛盾.

若8中仍包含一個(gè)3-團(tuán)，不妨設(shè)為&={v4,v5,V6}MB2=B\B]=[v7lv8,v9}.

則同理可得力2中的每個(gè)點(diǎn)最多與當(dāng)中的2個(gè)點(diǎn)相連，而%中最多含有3條邊，

故G中最多含有3+2x6+3+2x34-3=27條邊,與題設(shè)矛盾.

若B中不含3-團(tuán)，則在B中取這樣的3個(gè)點(diǎn)，不妨記為火、1?5、。6,使得集合B1={。4，。5，。6}是集合B的所有三元

子集中包含邊數(shù)最多的.

設(shè)該邊數(shù)為q,則0<ex<2.取為=B\Bi=(v7,va,v9}.

若1WeiW2,則82中的每個(gè)點(diǎn)最多與當(dāng)中的2個(gè)點(diǎn)相連，否則8中會(huì)產(chǎn)生一個(gè)3-團(tuán),與假設(shè)矛盾.

而為中最多含有2條邊，故G中最多含有3+2x6+24-2x3+2=25條邊,與題設(shè)矛盾;若e1=0,則反和當(dāng)

中都不含邊，且當(dāng)和坊之間也沒(méi)有邊相連,否則與當(dāng)?shù)娜》?，故G中最多含有3+2x6=15條邊，同樣與題

設(shè)矛盾.

情況2：3=2.

我們斷定，在圖G中必然存在這樣的3個(gè)點(diǎn)%,外，％，使得叫女e€E,但W%圖E.

否則，由于3=2,G最多含有4條邊,與題設(shè)矛盾.

現(xiàn)在在圖G中新增加一條邊。2%,得到一個(gè)新圖G'.則G'的團(tuán)數(shù)”=3.

根據(jù)情況1的證明，。最多含有27條邊，從而G最多含有27-1=26條邊，同樣與題設(shè)矛盾.

因此，圖G中必然含有一個(gè)4-團(tuán)，即必然有4個(gè)人，他們之間都互相比賽過(guò).

22.【2016年全國(guó)】給定空間中十個(gè)點(diǎn)，其中任意四點(diǎn)不在一個(gè)平面上，將某些點(diǎn)之間用線段相連，若得到

的圖形中沒(méi)有三角形也沒(méi)有空間四邊形，試確定所連線段數(shù)目的最大值.

【答案】15

【解析】

以這十個(gè)點(diǎn)為頂點(diǎn)、所連線段為邊得一個(gè)十階簡(jiǎn)單圖G.

下面證明：圖G的邊數(shù)不超過(guò)15.

設(shè)圖G的頂點(diǎn)為火,"2,…，巧0,共有k條邊，用degSi)表示頂點(diǎn)巧的度.

若deg(M<3對(duì)i=1,2,…,10均成立，則k=昌deg(巧)<x10x3=15.

假設(shè)存在頂點(diǎn)門(mén)滿足deg(叫)>4.不妨設(shè)deg(也)=n>4,且也與%如均相鄰.于是,外,%,…，%+i

之間沒(méi)有邊，否則，就形成三角形.從而，女,外，?,?，2+1之間恰有。條邊.

對(duì)每個(gè)j(n+24/W10),V；至多與…，Un+i中的一個(gè)頂點(diǎn)相鄰(否則，設(shè)片與%、vt(2<s<t<n+

1)相鄰，則%、%、巧、%就對(duì)應(yīng)了一個(gè)空間四邊形的四個(gè)頂點(diǎn)，這與題設(shè)條件矛盾).從而，必，“3,…，2+1

與%+2,%1+3,…,之間的邊數(shù)至多為

10—(n4-1)=9—n.

在外+2,廝+3,…,％這9-n個(gè)頂點(diǎn)之間，由于沒(méi)有三角形，由托蘭定理，知至多有［怨之］條邊?因此，圖G

的邊數(shù)為

/、［(9—n)2

fc<n4-(9-n)+——----

4

=9+'9+圖"

如圖所示給出的圖共有15條邊，且滿足要求.

綜上，所求邊數(shù)的最大值為15.

23.【2016年吉林預(yù)賽】一次競(jìng)賽共有n道判斷題，統(tǒng)計(jì)八名考生的答題后發(fā)現(xiàn)：對(duì)于任意兩道題，恰有兩

名考生答“T,T”；恰有兩名考生答“F,F”；恰有兩名考生答“T,F”；恰有兩名考生答“F,T”.求n的最大值.

【答案】7

【解析】

記“T”為1,“F”為0,從而，得到一個(gè)8行n列的數(shù)表.

顯然，交換同一列的。和1,此表的性質(zhì)不改變.因此，不妨設(shè)數(shù)表第一行全為0.

設(shè)第i行共有見(jiàn)個(gè)0(i=l,2,…，8).

則％=n,XF=2Of=4n—n=3n.

下面考慮同一行中的“00”的對(duì)數(shù)，則

/%=2髭=〉%=鬃=〉Cl-Sf=2ai=n2-n.

==i=2=i=2

由柯西不等式

黑4號(hào)(優(yōu)通)2,

知5(2幺1%)2-2：=1碎SH2-n=>i(3n)2-3n<n2-n=>n<7.

表1為n取最大值的情形.

表1

0000000

0111100

0110011

0001111

1010101

1011010

1100110

1101001

從而，n的最大值為7.

24.【2016年浙江預(yù)賽】設(shè)正整數(shù)nN2,對(duì)2Xn格點(diǎn)鏈中的2n個(gè)結(jié)點(diǎn)用紅（R）、黃（丫）、藍(lán)（B）三種顏

色染色，左右端點(diǎn)中的三個(gè)結(jié)點(diǎn)已經(jīng)染好色，如圖。若對(duì)剩余的2n-3個(gè)結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)恰染一種顏色,

相鄰結(jié)點(diǎn)異色，求不同的染色方法數(shù)。

Y

【答案】見(jiàn)解析

【解析】

記P為R（或y）、Q為8時(shí)的染色數(shù)為an；記P為B、Q為R（或丫）時(shí)的染色數(shù)為以；記P為R、Q為丫或P為八Q為R

時(shí)的染色數(shù)為cn.

(1)若右端沒(méi)有約束時(shí)，每增加一個(gè)格均有三種不同的染色方法，則即+bn+cn=3"T.

(2)由對(duì)稱性，即將圖形上下翻轉(zhuǎn)，且顏色R與V互換，知即=4.

(3)考慮相互的遞推特征，如圖3,則斯=2%-i+0-1.

an+bn+cn=3"T

從而，，%=bn(neZ+).故a”=2，t_i+d-I=+bn_i+Cn-i=3時(shí)2,即為問(wèn)題所求的

、an~2bn-i+d-1

不同的染色方法數(shù).

25.【2016年湖南預(yù)賽】已知互異的正實(shí)數(shù)與、打、孫、辦滿足QXiXi/S,-)<17.

—i=l陽(yáng)

證明：從X1、％2、不、/中任取三個(gè)數(shù)作為邊長(zhǎng)，共可構(gòu)