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

高中数学联赛2015-2021年真题分类汇编专题40排列组合与图论第三缉1．【2020年吉林预赛】若(1+x+x2)1010 的展开式为a0+a1x+a2x2+⋯+a2020x2020 ，则a0+a3+a6+⋯+a2019= ( )A.3670 B.3669 C.31009 D.31100 【答案】C【解析】令x=1 ,得a0+a1+a2+⋯+a2020=31010; ①令x=ω(ω=−12+32i). 则ω3=1 且ω2+ω+1=0 ,a0+a1ω+a2ω2+a3ω3+⋯+a2020ω2020 =0; ②令x=ω2 ,得a0+a1ω2+a2ω4+a3ω6+⋯+a2020ω4040 =0. ③①+②+③得3(a0+a3+a6+⋯+a2019)=31010 ⇒a0+a3+a6+⋯+a2019=31009 .2．【2019年贵州预赛】在Rt△ABC中,∠B=90°,AB=15,BC=20.则顶点B与斜边各点的连线中(含边AB,BC)长度为整数的线段的条数是( )A.9 B.10 C.11 D.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相邻的两个位置,易知此时共有A22C42=12种填法:(2)若中心格内填6,与上述情形类似,共有12种填法(3)若中心格内填5,则与1相邻的两个位置可能填写2和3或者2和4，若填写2和3,则4有两个位置可以选择,此时共有A22C21C31=12种填法；若填写2和4,则3只能填在与2相邻的位置,此时共有A22C31=6种填法.综合上述情形,表格共有12+12+12+6=42种填法.4．【2017年四川预赛】在x+y+z8的展开式中,所有形如x2yazba,b∈N的项的系数之和是( )(A)112 (B)448 (C)1792 (D)14336【答案】C【解析】提示：因为x+y+z8=k=08C8kx8−ky+zk,故所有形如x2yazba,b∈N的项的系数之和为C86×26=1792.5．【2017年黑龙江预赛】形如45132这样的数称为“波浪数”,即十位数字,千位数字均比与它们各自相邻的数字大,则由1、2,3、4、5可构成数字不重复的五位“波浪数”个数为( )(A)20 (B)18 (C)16 (D)11【答案】C【解析】提示:分两类,第一类:千位和十位是5和4,则有A22A33,第二类千位和十位是5和3,则有A22A22.所以总共有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.故所有填法种数为6×3=18.故选C.7．【2016年辽宁预赛】将2、3、4、6、8、9、12、15共八个数排成一行,使得任意相邻两个数的最大公约数均大于1.则所有可能的排法共有()种A．720 B．1014 C．576 D．1296【答案】D【解析】先将八个数分成三组:I(2,4,8),Ⅱ(3,9,15),Ⅲ(6,12)由I组中与Ⅱ组中的数无公因子,知满足条件的排列必为:(1)取出6、12两数以后,剩余数分成三部分排列(依次)I、Ⅱ、I或Ⅱ、I、Ⅱ,此时,这六个数的排列有2×3!×3!×2=144种.而6、12放在不同部分相交的地方有两种不同的放法,共有2×144=288种(2)取出6、12两数以后,剩余数分成两部分排列I、Ⅱ或Ⅱ、I,此时,这六个数有2×3!×3!种排列方式,而6、12若全部在I组与Ⅱ组的交界处,有两种排法,否则,只有一个在交界处,另一个位置有六种选法,共有2×3!×3!×2+2×6=1008.故所求的排法数为1008+288=1296.8．【2016年湖南预赛】在某次乒乓球单打比赛中，原计划每两名选手各比赛一场，但有三名选手各比赛两场之后就退出了，这样全部比赛只进行了50场. 则上述三名选手之间比赛的场数为（ ）A．0 B．1 C．2 D．3【答案】B【解析】试题分析：设一共有n个选手，故总场次Cn−32+6−x=(n−3)(n−4)2+6−x=50，其中x为上述3名选手之间比赛的场数，则x=(n−3)(n−4)2−44，经验证，当n=13时，x=1.考点：排列组合.9．【2015年四川预赛】已知n为正整数，二项式x2+1x3n的展开式中含有x7的项，则n的最小值为（ ）.A．4 B．5 C．6 D．7【答案】C【解析】注意到，所求二项式展开式的通项公式为Tr+1=Cnrx2n−r1x3r=Cnrx2n−5r由2n−5r=7r∈N，知当r=1时，n有最小值6.10．【2021年广西预赛】某校n 名同学通过选拔进入学校的数学讨论班，在一次讨论班上他们讨论A、B和C 三个问题.已知寿位同学都和班里的其他所有同学讨论了其中的一个问题.每两位同学只讨论一个问题.若至少有3名同学互相之间讨论的是同一个问题，求n的最小值，并给出证明.【答案】n 的最小值为17.证明见解析【解析】n 的最小值为17.设所求的最小值为m .(1)先考虑n=17 的情形.将17名同学表示为a1,a2,…,a17. 因为163>5 ,根据抽屈原理知a1 与其他16名同学中至少有6人讨论的是同一个问题,不妨设a1 与a2,…,a7 讨论的是问题A .若这6人中有2个人(不妨是a2 和a3 )讨论的是问题A ,则a1,a2 和a3 这3名同学互相之间讨论的是问题A. 否则，问题转化为这6名同学之间只讨论问题B或C 的情形.下面证明至少有3名同学互相讨论的是同一个问题.因为52>2 ,根据抽屉原理知a2 与其他5名同学中至少有3人(不妨是a3,a4 和a5 )讨论的是同一个问题，不妨设所讨论的是问题B .若这3人中有2人(不妨是a3 和a4 )讨论的是问题B ,则a2 、a3 和a4 这3名同学互相之间讨论的是问题B .否则a3,a4 和a5 讨论的是问题C.因此，m≤17 .(2)当n=16 时，考虑二进制下的集合G={0000,0001,⋯,1111} ，集合中每一个数表示一名同学。

对集合中的元素施以“按位加”(+)运算，即不考虑进位，同位相同则为0，同位相异则1.例如：1010+1100=0110 .设：V1={1100,0011,1001,1110,1000} ，V2={1010,0101,0110,1101,0100} ，V3={0001,0010,0111,1011,1111} .若x,y∈G ,易知x+y∈G .用x+y∈Vi(i=1,2,3) 表示同学x 和同学y 讨论第i 个问题；用x∈Vi(i=1,2,3) 表示同学0000与同学x 讨论第i 个问题.按照上述规定，没有3位同学互相之间讨论同一个问题.因此m≥17 .综上所述，m=17 ,即n 的最小值为17.11．【2020高中数学联赛A卷（第02试）】给定凸20边形P.用P的17条在内部不相交的对角线将P分割成18个三角形,所得图形称为P的一个三角剖分图.对P的任意一个三角剖分图T,P的20条边以及添加的17条对角线均称为T的边.T的任意10条两两无公共端点的边的集合称为T的一个完美匹配.当T取遍P的所有三角剖分图时,求T的完美匹配个数的最大值.【答案】89【解析】将20边形换成2n边形,考虑一般的问题.对凸2n边形P的一条对角线,若其两侧各有奇数个P的顶点,称其为奇弦,否则称为偶弦.首先注意下述基本事实:对P的任意三角剖分图T,T的完美匹配不含奇弦.(*)如果完美匹配中有一条奇弦e1,因为T的一个完美匹配给出了P的顶点集的一个配对划分,而e1两侧各有奇数个顶点,故该完美匹配中必有T的另一条边e2,端点分别在e1的两侧,又P是凸多边形,故e1与e2在P的内部相交,这与T是三角剖分图矛盾.记f(T)为T的完美匹配的个数.设F1=1,F2=2,对k≥2, Fk+2=Fk+1+Fk,是Fibonacci数列.下面对n归纳证明:若T是凸2n边形的任意一个三角剖分图,则f(T)≤Fn.设P=A1A2⋯A2n是凸2n边形.从P的2n条边中选n条边构成完美匹配,恰有两种方法, A1A2,A3A4,⋯,An−1An或A2A3,A4A5,⋯,A2n−2A2n−1,A2nA1.当n=2时,凸四边形P的三角剖分图T没有偶弦,因此T的完美匹配只能用P的边,故f(T)=2=F2.当n=3时,凸六边形P的三角剖分图T至多有一条偶弦.若T没有偶弦,同上可知f(T)=2.若T含有偶弦,不妨设是A1A4,选用A1A4的完美匹配是唯一的,另两条边只能是A2A3,A5A6,此时f(T)=3.总之f(T)≤3=F3.结论在n=2,3时成立.假设n≥4,且结论在小于n时均成立.考虑凸2n边形P=A1A2⋯A2n的一个三角剖分图T.若T没有偶弦,则同上可知f(T)=2.对于偶弦e,记e两侧中P的顶点个数的较小值为w(e).若T含有偶弦,取其中一条偶弦e使w(e)达到最小.设w(e)=2k,不妨设e为A2nA2k+1,则每个Ai(i=1,2,⋯,2k)不能引出偶弦.事实上,假设AiAj是偶弦,若j∈{2k+2,2k+3,⋯,2n−1},则AiAj与e在P的内部相交,矛盾.若j∈{1,2,⋯,2k+1,2n},则w(AiAj)<2k,与w(e)的最小性矛盾.又由(∗)知完美匹配中没有奇弦,故A1,A2,⋯,A2k只能与其相邻顶点配对,特别地, A1只能与A2或A2n配对.下面分两种情况.情形1:选用边$A_1A_2$.则必须选用边A3A4,⋯,A2k−1A2k.注意到A2nA2k+1的两侧分别有2k,2n−2k−2个顶点, 2n−2k−2≥w(A2nA2k+1)=2k,而n≥4,因此2n−2k≥6.在凸2n-2k边形P1=A2k+1A2k+2⋯A2n上,T的边给出了Pl的三角剖分图T1,在T中再选取n-k条边e1e2⋯en−k,与A1A2,A3AA⋯A2k−1A2k一起构成T的完美匹配,当且仅当e1,e2⋯en−k是T1的完美匹配.故情形1中的T的完美匹配个数等于f(T1).情形2:选用边A1A2n.则必须选用边A2A3,⋯,A2kA2k+1.在凸2n-2k-2边形P2=A2k+2A2k+3⋯A2n−1中构造如下的三角剖分图T2:对2k+2≤i