2022年高中数学联赛组合专题 .docx

精品_精品资料_课程简介： 全国高中数学联赛是中国高中数学学科的最高等级的数学竞赛,其位置远高于各省自行组织的数学竞赛.在这项竞赛中取得优异成果的全国约90 名同学有资格参与由中国数学会主办的“中国数学奥林匹克 CMO暨全国中同学数学冬令营”.优胜者可以自动获得各重点高校的保送资 格.各省赛区一等奖前6 名可参与中国数学奥林匹克,获得进入国家集训队的时机.中学校训练网重磅推出“全国高中数学联赛”辅导课程,无论是有意向参与竞赛的初学者,仍是已入围二试的竞赛选手,都有适合的课程供应.本套课程由中国数学奥林匹克高级教练熊斌、人大附中数学老师李秋生等名师主讲,轻松突破你的数学极限；课程招生简章：:/g12e/webhtml/project/liansaigz.shtml选课中心的址：:/member.g12e/selectcourse/commonCourse.shtm.courseeduid=170037#_170037_其次章组合专题一、重要的概念与定理1、完全图：每两个顶点之间均有边相连的简洁图称为完全图, 有 个顶点的完全图阶完全图记为.2、顶点的度：图中与顶点相关联的边数环按2 条边运算称为顶点的度或次数 ,记为.与分别表示图的顶点的最小度与最大度. 度为奇数的顶点称为奇顶点, 度为偶数的顶点称为偶顶点.3、树：没有圈的连通图称为树, 用表示 , 其中度为 1 的顶点称为树叶或悬挂点.阶树常表示为.4、部图：假设图的顶点集可以分解为个两两不相交的非空子集的并, 即并且同一子集内任何两个顶点没有边相连, 就称这样的图为部图 , 记作. 2部图又叫做偶图 , 记为.5、完全部图：在一个部图中, 假设对任意均有边连接和, 就称图为完全部图 , 记为.6、欧拉迹：包含图中全部边的迹称为欧拉迹. 起点与终点重合的欧拉迹称为闭欧拉迹.欧拉图：包含欧拉迹的图为欧拉图.欧拉图必是连通图 .哈密顿链圈：经过图上各顶点一次并且仅仅一次的链圈称为哈密顿链圈. 包含哈密顿圈的图称为哈密顿图.7、平面图：假设一个图可画在平面上 , 即可作一个与同构的图, 使的顶点与边在同可编辑资料 - - - 欢迎下载精品_精品资料_一平面内 , 且任意两边仅在端点相交, 就图称为平面图 .一个平面图的顶点和边把一个平面分成假设干个相互隔开的区域, 称为平面图的一个面 , 在全部边的外面的面称为外部面, 其余的称为内部面 .8、竞赛图：有向完全简洁图称为竞赛图. 有 个顶点的竞赛图记作.9、有向路： 在有向图中, 一个由不同的弧组成的序列, 其中的起点为, 终点为, 称这个序列为从到的有向路简称路 ,为这个路的长 ,为路的起点 ,为路的终点 . 假设, 就称这个路为回路.可编辑资料 - - - 欢迎下载精品_精品资料_定理 1 设是 阶图, 就中 个顶点的度之和为边数的2 倍.定理 2 对于任意图, 奇顶点的个数肯定是偶数.定理 3Turan 定理 有 个顶点且不含三角形的图的最大边数为.定理 4 图为偶图 , 当且仅当中不含长度为奇数的圈 . 定理 5 假设树的顶点数, 就中至少有两个树叶. 定理 6 假设数有 个顶点 , 就的边数.定理 7 设是有个顶点、条边的图 , 就以下命题等价 : 图是树; 图无圈 , 且; 图连通 , 且.定理 8阶连通图中以树的边数最少, 且 阶连通图必有一个子图是树.定理 9一笔画定理有限图是一条链或圈可以一笔画成的充要条件是是连通的 , 且奇顶点的个数为 0 或 2.当且仅当奇顶点个数为0 时, 连通图是一个圈 .定理 10 在偶图中, 假设, 就肯定无哈密顿圈 . 假设与的差大于 1, 就肯定无哈密顿链 .定理 11 设是阶简洁图 , 且对每一对顶点有, 就图有哈密顿链 .定理 12 设是阶简洁图 , 且对每一对不相邻的顶点有, 就图可编辑资料 - - - 欢迎下载精品_精品资料_有哈密顿圈 .定理 13 设是阶简洁图 , 假设每个顶点的度, 就图有哈密顿圈 .定理 14 假设图有哈密顿圈 , 从中去掉假设干个点及与它们关联的边得到图, 就图的连通分支不超过个.定理 15欧拉公式 假设一个连通的平面图有 个顶点、条边、个面 , 就定理 16 一个连通的平面简洁图有个顶点、条边, 就, 对于连通的偶图 , 就有.定理 17 一个图是平面图当且仅当它不包含同胚于或的子图 .定理 18 设 阶竞赛图的顶点为, 就, 且.定理 19 竞赛图中出度最大的点称为“优点” , “优点”到其余各点都有长度不超过2 的链 .定理 20 竞赛图中存在一条长为的哈密顿路 .定理 21 竞赛图中有一个回路是三角形的充要条件是有两个顶点满意.定理 22Ramsey定理 任意 2 色完全图中必存在同色三角形 .可编辑资料 - - - 欢迎下载精品_精品资料_二、例题选讲例 1 、某天晚上 21 个人之间通了,有人发觉这 21 人共通话 102 次, 且每两人至多通话一次.他仍发觉 , 存在个人 , 第 1 个人与第 2 个人通了话 , 第 2 个人与第 3 个人通了话 , ,第个人与第个人通了话 , 第个人又与第 1 个人通了话 , 他不愿透露的详细值 , 只说是奇数 . 求证 : 21 个人中必存在 3 人, 他们两两通了话.可编辑资料 - - - 欢迎下载精品_精品资料_例 2、45 个校友聚会 , 在这些人中 , 任意两个熟人数目相同的校友互不熟悉. 问在参与校友聚会的全部人中 , 熟人最多的人的数目最多是多少.可编辑资料 - - - 欢迎下载精品_精品资料_1. 平面上的 n 4个点中,任何 4 个点都是凸四边形的顶点.证明这n 个点是一个凸 n 边形的顶点.可编辑资料 - - - 欢迎下载精品_精品资料_2. 平面上有两条线段AB和 CD使得 ABDC是平行四边形.我想把AB在平面上连续的移动直到 A 与 C重合, B 与 D重合.证明：不管这两条线段多长,也不管它们相距多远,我总可以使得在平移的过程中AB扫过的总面积小于1.3. 证明: 平面上任意 n正整数个点能被满意以下条件的有限个圆盘圆盘包含边界掩盖:它们直径之和小于n,而且任何两个圆盘之间的距离指这两个圆盘上各取一点的最小距离都大于 1.可编辑资料 - - - 欢迎下载精品_精品资料_4. 在平面直角坐标系中,求全部满意以下条件的过原点的直线l : 对于任意实数a,b 以及d > 0,都存在整数 m,n 和 l 上的点P使得 a + m,b + n和 P的距离小于d.可编辑资料 - - - 欢迎下载精品_精品资料_5. 证明: 任给正整数 n,总存在正整数 K 使得下面的结论成立 : 假如平面上 K个点中没有三点共线,那么这些点中必定存在n 个点是一个凸n 边形的顶点.可编辑资料 - - - 欢迎下载精品_精品资料_6. 一个矩形 R被切成了假设干个内部不相交的而且拼起来恰好是整个 R的小矩形,这些小矩形的边都与 R的边平行或垂直,而且每个小矩形至少有一条边长为整数.证明： R也至少有一条边长为整数.可编辑资料 - - - 欢迎下载精品_精品资料_7. 平面上的点集S 中有有限个不全共线的点,它们被染成红和蓝两种颜色.证明: 存在一条直线使得它过 S 中至少两个点,而且S 中在这条直线上的全部点都是同一种颜色.可编辑资料 - - - 欢迎下载精品_精品资料_1. 试求 n 项的没有两个或以上连续的0 的 0,1 序列的个数.2. m,n 是正整数 . 证明 : 每个由 mn+1个不同实数组成的数列肯定有一个m+1项递增子序列或者一个 n+1项递减子序列.3. 正整数 n 的一个分拆是指把n 分成假设干个正整数不计次序之和. 证明对于任意正整数n,n 的分成每部分都是奇数的分拆个数等于n 的分成每部分互不相同的分拆个数.可编辑资料 - - - 欢迎下载精品_精品资料_4.n 是给定正整数 . 将 n 个黑子和 n 个白子任意放在一个圆周上. 从某个白子起 , 按顺时针方向依次将全体白子标上1,2, n, 再从某个黑子起 , 按逆时针方向依次将全体黑子标上1,2, n. 证明 : 在圆周上必可以找到连续n 个棋子 , 使得它们标号所成的集合恰好为1, 2, n.可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_5. 设 n 和 k 是正整数 , 且 k n 是非负偶数 . 有 2n 盏灯依次编号为1,2, 2n, 每一盏灯可以开和关 . 开头时全部的灯都是关的,现在要对这些灯进行k 次操作 , 每次操作转变且只转变一盏灯的开关状态 . 用 N 表示满意“k 次操作以后灯 1,2, n 是开的 , 其它灯都是关的”的不同操作序列总数 , 用 M表示满意“k 次操作以后灯1, 2, n 是开的 , 其它灯都是关的而且从来没有被开过”的不同操作序列总数. 试求比值.可编辑资料 - - - 欢迎下载精品_精品资料_6. 给定 n, k 是正整数 ,. 假设 F 是 1,2, n的子集族 , 假如 F 中的每个集合都有k个元素 , 而且 F 中任何两个集合都相交非空, 那么 F的最大可能值是多少.可编辑资料 - - - 欢迎下载精品_精品资料_7. 有 12 个人 , 其中任何 9 人中都有 5 人两两熟悉 . 证明 : 这 12 人中必有 6 人两两熟悉.可编辑资料 - - - 欢迎下载精品_精品资料_【学问储备】可编辑资料 - - - 欢迎下载精品_精品资料_【例题精讲】1.p 1是实数, n 是正整数 . 证明闵可夫斯基不等式：任给实数a1,a2.,b1,b 2,.,bn, 必有：可编辑资料 - - - 欢迎下载精品_精品资料_2. 假如函数 f ：ZR满意：存在正数 M使得对于任意正数a 和正整数 d,这里 I=a-d,a+d,表示 f 在 I 上的平均值,那么就称f 是 BMO的, M就称为 f 的一个 BMO模长 . 证明存在正的常数C,使得对于任何 BMO的函数 f ,只要 M是 f 的一个 BMO模长,就有对任何正数a 和正整数 d,可编辑资料 - - - 欢迎下载精品_精品资料_3. 设 n 是给定的正整数 .S=1,2,n. 求|A S|+|B S|+|C S| 的最小值. 这里 A,B 是非空有限实数集合, C=A+B=x+y|xA,y B.X Y 表示由恰好属于 X,Y 中一个的元素组成的集合.可编辑资料 - - - 欢迎下载精品_精品资料_4. 证明存在正的常数C,使得平面直角坐标系中的任意有限个边平行于坐标轴的正方形中必能挑出一些正方形两两内部无公共点,而且他们掩盖的总面积不小于全体正方形掩盖总面积的C倍.5. 设 A 是一个有限实数集 .A 1,A 2, ,A n 是 A 的非空子集,且满意：i A 中全部元素之和为0.ii对任意 x i Ai i=1,2 , ,n , 都成立. 证明 : 存在 1i1<i 2<<i kn使得可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_6. 设 m和 n 是给定的正整数, 4<m<n.A1A2A2n+1 是一个正 2n+1边形, P=A1, A 2, A2n+1 .求顶点属于 P 且恰有两个内角是锐角的凸m边形个数 .可编辑资料 - - - 欢迎下载精品_精品资料_7. 将全体正整数用红或蓝进行二染色. 证明：存在一列无穷个递增正整数a1,a 2,a 3, 使得全都是同色的正整数 .可编辑资料 - - - 欢迎下载精品_精品资料_8. 假如平面上的有限 1个非零向量形成的集合R 满意以下三个条件就称R 为一个根系： i 任两个向量 a,bR,是整数. ii 任两个向量 a,bR,R. iii假如 R 中两个向量共线,那么他们或者相等或者和为0. 试求平面上全部可能的根系.可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载精品_精品资料_可编辑资料 - - - 欢迎下载