备战2021年高中数赛之历年真题汇编（1981-2020）
专题30图论与对策
历年联赛真题汇编
1．【2020高中数赛A卷（第02试）】给定凸20边形P.用P的17条在内部不相交的对角线将P分割成18个三角形,所得图形称为P的一个三角剖分图.对P的任意一个三角剖分图T,P的20条边以及添加的17条对角线均称为T的边.T的任意10条两两无公共端点的边的集合称为T的一个完美匹配.当T取遍P的所有三角剖分图时,求T的完美匹配个数的最大值.
2．【2019高中数赛B卷（第02试）】将一个凸2019边形的每条边任意染为红、黄、蓝三种颜色之一，每种颜色的边各673条.证明:可作这个凸2019边形的2016条在内部互不相交的对角线将其剖分成2017个三角形，并将所作的每条对角线也染为红、黄、蓝三种颜色之一，使得每个三角形的三条边或者颜色全部相同或者颜色互不相同.
3．【2017高中数赛A卷（第02试）】将33×33方格纸中每个小方格染三种颜色之一，使得每种颜色的小方格的个数相等.若相邻两个小方格的颜色不同，则称它们的公共边为“分隔边”试求分隔边条数的最小值.
4．【2016高中数赛（第02试）】给定空间中10个点，其中任意四点不在一个平面上将某些点之间用线段相连，若得到的图形中没有三角形也没有空间四边形，试确定所连线段数目的最大值.
5．【2011高中数赛（第02试）】设A是一个3×9的方格表，在每一个小方格内各填一个正整数.称A中的一个m×n(1≤m≤3，1≤n≤9)方格表为“好矩形”，若它的所有数的和为10的倍数.称A中的一个1×1的小方格为“坏格”，若它不包含于任何一个“好矩形”.求A中“坏格”个数的最大值.
6．【2010高中数赛（第02试）】一种密码锁的密码设置是在正n边形𝐴1𝐴2⋯𝐴𝑛的每个顶点处赋值0和1两个数中的一个，同时在每个顶点处涂染红、蓝两种颜色之一，使得任意相邻的两个顶点的数字或颜色中至少有一个相同.问：该种密码锁共有多少种不同的密码设置? 7．【2009高中数赛（第02试）】在非负数构成的3×9数表
𝑥11𝑃(𝑥21
𝑥31
𝑥12𝑥22𝑥32
𝑥13𝑥23𝑥33
𝑥14𝑥24𝑥34
𝑥15𝑥25𝑥35
𝑥16𝑥26𝑥36
𝑥17𝑥27𝑥37
𝑥18𝑥28𝑥38
𝑥19𝑥29) 𝑥39
中每行的数互不相同，前六列中每列的三个数之和为1，𝑥17=𝑥28=𝑥39=0，𝑥27,𝑥37,𝑥18,𝑥38,𝑥19,𝑥29均大于1.如果P的前三列构成的数表
𝑥11
𝑆=(𝑥21
𝑥31
𝑥12𝑥22𝑥32
𝑥13𝑥23) 𝑥33
𝑥1𝑘
满足下面的性质(O)：对于数表P中的任意一列(𝑥2𝑘)(𝑘=1,2,⋯,9)均存在某个i∈{1，2，3}使得𝑥𝑖𝑘⩽𝑢𝑖=
𝑥3𝑘min{𝑥𝑖1,𝑥𝑖2,𝑥𝑖3} 求证：
(i)最小值𝑢𝑖=min{𝑥𝑖1,𝑥𝑖2,𝑥𝑖3},𝑖=1,2,3一定取自数表S的不同列. 𝑥1𝑘∗𝑥11
(ii)存在数表P中唯一的一列(𝑥2𝑘∗),𝑘∗≠1,2,3使得3×3数表𝑆′=(𝑥21
𝑥3𝑘∗𝑥31
𝑥12
𝑥22𝑥32
𝑥1𝑘∗
𝑥2𝑘∗)仍然具有性质(O). 𝑥3𝑘∗
①
8．【2007高中数赛（第02试）】如图，在7×8的长方形棋盘的2个小方格的中心点各放1个棋子.如果2个棋子所在的小方格共边或共顶点，那么称这2个棋子相连.现从这56个棋子中取出一些，使得棋盘上剩下的棋子，没有5个在一条直线(横、竖、斜方向)上依次相连.问最少取出多少个棋子才可能满足要求?并说明理由.
9．【2002高中数赛（第02试）】在世界杯足球赛前，F国教练为了考察𝐴1,𝐴2,⋯,𝐴7，这七名队员，准备让他们在三场训练比赛(每场90分钟)都上场假设在比赛的任何时刻，这些队员中有且仅有一人在场上，并且𝐴1,𝐴2,𝐴3,𝐴4每人上场的总时间(以分钟为单位)均被7整除，𝐴5,𝐴6,𝐴7每人上场的总时间(以分钟为单位)均被13整除如果每场换人次数不限，那么按每名队员上场的总时间计算，共有多少种不同的情况.
10．【2001高中数赛（第02试）】将边长为正整数m，n的矩形划分成若干边长均为正整数的正方形，每个正方形的边均平行于矩行的相应边，试求这些正方形边长之和的最小值.
11．【2000高中数赛（第02试）】有n个人，已知他们中的任意两个人至多通电话一次，他们中的任意n－2个人之间通电话的总次数相等，都是3k次，其中k是自然数，求n的所有可能值.
12．【1999高中数赛（第02试）】给定正整数n，已知用克数都是正整数的k块砝码和一台天平可以称出质量为1，2，3，…，ng的所有物品. (1)求k的最小值f(n)；
(2)当且仅当n取什么值时，上述f(n)块砝码的组成方式是唯一确定的?并证明你的结论.
13．【1997高中数赛（第02试）】在100×25的长方形表格中每一格填入一个非负实数，第i行第j列中填入的数为x(i=1，2，…，100；j=1，2，…，25)(表1).然后将表1没列中的数按由大到小的次序从上到下重新排
′′′列为𝑥1,𝑗⩾𝑥2,𝑗⩾⋯⩾𝑥100,𝑗(𝑗=1,2,⋯,25)(表2).
求最小的自然数k，使得只要表1中填入的数满足∑𝑗=1𝑥𝑖,𝑗⩽1(𝑖=1,2,⋯100)，
25𝑗=1
′
𝑥1,𝑗⩽1 (𝑖=1,2,⋯100)成立.
25
则当i≥k时，在表2中就能保证∑
表1
𝑥1,1 𝑥2,1 ⋯ 𝑥1,2 𝑥2,2 ⋯ ⋯ ⋯ ⋯ 𝑥1,25 𝑥2,25 ⋯
𝑥100,1 表2
′𝑥1,1 ′𝑥1,2 𝑥100,2 ⋯ 𝑥100,25 ⋯ ⋯ ⋯ ⋯ ′𝑥1,25 ′𝑥2,1 ′𝑥2,2 ′𝑥2,25 ⋯ ′𝑥100,1 ⋯ ′𝑥100,2 ⋯ ′𝑥100,25
14．【1996高中数赛（第02试）】有n(n≥6)个人聚会，已知：
𝑛2
(1)每人至少同其中[]个人互相认识；
(2)对于其中任意[]个人，或者其中有2个人相识，或者余下的人中有2个人相识.
2
𝑛
证明：这n个人中必有3个人两两相识.
15．【1995高中数赛（第02试）】将平面上的每个点都以红，蓝两色之一着色.证明：存在这样两个相似的三角形，它们的相似比为1995，并且每一个三角形的三个顶点同色.
16．【1994高中数赛（第02试）】给定平面上的点集𝑃={𝑃1,𝑃2,⋯,𝑃1,994},𝑃中任三点均不共线，将P中的所有的点任意分成83组，使得每组至少有3个点，且每点恰好属于一组，然后将在同一组的任两点用一条线段相联结，不在同一组的两点不联结线段，这样得到一个图案G，不同的分组方式得到不同的图案，将图案G中所含的以P中的点为顶点的三角形个数记为𝑚(𝐺). (1)求m(G)的最小值m0.
(2)设G*是使m(G*)=m0的一个图案，若G*中的线段(指以P的点为端点的线段)用4种颜色染色，每条线段恰好染一种颜色，证明存在一个染色方案，使G*染色后不含以P的点为顶点的三边颜色相同的三角形.
17．【1990高中数赛（第02试）】某市有n所中学，第i所中学派出Ci名学生(1≤Ci≤39，1≤i≤n)来到体育馆
观看球赛，全部学生总数为∑𝑛𝑖=1𝐶𝑖=1990.看台上每一横排有199个座位.要求同一学校的学生必须坐在同一横排，问体育馆最少要安排多少个横排才能够保证全部学生都能坐下?
18．【1987高中数赛（第02试）】.n(n>3)名乒乓球选手单打比赛若干场后，任意两个选手已赛过的对手恰好都不完全相同，试证明：总可以从中去掉一名选手，而使在余下的选手中，任意两个选手已赛过的对手仍然都不完全相同.
19．【1986高中数赛（第02试）】平面直角坐标系中，纵、横坐标都是整数的点称为整点.请设计一种方法将所有的整点染色，每一个整点染成白色、红色或黑色中的一种颜色，使得：
(1)每一种颜色的点出现在无穷多条平行于横轴的直线上；
(2)对任意白点A、红点B和黑点C，总可以找到一个红点D，使得四边形ABCD为一个平行四边形. 证明你设计的方法符合上述要求.
20．【1985高中数赛（第02试）】某足球邀请赛有16个城市参加，每市派出甲、乙两个队.根据比赛规则，每两队之间至多赛一场，并且同一城市的两队之间不进行比赛.比赛若干天后进行统计，发现除A市甲队外，其他各队已比赛过的场数各不相同.问A市乙队已赛过多少场?请证明你的结论.
21．【1981高中数赛（第02试）】组装甲、乙、丙三种产品，需用A，B，C三种零件.每件甲需用A，B各2个；每件乙需用B，C各1个；每件丙需用2个A和1个C.用库存的A，B，C三种零件，如组装成P件甲产品、q件乙产品和r件丙产品，则剩下2个A和1个B，但C恰好用完.试证:无论怎样改变甲、乙、丙的产品件数，也不能把库存的A，B，C三种零件都恰好用完.
优质模拟题强化训练
1．我们知道，目前最常见的骰子是六面骰，它是一颗正立方体，上面分别有一到六个洞(或数字)，其相对两面之数字和必为七.显然，掷一次六面骰，只能产生六个数之一(正上面).现欲要求你设计一个“十进制骰”，使其掷一次能产生0~9这十个数之一，而且每个数字产生的可能性一样.请问：你能设计出这样的骰子吗?若能，请写出你的设计方案；若不能，写出理由.
2．在9×9的方格表中取出46个方格染成红色.证明：存在一块由4个方格构成的2×2区域，其中由至少3个方格被染成红色.
3．用电阻值分别为𝑎1、𝑎2、𝑎3、𝑎4、𝑎5、𝑎6(𝑎1>𝑎2>𝑎3>𝑎4>𝑎5>𝑎6)的电阻组装成一个如图的组件，在组装中应如何选取电阻，才能使该组件总电阻值最小？证明你的结论.
4．设V是空间中2019个点构成的集合，其中任意四点不共面某些点之间连有线段，记E为这些线段构成的集合.试求最小的正整数n，满足条件：若E至少有n个元素，则E一定含有908个二元子集，其中每个二元子集中的两条线段有公共端点，且任意两个二元子集的交为空集.
5．设n为正整数，称n×n的方格表Tn的网格线的交点(共(n+1)2个交点)为格点.现将数1，2，……，(n+1)2分配给Tn的所有格点，使不同的格点分到不同的数.称Tn的一个1×1格子S为“好方格”，如果从2S的某个顶点起按逆时针方向读出的4个顶点上的数依次递增(如图是将数1，2，…，9分配给T2的格点的一种方式，其中B、C是好方格，而A、D不是好方格)设Tn中好方格个数的最大值为f(n).
（1）求f(2)的值；
（2）求f(n)关于正整数n的表达式.
𝑚𝑛2
6．设𝐴是一个由0和1构成的𝑚行𝑛列的数表，且𝐴中所有数字之和不小于，所有这样的数表构成的集合记为𝑆(
𝑚,𝑛)，记𝑅𝑖(𝐴)为𝐴的第𝑖行各数之和(1≤𝑖≤𝑚)，𝐶𝑗(𝐴)为𝐴的第𝑗列各数之和(1≤𝑗≤𝑛)，𝐾(𝐴)为𝑅1(𝐴)、𝑅2(𝐴)、⋯，𝑅𝑚(𝐴)、𝐶1(𝐴)、𝐶2(𝐴)、⋯、𝐶𝑛(𝐴)中的最大值.
（1）对如下数表𝐴，求𝐾(𝐴)的值；
1 1 0 0 0 0 1 1
（2）设数表𝐴∈𝑆(4,4)，求𝐾(𝐴)的最小值；
（3）已知𝑡为正整数，对于所有的𝐴∈𝑆(6,𝑡)，𝑅𝑖(𝐴)=5 (1≤𝑖≤6)，且𝐴的任意两行中最多有2列各数之和为2，求𝑡的值.
7．求正整数n的最大值，使得对任意一个以𝑉1,𝑉2,⋯,𝑉𝑛为顶点的n阶简单图，总能找到集合{1,2,⋯,2014}的n个子集𝐴1,𝐴2,⋯,𝐴𝑛，满足：𝐴𝑖∩𝐴𝑗≠∅(𝑖≠𝑗)当且仅当𝑉𝑖与𝑉𝑗相邻.
8．已知有n(n≥4)支足球队参加单循环赛，每两队赛一场，每场胜方得3分，负方得0分，平局各得1分，所有比赛结束后发现，各队的总分构成公差为1的等差数列，求最后一名得分的最大值。
9．一次循环赛中有2n+1支参赛队，其中每队与其他队均只进行一场比赛，且比赛结果中没有平局。若三支参赛队A、B、C满足：A击败B，B击败C，C击败A，则称它们形成一个“环形三元组”。求： （1）环形三元组的最小可能数目； （2）环形三元组的最大可能数目。
10．（1）构造一个元素都是整数的2×2矩阵，使得其每一行的和与每一列的和这四个数是互不相同的完全平方数；（2）构造一个元素都是整数的3×3矩阵，使得其每一行的和与每一列的和这六个数是互不相同的完全平方数；（3）构造一个元素都是整数的4×4矩阵，使得其每一行的和与每一列的和这八个数是互不相同的完全平方数.
11．某国建了一座时间机器，形似一条圆形地铁轨道，其上均匀设置了2014个站台（编号依次为l，2，…，2014）分别对应一个年份，起始站及终点站均为第1站（对应2014年）.为节约成本，机器每次运行一圈，只在其
中一半的站台停靠，出于技术原因，每次至多行驶三站必须停靠一次，且所停靠的任两个站台不能是圆形轨道的对径点.试求不同的停靠方式的种数.
12．设𝑛≥4，𝑀为三维空间中𝑛个点组成的有限集，其中任意四点不在一个平面上，将集合𝑀中的点染成白色或黑色，使得任意一个与集合𝑀至少交于四个点的球面具有这样的性质：这些交点中恰有一半的点为白色的.证明：集合𝑀中所有的点均在一个球面上，
13．在正2018边形的每两个顶点之间均连一条线段，并把每条线段染成红色或蓝色.求此图形中三边颜色都相同的三角形的最小个数.
14．某国有53座城市，任意两座城市之间要么有一条双向公路直达，要么没有直接相连的公路。已知这53座城市之间共有312条公路，并且由任何一座城市出发通过公路均能到达其余各城市。每一座城市至多向其余12座城市引出公路，且每走一条公路需要缴纳10元路费。现甲在城市A，且身上仅有120元。甲是否一定能到达任意一座城市？证明你的结论。
15．平面上有任意三点不共线的12个点，以其中任意一点为始点，另一点为终点作向量，且作出所有这样的向量.若三边向量和为零向量，则称该三角形为“零三角形”，求以这12个点为顶点的零三角形个数的最大值. 16．在平面直角坐标系𝑥𝑂𝑦中,有一个微型智能机器人（大小不计）只能沿着坐标轴的正方向或负方向行进,且每一步只能行进1个单位长度,例如：该机器人在点(1,0)处时,下一步可行进到(2,0)、(0,0)、(1,1,)、(1,−1)这四个点中的任一位置．记该机器人从坐标原点𝑂出发、行进𝑛步后落在𝑦轴上的不同走法的种数为𝐿(𝑛)． （1）分别求𝐿(1)、𝐿(2)、𝐿(3)的值； （2）求𝐿(𝑛)的表达式．
17．出租车几何学是由十九世纪的赫尔曼·闵可夫斯基所创立的。在出租车几何学中，点还是形如(𝑥,𝑦)的有序实数对，直线还是满足𝑎𝑥+𝑏𝑦+𝑐=0的所有(𝑥,𝑦)组成的图形，角度大小的定义也和原来一样，直角坐标系内任意两点𝐴(𝑥1,𝑦1),𝐵(𝑥2,𝑦2)定义它们之间的一种“距离”：|𝐴𝐵|=|𝑥1−𝑥2|+|𝑦1−𝑦2|，请解决以下问题： （1）求线段𝑥+𝑦=4(𝑥≥1,𝑦≥2)上一点𝑀(𝑥,𝑦)到点𝑁(1,2)的“距离”；
（2）定义：“圆”是所有到定点“距离”为定值的点组成的图形，求“圆”上的所有点到点𝑄(𝑎,𝑏)的“距离”均为𝑟的“圆”方程，并求该“圆”围成的图形的面积；
（3）若点𝐶(𝑥,𝑦)到点𝐴(1,3)的“距离”和点𝐶(𝑥,𝑦)到点𝐵(6,9)的“距离”相等，其中实数𝑥,𝑦满足0≤𝑥≤10,0≤𝑦≤10，求所有满足条件的点𝐶的轨迹的长之和.
18．设𝑦2=2𝑛+1𝑥（n = 1，2，3，…，2000）为一族抛物线，分别过每条抛物线的焦点作倾斜角为45°的直线，并截该抛物线得弦𝐴𝑛𝐵𝑛（n = 1，2，3，…，2000），将各弦绕其对应准线旋转90°得到2000个旋转面.试求所有这些旋转面面积之和.
19．在直角坐标系中，有三只青蛙A、B、C，其起始位置分别为𝐴0(4,6)、𝐵0(−√5−2,−√5−3),𝐶0(6+√5,9+√5)，首先，A以B为中心跳到其对称点上，然后，B以C为中心跳到其对称点上，接着，C以A为中心跳到其对称点上，……依此类推。设A、B、C第n次跳到的位置分别为𝐴𝑛、𝐵𝑛、𝐶𝑛，𝛥𝐴2011𝐵2011𝐶2011的三边长分别为a、b、c，面积为S。证明:𝑎2+𝑏2+𝑐2>300×172017𝑆
20．在一次数学竞赛中，某些选手是朋友关系.记所有选手的集合为X，对集合X的子集Y，若可以将这些人两两分组，且每组中两名选手均是朋友关系，则称子集Y“可两两分组”.已知集合X不可两两分组，且对于任意选手𝐴、𝐵∈𝑋，若A、B不是朋友关系，则𝑋\\{𝐴,𝐵}可两两分组，且X中没有一个人与其他所有人均为朋友关系证明:对任意选手𝑎、𝑏、𝑐∈𝑋，若a、b为朋友关系，b、c为朋友关系，则a、c也为朋友关系
