专题40排列组合与图论第三缉-备战2022年高中数学联赛之历年真题分类汇编(2015-2021)

这是一份专题40排列组合与图论第三缉-备战2022年高中数学联赛之历年真题分类汇编(2015-2021)，文件包含专题40排列组合与图论第三缉解析版-备战2022年高中数学联赛之历年真题分类汇编2015-2021docx、专题40排列组合与图论第三缉原卷版-备战2022年高中数学联赛之历年真题分类汇编2015-2021docx等2份试卷配套教学资源，其中试卷共27页， 欢迎下载使用。
备战2022年高中数学联赛之历年真题分类汇编(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)