高中数学联赛2015-2021年真题分类汇编-排列组合与图论【含解析】

高中数学联赛2015-2021年真题分类汇编

专题40排列组合与图论第三缉

1.【2020年吉林预赛】若(1+x+Myo]。的展开式为劭++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年贵州预赛】在RtAABC中,NB=9(r,AB=15,BC=20.则顶点B与斜边各点的连线中(含边AB,BC)

长度为整数的线段的条数是()

A.9B.10C.llD.12

【答案】D

【解析】因为顶点B到斜边AC的距离12,所以顶点B与斜边各点的连线中长度为13、14、15的线段各有

两条,长度为12、16、17、18、19、20的线段各有一条，故满足条件的线段共有12条.

3.[2019年吉林预赛】将1,2,3,--,9这9个数全部填入下图的3x3方格内，每个格内填一个数，则使得每行中

的数从左至右递增，每列中的数从上至下递减的不同填法共有()种

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

【答案】c

【解析】1只能填在左下角格内,9只能填在右上角格内.中心格内的数字可能为4,5,6,现分3种情

形讨论：

(1)若中心格内填4,则2和3只能填在与1相邻的两个位置，易知此时共有房盘=12种填法：

(2)若中心格内填6,与上述情形类似，共有12种填法

(3)若中心格内填5,则与1相邻的两个位置可能填写2和3或者2和4,若填写2和3,则4有两个位置可以选

择，此时共有/6玛=12种填法；若填写2和4,则3只能填在与2相邻的位置,此时共有朗玛=6种填法.

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

4.【2017年四川预赛】在(x+y+z＞的展开式中，所有形如/yaz.a,/,eN)的项的系数之和是()

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

【答案】C

【解析】提示：因为(x+y+z)8=浅=0或迪-气丫+2)匕故所有形如产丫。2/(1/eN)的项的系数之和为

若x26=1792.

5.[2017年黑龙江预赛】形如45132这样的数称为“波浪数”，即十位数字,千位数字均比与它们各自相邻的数

字大，则由1、2,3、4、5可构成数字不重复的五位“波浪数”个数为()

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

【答案】C

【解析】提示:分两类，

第一类:千位和十位是5和4,则有掰用，

第二类千位和十位是5和3,则有掰鹿.

所以总共有12+4=16种.

6.[2017年贵州预赛】将1,2,…,9这九个数字填在如图所示的九个空格中,要求每一行从左到右，每一列从上

到下分别依次增大.当5固定在图中中央位置时，则填写空格的方法种数为()

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

【答案】D

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

第一行例)可填1,2,3;1,2,4;1,3,4.其中每一种情况对应第三行(列)可填6,7,9;6,8,9;7,8,9.

故所有填法种数为6x3=18.

故选C.

7.[2016年辽宁预赛】将2、3、4、6、8、9、12、15共八个数排成一行，使得任意相邻两个数的最大公约

数均大于1.则所有可能的排法共有()种

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

【答案】D

【解析】

先将八个数分成三组：

1(2,4,8),11(3,9,15),111(6,12)由I组中与H组中的数无公因子，知满足条件的排列必为：

⑴取出6、12两数以后，剩余数分成三部分排列(依次)1、II、I或II、I、此时，这六个数的排列有

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

⑵取出6、12两数以后，剩余数分成两部分排列I、II或II、I,此时，这六个数有2x3!x3!种排列方式，而6、12

若全部在I组与II组的交界处，有两种排法，否则，只有一个在交界处，另一个位置有六种选法，共有2x3!x3!x

(2+2x6)=1008.

故所求的排法数为1008+288=1296.

8.[2016年湖南预赛】在某次乒乓球单打比赛中，原计划每两名选手各比赛一场，但有三名选手各比赛两

场之后就退出了，这样全部比赛只进行了50场.则上述三名选手之间比赛的场数为()

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

【答案】B

【解析】

试题分析：设一共有n个选手，故总场次鬣.3+6-x=⑴-号=旬+6一%=50,其中x为上述3名选手之间

比赛的场数，则X=m-3,）_44,经验证，当n=13时，x=l.

考点：排列组合.

9.[2015年四川预赛】已知n为正整数，二项式+或的展开式中含有一的项，则n的最小值为（）.

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

【答案】C

【解析】

注意到，所求二项式展开式的通项公式为〃+1=。（公尸-（点丫=Crx2n-5r

由2n—5r=7（reN）,知当r=l时，n有最小值6.

10.【2021年广西预赛】某校n名同学通过选拔进入学校的数学讨论班，在一次讨论班上他们讨论A、B和

C三个问题.已知寿位同学都和班里的其他所有同学讨论了其中的一个问题.每两位同学只讨论一个问题.若

至少有3名同学互相之间讨论的是同一个问题，求n的最小值，并给出证明.

【答案】n的最小值为17.证明见解析

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

设所求的最小值为m.

（1）先考虑般=17的情形.将17名同学表示为由,a?，…,a17.

因为?>5，根据抽屈原理知的与其他16名同学中至少有6人讨论的是同一个问题，

不妨设的与…，讨论的是问题4.

若这6人中有2个人（不妨是（X2和）讨论的是问题4,

则由以2和。3这3名同学互相之间讨论的是问题4

否则，问题转化为这6名同学之间只讨论问题B或C的情形.

下面证明至少有3名同学互相讨论的是同一个问题.

因为|>2，根据抽屉原理知a?与其他5名同学中至少有3人（不妨是。3，。4和。5）讨论的是同一个问题，不

妨设所讨论的是问题B.

若这3人中有2人（不妨是（13和）讨论的是问题B，则、。3和这3名同学互相之间讨论的是问题B.

否则。3，。4和讨论的是问题C.

因此，m<17.

（2）当n=16时，考虑二进制下的集合G={0000,0001,,一,1111}，集合中每一个数表示一名同学。对集合

中的元素施以“按位加”（+）运算,即不考虑进位,同位相同则为0,同位相异则1.例如:1010+1100=0110.

设:

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)表示同学x和同学y讨论第i个问题；

用xG匕(i=1,2,3)表示同学0000与同学x讨论第i个问题.

按照上述规定，没有3位同学互相之间讨论同一个问题.

因此m>17.

综上所述，m=17，即n的最小值为17.

11.12020高中数学联赛A卷(第02试)】给定凸20边形P.用P的17条在内部不相交的对角线将「分割

成18个三角形,所得图形称为P的一个三角剖分图.对P的任意一个三角剖分图T,P的20条边以及添加的17

条对角线均称为T的边7的任意10条两两无公共端点的边的集合称为T的一个完美匹配.当T取遍P的所

有三角剖分图时，求T的完美匹配个数的最大值.

【答案】89

【解析】将20边形换成2〃边形，考虑一般的问题.

对凸2n边形P的一条对角线，若其两侧各有奇数个P的顶点，称其为奇弦，否则称为偶弦.首先注意下述基本事

实：

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

如果完美匹配中有一条奇弦e1,因为T的一个完美匹配给出了P的顶点集的一个配对划分，而ei两侧各有奇数

个顶点，故该完美匹配中必有7"的另一条边02,端点分别在内的两侧，又尸是凸多边形，故e1与e2在尸的内部相交,

这与T是三角剖分图矛盾.

记/'(7)为7的完美匹配的个数.设&=L尸2=2,对k>2,醍+2=Fk+i+是Fibonacci数列.

卜.面对"归纳证明:若T是凸2n边形的任意一个三角剖分图，则/(7)<Fn.

设P=&&…4”是凸2"边形.从P的2〃条边中选n条边构成完美匹配，恰有两种方

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

当n=2时，凸四边形P的三角剖分图7没有偶弦，因此T的完美匹配只能用P的边，故/\7)=2=F2.

当〃=3时，凸六边形P的三角剖分图T至多有一条偶弦.若7没有偶弦，同上可知/(T)=2.

若丁含有偶弦，不妨设是选用的完美匹配是唯一的，

另两条边只能是&&，4546,此时f(T)=3.总之/(7)<3=F3.

结论在"=2,3时成立.假设论4,且结论在小于〃时均成立.考虑凸2n边形P=A,A2…42n的一个三角剖分图

r若T没有偶弦,则同上可知/'(T)=2.

对于偶弦e,记e两侧中P的顶点个数的较小值为w(e).若7•含有偶弦，取其中一条偶弦e使w(e)达到最小.

设w(e)=2/c,不妨设e为42nA2k+i，则每个=1,2,…,2k)不能引出偶弦.

事实上，假设•是偶弦，若/6{2k+2,2k+3,-,2n-1},则4网•与e在P的内部相交,矛盾.

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

又由(*)知完美匹配中没有奇弦，故儿醺…，&k只能与其相邻顶点配对，特别地，4只能与%或42n配对.下面

分两种情况.

情形1:选用边$4」4_2$.则必须选用边心44，“・，42142心注意到4/2丘1的两侧分别有湍271-24-2个顶

点，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一起构成T的完美匹配，

当且仅当02…e.T是口的完美匹配•故情形।中的丁的完美匹配个数等于/(n).

情形2：选用边为A2n•则必须选用边4A3,…,&〃2上+1•在凸2〃-2k-2边形P2=4k+242k+3-M2n-l中构造如下

的三角剖分图△：对2k+2<i<j<2n—1,若线段44•是7的边，则也将其作为72的边,由于这些边在内部互

不相交，因此可再适当地添加一些P2的对角线，得到一个22的三角剖分图72，它包含了7的所有在顶点

&k+2,42k+3,…，42口-1之间的边•因此每个包含边42n4，&43,…，&k&k+i的T的完美匹配，其余的边必定是

久的完美匹配•故情形2中的T的完美匹配个数不超过

由归纳假设得/(A)<Fn-k,/(T2)<F…T，

结合上面两种情形以及Q1,有f(T)<fg+/(0)<Fn_k+叫-i=Fn-k+i<Fn.

下面说明等号可以成立.考虑凸2〃边形&&n的三角剖分图为：

添加对角线424271，42睛3,43A2n-l，4271-14,4d&n-Z，…，An+3，n，，n4ri+2・

重复前面的论证过程，/'(/)=2J(Z13)=3.对>4,考虑偶弦41A3.

情形1,用4〃2,由于在凸2〃-2边形①①…4m中的三角剖分图恰是4t-i，此时有个7的完美匹配.

情形2,用&&"，山于在凸2"-4边形4/…中7的边恰构成三角剖分图4-2,不用添加任何对角线，故这

一情形下T的完美匹配个数恰为/(/_2).

从而对佗4,有/(4)=/(/_])+f(4_2).

由数学归纳法即得/(4)=•结论得证.

因此，对凸20边形P,f(7)的最大值等于Fl。=89.

12.【2020年福建预赛】将一个2020x2020方格表的每个格染黑、白两种颜色之一，满足以下条件：方格表

中的任意一个格A,它所在的行与列的所有格中，与A异色的格多于与A同色的格.证明：染色后，方格表

中每行每列两种颜色的格一样多

【答案】证明见解析

【解析】对黑格与白格分别标记为-1与1.对于任意的4i,)(2020)，设第i行各数之和为*,第/列

各数之和为弓，第i行与第j列交叉格中的数为a”，则位于第i行或第/列上的全部数之和为其+弓-四厂

由条件，知Sj+弓一a“与叼异号.

则(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.

故对于任意的i、j,均有Sj—0,tj—0.

从而，每行、每列中的两种颜色的格一样多.

13.[2019年上海预赛】设n为正整数，称〃X”的方格表7“的网格线的交点(共(n+1)2个交点)为格点.现将数

1,2,…,("+1)2分配给7；的所有格点，使不同的格点分到不同的数称7；的一个1X1格子S为“好格”:若从S的某

个顶点起按逆时针方向读出的四个顶点上的数依次递增(例如，图中是将数1,2,…,9分配给T2的格点的一种方

式，其中,8、C为好格，而A、。不为好格)设T”中好格个数的最大值为式初

⑴求42)的值；

(2)求负〃)关于正整数〃的表达式

【答案】⑴3；⑵/⑺=［号斗

【解析】⑴

如图所示，将T2的四个1X1格子(以下简称“格子”)分别记为A、B、C、。，将九个格点上的数分别记为a力,..工

当〃也…i,依次取为1,2,...,9时,易验证8、C、。均为好格，这表明次2巨3.

现假设火2)=4,即存在一种数的分配方式，使A、B、C、。均为好格.

由对称性,不妨设边界上八个数a,h,...,h中的最小数为a或〃.此时，由A为好格，知要么a<b<i<h要么b<i<h<a.

故txi<h总成立.进而，由B、C为好格，知必有i<f<g<h,b<c<d<i但此时d<i<f，与D为好格矛盾.

综上32)=3.

(2)设7“的各格点的数已被分配好，此时，好格有k个称格子的一条边为一段“格线”.对7“的每段格线标记一个

箭头:若格线连接了两个格点U、V(U上的数小于V上的数)，则对格线UV标上一个指向而顺时针旋转90。

后所得方向的箭头.

称一个格子S及S的一条边UV所构成的有序对(S,UV)为一个“对子”:若UV上所标的箭头由S内指向S外.

设对子总数为N.

一方面，每个格子S至少贡献一个对子(否则，沿逆时针方向读S顶点上的数将永远递减,矛盾)，而据好格的定义,

每个好格贡献三个对子，于是N>3/c+1-(n2—/c)=2/c+n2.

另一方面Z的每段格线至多贡献一个对子，且7；边界上至少有一段格线标有向内的箭头(否则，沿逆时针方向

读7“边界上的数将永远递增,矛盾)，从而，不贡献对子.

注意到,7；的格线段数为2"("+1).于是,NW2”(”+1)-1.

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

即好格个数k4安二.

最后，对〃为奇数和〃为偶数的情况，分别如图所示

将12…,（〃+1）2按粗线经过的次序依次分配给所有格点.对图中标有“▲”记号的每个格子，易验证，按被粗线经

过的先后次序排列其4个顶点，恰为一种逆时针排列，因而，这些格子均为好格

左图中好格数为等・n+亨=注二

右图中好格数为受《+管一1）・1+.号二=件等二

其中,团表示不超过实数x的最大整数.

综上/（“）=［号匚］

14.［2019年贵州预赛】我们知道,目前最常见的骰子是六面骰，它是一颗正立方体，上面分别有一到六个洞（或

数字），其相对两面之数字和必为七.显然，掷一次六面骰,只能产生六个数之一（正上面）。现欲要求你设计一个

“十进制骰”，使其掷一次能产生0~9这十个数之一，而且每个数字产生的可能性一样。请问:你能设计出这样的

骰子吗?若能，请写出你的设计方案;若不能，写出理由。

【答案】答案见解析

【解析】因为不存在正十面体，所以直接产生“十进制骰是办不到的。但要实现“十进制骰”的要求，这样的骰子

是也是能设计的。即把骰子做成正二十面体,使其相对两面标同一个数字，这样0~9这十个数字就均匀分布在

骰子上，当掷一次骰子时，最上面出现的数字必然是0~9这十个数字之一，显然，每个数字出现的可能性是一样

的。故"个位骰''即为"二十面骰”

（注:答案不唯一，只要解答合情合理合法，均可适当给分。就以二十面骰为例，将0~9中的每个数字放在相邻两

个面上或者任意两个面上,也是可以的。）

15.12019高中数学联赛B卷（第02试）】将一个凸2019边形的每条边任意染为红、黄、蓝三种颜色之一,

每种颜色的边各673条.证明:可作这个凸2019边形的2016条在内部互不相交的对角线将其剖分成2017个

三角形，并将所作的每条对角线也染为红、黄、蓝三种颜色之一，使得每个三角形的三条边或者颜色全部

相同或者颜色互不相同.

【答案】证明见解析

【解析】我们对〃云归纳证明加强的命题:如果将凸”边形的边染为三种颜色a,b,c,并且三种颜色的边

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

当〃=5时，若三种颜色的边数为1、1、3,由对称性，只需考虑如下两种情形，分别可作图①中所示的三角

形剖分.

图①

若三种颜色的边数为1、2、2,由对称性,只需考虑如下三种情形，分别可作图②中所示的三角形剖分.

图②

假设结论对"（论5）成立，考虑n+1的情形，将凸n+1边形记为4遇2-Al+i-

情形1：有两种颜色的边各只有一条.不妨设心〃色边各只有一条.由于"+G6,故存在连续两条功均为c色,

不妨设是4714n+14•作对角线44，并将44染为C色，则三角形4（+14的三边全部同色•此时凸〃边形

为乙…An的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分.

情形2:某种颜色的边只有一条，其余颜色的边均至少两条.不妨设。色边只有一条，于是可以选择两条相邻

边均不是a色，不妨设(dt+iMn+iA均不是“色，作对角线人4，则必心有唯一的染色方式，使得三角

形A储n+i&的三边全部同色或互不同色•此时凸〃边形&①…(的三种颜色的边均至少有一条，由归纳假

设，可对其作符合要求的三角形剖分.

情形3：每种颜色的边均至少两条.作对角线则44n有唯一的染色方式，使得三角形4nAi+14的三边

全部同色或互不同色.此时凸“边形4遇2…4的三种颜色的边均至少有一条由归纳假设，可对其作符合要求

的三角形剖分.

综合以上3种情形，可知〃+1的情形下结论也成立.

由数学归纳法，结论获证.

16.【2018年安徽预赛】在正2018边形的每两个顶点之间均连一条线段，并把每条线段染成红色或蓝色.求

此图形中三边颜色都相同的三角形的最小个数.

【答案】N=2此oo9

【解析】

设N是此图形中三边颜色都相同的三角形数目，M是此图形中三边颜色不全相同的三角形数目，%是以第

i个顶点为端点的红色线段数目，则有M+N=废oi8，S/=l8x,(2017-Xi)=2M.当且仅当每个々=1008或

2

1009时，N取得最小值废018-1009x1008=2C^009.

N=2盘oo9是可以取到的，例如：把线段i-i士Jmod2018(1<i<2018,1<;<504)染成红色，其他

线段染成蓝色.

17.[2018年浙江预赛】如图所示将同心圆环均匀分成n(n>3)格.在内环中固定数字1~〃.问能否将数字1~"

填入外环格内，使得外环旋转任意格后有且仅有一个格中内外环的数字相同？

【答案】见解析

【解析】

设对应于内环1,2,”的外环数字为八，h,i,„它是数字1,2,”的一个排列.对上1,2,

〃，记外环数字立在按顺时针方向转动人格时，和内环数字相同，即

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

根据题意，力，力，…，./〃应是0,1,2,…，〃-1的排列.求和

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

于是n必须是奇数.

对于奇数〃，我们取i”=〃，itn=n-m,(m=\,2,…，〃-1),可以验证九一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高中数学联赛A卷(第02试)】将33x33方格纸中每个小方格染三种颜色之一，使得每种颜色

的小方格的个数相等.若相邻两个小方格的颜色不同，则称它们的公共边为“分隔边”试求分隔边条数的最小

值.

【答案】56

【解析】记分隔边的条数为L首先，将方格纸按如图分成三个区域，分别染成三种颜色，粗线上均为分隔

边，此时共有56条分隔边，即L=56.

下面证明LN56.将方格纸的行从上至下依次记为乙,…，&3，列从左至右依次记为当,/3.行4・中方

格出现的颜色个数记为n(A)列与中方格出现的颜色个数记为MB)三种颜色分别记为q,C2，C3.

对于一种颜色q,设n(g)是含有勺色方格的行数与列数之和.

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

[〃(0,否则

类似地定义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个，设含有q色方格的行有。个，列有〃个，则勺色的方格一定在这。行和

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

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

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

由于在行4中有n(4)种颜色的方格，因此至少有n(4)-1条分隔边.

同理在列当中，至少有n(Bj)-1条分隔边,于是

3333

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

1=14=1

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

=S；=in(q)-66③

下面分两种情形讨论.

情形1有一行或一列全部方格同色不妨设有一行全为J色，从而方格纸的33列中均含有q色的方格，由于q

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

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

情形2没有一行也没有一列的全部方格同色.则对任意1</<33,均有n(4)>2,n(B。>2.

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

综上所述，分隔边条数的最小值等于56.

19.(2017年山东预赛】求最大的正整数凡将正整数1到400任意填入20x20的400个方格中，则总有一行

或一列，其中两数之差不小于九

【答案】证明见解析

【解析】将正方形表格分为20X10的两个矩形表格,然后将1到200依次逐行按照从小到大的顺序填入左侧

表格,同理将201到400填人右侧表格，则在此表格中，每行中两数之差不大于209,每列中两数之差不大于190,

所以n<209.

令M={1,2，…,91},N={300,301,…,400}易知,若集合M、N中各有一个数位于表格的同一行或同一列，则该

两数之差不小于209,因此只需证明在表格的每一行及每一列中必有集合M、N中各一个数.

设表格已经任意填好，表格中共有i行/列含有M中的数，表格中共有k行，列含有N中的数，则i+j22西2

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

利用抽屉原理，必有一行或一列，同时含有两个集合的各一个数，命题得证.

综上所述,n=209.

20.[2017年江苏预赛】平面上2n个点5>l,n6N),无三点共线，任意两点间连线段，将其中任意彦+1条线

段染成红色.求证：三边都为红色的三角形至少有n个.

【答案】证明见解析

【解析】首先证明一定存在红色三角形(三边均为红色的三角形为红色三角形,下同).设从顶点4出发的红色线

段最多，由4引出的红色线段为481,482,…上取,则k>n+l.

I

若Bi，B2,-,为中存在两点，不妨设为B，B2使线段B/2为红色线段，则△48/2为红色三角形.若名,&，•••，Bk

相互之间没有红色线段相连，则从=1,2,…,k)出发的红色线段最多有前-k条.所以这2n个点红色线段最

多有

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

与题设矛盾.

所以存在以A为顶点的红色三角形.

(1)当n=2时，平面上有四个点4、B、C、。中两两连线共有6条,其中有5条为红色，只有一条非红色，设为AB.

则4ACD与小BCD均为红色三角形，命题成立.

(2)假设n=k时，命题成立，即至少存在k个红色三角形.

当〃=k+1时，有2k+2个点，且有(k+I)2+1条红色线段，一定存在一个红色三角形屋设为△ABC.

考查从4、B、C引出的红色线段分别记为d(4),d(B),d(C)条,不妨设d(4)Wd(B)Wd(C).

若d(4)+d(B)<2k+2,则除去点4、B余下的2k个点之间至少有(k+l)2+1-(2k+1)=k2+1,

由归纳假设可知存在至少k个红色三角形，再加上△ABC至少有k+1个红色三角形.

若d(4)+d(B)>2k+3,则d(4)+d(B)+d(C)>3fc+5,故从4、B、C出发向其他2k-1个点引出红色线

段至少有3k-1条.

因为(3k-1)-(2fc-1)=k.这(3k-1)线段至少有k对线段有公共点(不包括48,C),故至少存在k个红色三

角形，再加上工ABC,则至少有k+1个红色三角形，所以ri=k+1时命题也成立.

由⑴(2)可知，当n>l,neN时,2n点之间的层+1条红色线段至少可组成n个红色三角形.

21.【2017年新疆预赛】有一9个人参加乒乓球单打比赛，每2个人之间最多比赛1场.已知比赛共举办了28场.

求证：必然有4个人，他们之间都互相比赛过.

【答案】证明见解析

【解析】用点火42,…，为代表参加乒乓球单打比赛的9个人.

构造一个图G=(V,E)如下：点集V—{%,上…,为},《和环连一条边(记作女竹eE)当且仅当q和V/打过比赛.

由题意,G中含有28条边.称{叼|,…,/J构成一个k一团(2<k<9),如果该集合中任意两点之间都有边相连.

称图G所包含的最大团中点的数目为图G的团数.

这样，问题转化为证明：图G中必然存在一个4-团,即团数至少为4.

用反证法,假设图G的团数e<3.因为图G中有边，故3>2.只需考虑以下两种情况：

情况1：3=3.

不妨设4={巧,“2，%}为图G的一个3-团，令B=V\A={v4,v5,v6,v7,v8,v9),

则4中含有3条边,B中的每个点最多与A中的2个点相连，否则G中就会产生一个4-团,与假设矛盾.

若8中仍包含一个3-团，不妨设为&={v4,v5,V6}MB2=B\B]=[v7lv8,v9}.

则同理可得力2中的每个点最多与当中的2个点相连，而%中最多含有3条边，

故G中最多含有3+2x6+3+2x34-3=27条边,与题设矛盾.

若B中不含3-团，则在B中取这样的3个点，不妨记为火、1?5、。6,使得集合B1={。4，。5，。6}是集合B的所有三元

子集中包含边数最多的.

设该边数为q,则0<ex<2.取为=B\Bi=(v7,va,v9}.

若1WeiW2,则82中的每个点最多与当中的2个点相连，否则8中会产生一个3-团,与假设矛盾.

而为中最多含有2条边，故G中最多含有3+2x6+24-2x3+2=25条边,与题设矛盾;若e1=0,则反和当

中都不含边，且当和坊之间也没有边相连,否则与当的取法矛盾，故G中最多含有3+2x6=15条边，同样与题

设矛盾.

情况2：3=2.

我们断定，在图G中必然存在这样的3个点%,外，％，使得叫女e€E,但W%图E.

否则，由于3=2,G最多含有4条边,与题设矛盾.

现在在图G中新增加一条边。2%,得到一个新图G'.则G'的团数”=3.

根据情况1的证明，。最多含有27条边，从而G最多含有27-1=26条边，同样与题设矛盾.

因此，图G中必然含有一个4-团，即必然有4个人，他们之间都互相比赛过.

22.【2016年全国】给定空间中十个点，其中任意四点不在一个平面上，将某些点之间用线段相连，若得到

的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值.

【答案】15

【解析】

以这十个点为顶点、所连线段为边得一个十阶简单图G.

下面证明：图G的边数不超过15.

设图G的顶点为火,"2,…，巧0,共有k条边，用degSi)表示顶点巧的度.

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

假设存在顶点门满足deg(叫)>4.不妨设deg(也)=n>4,且也与%如均相邻.于是,外,%,…，%+i

之间没有边，否则，就形成三角形.从而，女,外，・,・，2+1之间恰有。条边.

对每个j(n+24/W10),V；至多与…，Un+i中的一个顶点相邻(否则，设片与%、vt(2<s<t<n+

1)相邻，则%、%、巧、%就对应了一个空间四边形的四个顶点，这与题设条件矛盾).从而，必，“3,…，2+1

与%+2,%1+3,…,之间的边数至多为

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

在外+2,厮+3,…,％这9-n个顶点之间，由于没有三角形，由托兰定理，知至多有［怨之］条边•因此，图G

的边数为

/、［(9—n)2

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

4

=9+'9+图"

如图所示给出的图共有15条边，且满足要求.

综上，所求边数的最大值为15.

23.【2016年吉林预赛】一次竞赛共有n道判断题，统计八名考生的答题后发现：对于任意两道题，恰有两

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

【答案】7

【解析】

记“T”为1,“F”为0,从而，得到一个8行n列的数表.

显然，交换同一列的。和1,此表的性质不改变.因此，不妨设数表第一行全为0.

设第i行共有见个0(i=l,2,…，8).

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

下面考虑同一行中的“00”的对数，则

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

==i=2=i=2

由柯西不等式

黑4号(优通)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年浙江预赛】设正整数nN2,对2Xn格点链中的2n个结点用红（R）、黄（丫）、蓝（B）三种颜

色染色，左右端点中的三个结点已经染好色，如图。若对剩余的2n-3个结点，要求每个结点恰染一种颜色,

相邻结点异色，求不同的染色方法数。

Y

【答案】见解析

【解析】

记P为R（或y）、Q为8时的染色数为an；记P为B、Q为R（或丫）时的染色数为以；记P为R、Q为丫或P为八Q为R

时的染色数为cn.

(1)若右端没有约束时，每增加一个格均有三种不同的染色方法，则即+bn+cn=3"T.

(2)由对称性，即将图形上下翻转，且颜色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时2,即为问题所求的

、an~2bn-i+d-1

不同的染色方法数.

25.【2016年湖南预赛】已知互异的正实数与、打、孙、办满足QXiXi/S,-)<17.

—i=l阳

证明：从X1、％2、不、/中任取三个数作为边长，共可构