专题03 高中数学竞赛二试内容——组合数学（竞赛培优专项训练,11大考点+强基竞赛）高二数学人教A版全国通用

专题03 高中数学竞赛二试内容——组合数学 目录概览 A考点精研・竞赛考点专项攻坚 考点一 抽屉原理 2 考点二 极端原理 7 考点三 算两次原理 9 考点四 对策问题 11 考点五 容斥原理 14 题型六 递推问题 17 题型七 母函数法 21 题型八 组合几何 23 题型九 对策问题 31 题型十 图论 34 题型十一 染色问题 42 B实战进阶・竞赛选拔模拟特训（精选各地竞赛、强基试题11道） 【归纳重点知识】 1．定理1（容斥原理）（也称逐步淘汰公式）设是的子集，则 ． 定理2（容斥原理的对偶形式）设是的子集，则 （因为，所以） 2．极端原理 极端原理就是通过讨论“极端”对象来解题的方法，它考虑的是极端情况——最大或最小. 因此，它往往在题目中增加一个（最大或最小）条件，从而使问题巧妙地得以解决.同时， 它常跟反证法结合，通过与“最大”与“最小”的矛盾来解决问题. 通常考虑的极端情况，可以是边最长（最短），最大数（或最小数）等，其在不等式、不定方程、图论及一些组合问题（特别是一些存在性问题）中都经常被用到. 3.抽屉原理 (1)第I型抽屉原理：把个物体放入个抽屉，则至少有一个抽屉的物品不少于个，其中 (2)第II型抽屉原理：把个物体放入个抽屉，则至少有一个抽屉的物品不多于个，其中 4．基本的组合恒等式 简单的组合恒等式的化简和证明，可以直接运用课本所学的基本组合恒等式.事实上，许多竞赛中出现的较复杂的组合数记算或恒等式证明，也往往运用这些基本组合恒等式，通过转化，分解为若干个简单的组合恒等式而加以解决.常见的组合恒等式有： ①； ②； ③； ④； ⑤； ⑥ 考点一 抽屉原理 1．设有限集，对任意，定义．证明以下结论： (1)存在，使得； (2)．其中表示集合中的元素个数，． 【答案】(1)证明见解析 (2)证明见解析 【解析】（1）， 则由抽屉原理知，存在，使得． （2）由柯西不等式得 所以. 2．请阅读以下材料并完成以下问题： 【材料一】范数是定义在向量空间上的一个函数，它为向量空间中的每个向量赋予一个非负的实数值，直观上可以理解为向量的“长度”或“大小”. -范数：在维向量空间中，向量的-范数定义为，其中.如当时，得到1-范数，即，它表示向量各个分量绝对值之和，例如. 再以常见的二维欧几里得空间为例，对于向量，其欧几里得范数（也称为2-范数）定义为，这正是我们熟悉的从原点到向量终点的直线距离，符合我们对向量长度的直观认知. 【材料二】桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果.这一现象就是我们所说的“抽屉原理”. 抽屉原理是德国数学家狄利克雷（P.G.T.Dirichlet，1805~1859）首先提出来的，也称狄利克雷原理.抽屉原理的一般含义为：如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有个元素放到个集合中去，其中必定有一个集合里至少有两个元素. 【材料三】在维向量空间中，对，其中，，定义. (1)若，且，其中，；记为奇数的向量个数为. ①求； ②求（用含的式子表示，其中）； (2)若正整数，若定义集合，其中，，，且；请求出的元素个数；若已知，满足对任意，都有，求的最大值. 【答案】(1)①，；② (2)的元素个数为.的最大值为4. 【解析】（1）①当时，，则的个数为1， 根据乘法原理. 当时，范数为奇数，则的个数为偶数，即0的个数为0，2， 根据乘法原理和加法原理得到. ②当为偶数时，为奇数，则的个数为奇数，即0的个数为， 根据乘法原理和加法原理得到， ， ， 两式相减得到； 当为奇数时，范数为奇数，则的个数为偶数，即0的个数为， 根据乘法原理和加法原理得到， ， ， 两式相加得到. 综上所述：. （2）由题：（1）由，且，故， 中6个分量中恰有3个1， 的元素个数为. 又由，由集合元素互异性，，故可取， 若要满足条件，则中恰有一个相同位置的元素均为1. 猜想：列举其中一种， 若，则， ，， 而此时前面三位均已不可站位，由抽屉原理，不管怎么选都不能满足题意，故的最大值为4. 下证若，则中有三个分量为1，但要求中都恰好有一个分量与相同， 则由抽屉原理，必然有一个位置有两个分量与之相同， 即中至少有两个向量在相同的位置与有相同的分量1； 不妨设的第一个分量为1，此时的剩余6个分量要分配在5个不同的位置里， 但由抽屉原理，中至少有两个向量在两个相同的位置都有1， 不妨设这两个向量为，则， 与题设：“对任意，都有”矛盾，故. 当时， 令，满足题意. 故的最大值为4. 另解：由题：由，且，故中6个分量中恰有3个1， 故的元素个数为. 对于的非空子集. 设，这里是的第个分量， 定义，规定， 设， 令， 我们先证明引理：. 反证法：，令， 设满足，其中， ，即：，且， ，这与矛盾，引理证毕. 回到原题，由引理，解得， ， ，符合题意， 综上，当时，的最大值为4. 3．设为不小于3的正整数，集合满足.设为平面，点，对任意，点，且点满足. (1)若，且，求直线与所成角的大小； (2)证明：； (3)对任意，规定.设点满足.证明：存在，使得对任意，都有，或且与在的不同侧. 【答案】(1)； (2)证明见解析； (3)证明见解析. 【解析】（1）由已知，是等边三角形，且平面， 以为坐标原点，分别以、所在直线为轴、轴建立空间直角坐标系，如图，    设，则， 所以， 又平面的法向量为，设直线与平面所成角为， 则，因为，所以. （2）， 所以，即，因为，所以. （3）由知，具有周期， 对，若， 当时，由（2）得； 当时，由周期性的符号（相对于）一致，故与始终在的不同侧； 由抽屉原理，因，则必，使，都有，或且与始终在的不同侧. 考点二 极端原理 4．设集合是由平面上任意三点不共线的4039个点构成的集合，且其中2019个点为红色，2020个点为蓝色；在平面上画出一组直线，可以将平面分成若干区域，若一组直线对于点集满足下述两个条件，称这是一个“好直线组”： （1）这些直线不经过该点集中的任何一个点； （2）每个区域中均不会同时出现两种颜色的点. 求的最小值，使得对于任意的点集，均存在由条直线构成的“好直线组”. 【答案】. 【解析】先证明： 在一个圆周上顺次交替标记2019个红点和2019个蓝点，在平面上另外任取一点染为蓝色，这个圆周就被分成了4038段弧，则每一段的两个端点均染了不同的颜色； 若要满足题目的要求，则每一段弧均与某条画出的直线相交； 因为每条直线和圆周至多有两个交点，所以，至少要有条直线. 再证明：用2019条直线可以满足要求. 对于任意两个同色点，均可用两条直线将它们与其他的点分离. 作法：在直线的两侧作两条与平行的直线，只要它们足够接近，它们之间的带状区域里就会只有和这两个染色点. 设是所有染色点的凸包，有以下两种情形： （1）假设有一个红色顶点，不妨记为.则可作一条直线，将点和所有其他的染色点分离，这样，余下的2018个红点可以组成1009对，每对可以用两条平行直线将它们与所有其他的染色点分离.所以，总共用2019条直线可以达到要求. （2）假设的所有顶点均为蓝色.考虑上的两个相邻顶点，不妨记为.则用一条直线就可以将这两个点与所有其他染色点分离.这样，余下的2018个蓝点可以组成1009对，每对可以用两条直线将它们与所有其他染色点分离. 所以，总共也用了2019条直线可以达到要求. 综上：的最小值为2019. 5．名乒乓球选手单打比赛若干场后，任意两个选手已赛过的对手恰好都不完全相同.试证明：总可以从中去掉一名选手，而使在余下的选手中，任意两个选手已赛过的对手仍然都不完全相同. 【解析】本题是纯逻辑推理题，用集合记号配以图示易于叙述和证明. 设有n个选手，与他们进行过比赛的对手集合分别记作.显然，，且若，必.又由题意. 设是赛过场次最多的选手（即最大）. 若不存在可去选手，则不是可去对手，于是对存在，使当去掉后，与赛过的对手集合相同.又由，不仿设，从而.同理，对存在，使，而（如图所示）（* *）. 由 . 又若与（* *）矛盾.从而可得， 与最大矛盾.故命题得证. 6．一个由空间中的点组成的集合满足性质：中任意两点之间的距离互不相同．假设中的点的坐标都是整数，并且、、．证明：集合的元素个数小于． 【解析】记．因为满足、、的整点之间的距离不超过与之间的距离，所以，对任意的、，都有． 依题意知，中任意两点之间的距离互不相同，故，即． 于是，（最后一个不等式等价于，展开后移项即可得到）． 另一方面，对中的任意两点、，考虑集合（允许出现重复元素），其中，，，． 依题意知，所得的两两不同，且、、，、、不全为0． 于是，    ．                ① 故．解得． 当时，有． 事实上，只需证明： ， 展开后移项即可知此不等式在时成立． 于是，当时，总有．        ② 而当时，；当时，由式①知．此两种情况下，式②仍成立． 考点三 算两次原理 7．已知集合. (1)“算两次”思想在组合数学中有着重要应用．例如：对于一个元集合的所有子集个数，一方面有，另一方面：对于所有子集，每个中的元素有“出现”和“不出现”两种选择，由分布计数原理可得，因此有．令，试用算两次思想化简； (2)对于的子集个数还可以这样理解：，展开式中每一项都唯一对应着的一个子集．令，试化简； (3)对偶原理也是组合数学的重要方法，例如数学王子高斯小时候在计算的值时，他把与配对，与配对，从而化变量为常量，大大简化了计算．这其实就是对偶原理的一种体现．令，其中是中元素从小到大的一个排列，试用对偶原理化简. 【答案】(1) (2) (3) 【解析】（1）对任意，的包含的子集数目与集合的全体子集数目一一对应，共有个. 所以，将展开成若干项的求和后，每个在表达式中都出现次. 这就得到. （2）对集合，由于的展开式中，除第一项的外，每一项都唯一对应着的一个子集的各个元素的乘积. 故. 特别地取，就有，. （3）将的子集分为两类：第一类是不包含元素的子集，第二类是包含元素的子集. 那么第一类和第二类子集之间可以实现一一对应：将任意一个第一类子集添加元素，就得到一个第二类子集；将任意一个第二类子集去掉元素，就得到一个第一类子集. 设是一个第一类子集，它对应一个第二类子集. 那么求和式中的每一项在的求和式中都以符号相反的状态出现，若计算，则这些项两两抵消，只剩下的第一项. 所以每对对应的第一类子集和第二类子集都满足. 而的子集共有个，故一共有个这样的对应，所以. 【点睛】关键点点睛：本题的关键点在于用不同的方式计算同一个变量，以得到相应的恒等式，这就是经典的算二次方法或富比尼原理. 8．数学家波利亚说：“为了得到一个方程，我们必须把同一个量以两种不同的方法表示出来，即将一个量算两次，从而建立相等关系”这就是算两次原理，又称为富比尼原理.例如：如图甲，在△ABC中，D为BC的中点，则，，两式相加得，.因为D为BC的中点，所以，于是.请用“算两次”的方法解决下列问题： (1)如图乙，在四边形ABCD中，E，F分别为AD，BC的中点，证明：. (2)如图丙，在四边形中，E，F分别在边AD，BC上，且，，，，与的夹角为，求向量与向量夹角的余弦值. 【答案】(1)证明见解析； (2). 【分析】（1）利用图形关系的向量运算法则结合已知求解即可； （2）由图形关系的向量运算得到，求出其模长；再利用定义式求解，最后再利用向量夹角的余弦公式求解即可. 【解析】（1）证明：在四边形ABFE中，，① 在四边形CDEF中，，② 由①②，得， 因为E，F分别为AD，BC的中点， 所以，， 于是. （2）在四边形ABFE中，①， 在四边形CDEF中，②， 由，， 得，. 由，得，   所以， 所以， ， 所以. 考点四 对策问题 9．甲、乙两人分别进行投硬币和掷图钉试验，每人各进行100次试验．设为前k次试验中硬币正面向上的次数，为前k次试验中图钉针尖朝下的次数，记． (1)若，问是否存在常数P，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有P的可能值；若不存在，请说明理由； (2)若，问是否存在常数Q，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有Q的可能值；若不存在，请说明理由． 【答案】(1)不存在；理由见解析 (2)存在，或． 【解析】（1）不存在，先考虑最后50次试验硬币正面向上，则对应的均小于0.5． 再考虑第2次至第51次试验硬币正面向上，则对应的均大于等于0.5． 这与最后50次试验硬币正面向上的情形没有公共的取值，故这样的P不存在. （2）存在，或，先考虑最后70次试验针尖向下，则对应的均小于0.7． 再考虑第2次至第71次试验针尖向下， 则对应的分别为， 所以符合要求的Q只可能取． 下证对，必存在时，使得． 设， 若第k次试验针尖朝上，则，则 ； 若第k次试验针尖朝下，则，则 当时，． 所以由介值性定理知，必存在，使得，即，得证． 10．在一张无限大的方格表上的每个方格中填有一个实数．已知任意一个由格线构成的正方形中的数之和的绝对值不超过1．证明：任意一个由格线构成的矩形中的数之和的绝对值不超过4． 【答案】证明见解析. 【解析】反证法．假设有一个由格线构成的矩形中的数值和的绝对值为．设其两边长为a，b且，则显然，否则该矩形可以切割成两个小正方形，两个小正方形中数之和的绝对值均不超过2，从而矩形中的数值和不超过2，矛盾. （1），设． 不妨设，对有．同理，． 而， 于是， 于是．同理，． 又，因此， 故，并且这是一个的矩形中数之和． （2），不妨设． 由，于是，于是． 又，即 ， 于是．同理． 从而， 且这是一个的矩形． 从而综合（1），（2）可知，如果有矩形中数之和绝对值为， 则．且时存在一个的矩形中数之和绝对值至少时存在一个矩形中数之和绝对值至少． 考虑： , 令． 我们说明存在正整数，时都满足 ③， 注意到如果满足③，那么易知也满足③． 因此，若前述断言不成立，则都不满足③，从而易知，注意到 ， 因此数列是单调递增有界正整数数列，矛盾．于是前述断言成立． 我们不妨设满足③，那么注意到 ． 从而，即存在一个边长为、的矩形中各方格中实数和绝对值至少，而这个矩形可以划分成个边长为的正方形，从而其各方格中实数和绝对值至多，于是，令，矛盾． 综上所述，假设不成立，原命题得证． 考点五 容斥原理 11．从集合的子集中先后取出两个不同的子集、，求以下事件发生的概率： （1），且； （2）Card 【答案】（1）；（2） 【解析】由集合共有个子集，知有序子集对的取法共有种. （1）考虑“，且”的对立事件：“ 或 ”. 若 ，记Card..则有种取法.而是的真子集，于是，有种取法.从而，满足 的子集对的取法总数为 . 由对称性， 的取法也有种. 因此， ，且 的概率为. （2）集合中含有的子集的个数为个.于是，事件Card等价于在元集合\中先后选取两个子集、，使得. 设Card.则有种取法.于是，. 从而，有种取法. 此时，子集对共有种选法. 故满足的子集对有（个）. 因此，Card的概率为. 12．给定正整数，对于正整数，集合.集族满足如下条件： （1）的每个集合都是的元子集； （2）中的任意两个集合至多有一个公共元素； （3）的任意一个元素恰出现在中的两个集合中. 试求的最大值. 【答案】 【解析】的最大值为. 首先，估计的上界. 一方面，考虑集合. 由条件（3）知，对中的任意一个元素，有且仅有一对，使得.因此，. 另一方面，考虑集合. 由条件（3）知. 由条件（1）知. 故． 由条件（2）知，. 于是，.从而，，即. 下面用数学归纳法构造一个的例子. 对，，，集族符合条件. 假设当时，，满足条件. 当时，，，其中，. 令， 其中，，. 经验证，知集族符合条件. 从而，由归纳原理知可取到. 综上，所求的最大值为. 13．一些选手参加数学竞赛，其中有些选手互相认识，有些选手互相不认识，而任何两个不相识的选手都恰有两个共同的熟人．若与认识，但没有共同的熟人，求证：、认识的熟人一样多． 【答案】见解析 【解析】用点表示人，两人互相认识就在相应两点间连一条线段，依题意间有连线（如图）． 由于、没有共同的熟人，故凡认识的人就不认识，凡认识的人就不认识． 现设，，…，与认识，，，…，与认识，由于任一与不认识，而任何两个不相识的选手都恰有两个共同的熟人，故与有且仅有一个共同的熟人． 反之，每一个与有且仅有一个共同的熟人． 亦即每一必与某一有连线，每一也必与某一有连线． 现设与认识，与认识，下面证明与不相同时，与也不相同． 若不然，与重合，则、与均有连线，从而互不认识的，共同认识3个人，，（如图），与已知条件“恰有两个共同的熟人”矛盾，可见，． 同理，，不相同时，其对应的，也不相同，又得． 从而．这表明、认识的熟人一样多． 14．国际数学奥林匹克主试委员会有个国家参加，每个国家由领队和副领队两人参加，会前与会者互相握手，但领队不与本国的副领队握手，会后主办国的领队询问与会者握手的次数，所有人的回答却各不相同，主办国的副领队握手次.求实数、的值. 【答案】 【解析】主办国的领队问人，由于回答各不相同，可能回答的集合为， 对于每一个，有唯一的一个人，他恰与个人握手，则是唯一与没有握手的人. 因此，与为同一国家的正、副领队，他们均不是主办国的副领队； 与握手的只有一个人，自然是， 因此，与为仅有的与未曾握手的人. 从而，与为同一国家的. 类似地，可断定与为来自同一国家的. 因此，为主办国的副领队，他恰与个人握过手. 故. 题型六 递推问题 15．已知数列满足，． (1)若是递增数列，求实数的取值范围； (2)若，且对任意大于的正整数，恒有，求的最小值． 【答案】(1) (2) 【解析】（1）由知， 首先有，则， 当时，显然成立， 当时，，解得， 综上，的解集为， 其次当时，因为，， 则，于是； 以此类推，不妨设，， 则，， 则，于是． 综上所述，实数的取值范围是． （2）由（1）知，若，则是递增数列，所以易知， 一方面，， 则，得， 因此，则； 另一方面，又因为，所以， 因为，则，即，则，于是． 由已知得，则，于是当时，． 根据，则， 所以当时，，得，从而． 故的最小值是． 【点睛】关键点睛：第一问的关键是先由，即，算出的范围，进一步验证此时是否有；第二问的关键是首先得出，然后根据数列极限的夹逼性即可顺利求解. 16．数列满足且．证明：其中无理数． 【答案】证明见解析 【解析】证法一：由递推关系有. 故． 两边取对数并利用已知不等式得： ． 故． 有， ， … ． 将上述不等式两边相加可得 ． 即，故． 证法二：由数学归纳法易证对成立，故 ． 令，则． 对上述不等式两边取对数并利用已知不等式得： ． 故， ， … ． 将上述不等式两边相加可得： ． 因．故． 故，又显然，故对一切成立． 17．已知数列满足，，. （1）若对任意的正整数，有，求实数的取值范围； （2）若，且对任意大于1的正整数，有恒成立，求的最小值. 【答案】（1）；（2）. 【解析】解 （1）必要条件：，解得，此时. 设时，， 则当时，， 因为，，故， 由数学归纳法可知时，有. （2）由题意有，，，则，. 因为，故， 若，则，则恒成立，这不可能成立， 故， 猜想：，下面利用数学归纳法证明. 当时， 设当时，有， 则当时， ； 另一方面： . 由数学归纳法可得猜想成立. 因为对任意大于1的正整数，有恒成立， 故，故对任意大于1的正整数，有恒成立， 取，则， 取，则，故， 而，故. 下证：, 当时，由的取值范围的来源可得不等式成立， 设当时，， 则当时， 而 ()， 所以， 又 而 ， 故成立， 由数学归纳法得到对任意的恒成立， 故的最小值为： 题型七 母函数法 18．已知的非空子集，满足其元素之和为5的倍数．求上述子集的个数． 【答案】 【解析】设. 则 设T为满足题意的一个非空子集，且. 则                             ① 式①在且时的每一组非负整数解，所对应的子集个数为. 其母函数为 . 故所求子集的个数为f(x)中所有的系数之和，即为，其中，为的一个复根.则. 又， . 令. 则为根. 故. 从而，所求子集的个数为 . 19.求位十进制数中出现偶数个5的数的个数． 【答案】 【解析】令位十进制数中出现偶数个5的数的个数，位十进制数中出现奇数个5的数的个数． 因此有关系：，其中，则，此关系为关于序列的递推关系，求解此递推关系是解决本问题的难点．我们可以考虑引进序列的发生函数，即：，利用错位相加减的方法，即： ， ， 则，， 再将展开成幂级数的形式：， 因此． 题型八 组合几何 20．设n为一个正整数，三维空间内的点集S满足下述性质： （1）.空间内不存在n个平面，使得点集S中的每个点至少在这n个平面中的一个平面上； （2）.对于每个点，均存在n个平面，使得中的每个点均至少在这n个平面中的一个平面上. 求点集S中点的个数的最小值与最大值. 【答案】最小值为3n+1，最大值为. 【解析】先求的最小可能值. 由于过任意三点均可以作一个平面，故. 而当3n+1个点中，任意四点不共面时，即满足题设条件. 于是，的最小可能值为3n+1. 接下来求的最大可能值. 对于每一个， 设直线能覆盖. 由题设知. 设. 则为一个三元n次多项式，且，. 于是，在（为次数不超过n的三元多项式的向量空间）中是线性无关的. 因此，. 下面给出集合S中有个点的例子. 如图，设为个点构成的正四面体点阵. 则. 对于每个点，可以用n个平面覆盖.但不能用n个平面覆盖. 综上，集合S中点的个数的最大值为. 21．求的最大值，使得平面上有个点，其中任意三点中必存在两点间距离为1． 【答案】见解析 【解析】若存在 个点满足题设条件，用表示其中的八个点，当且仅当两点间的距离为1时，在这两点之间连一条边，构成图． 若存在一点（不妨设为）的度小于或等于3，则与不相连的至少四个点必两两相连，这显然是不可能的． 故任何一点的度至少为4． 在点集的凸包的顶点处取一个点集中的点（不妨设为），点与相连（按逆时针方向依次排列）．则（否则，无两点连线，矛盾）．由此均与中的至少一个相连．从而都恰与中的一个相连（否则，不妨假设与都相连，则中无两点相连，矛盾）． 又不可能同时与中的一点相连，于是，点中仅仅可能出现或（均有）． 因此中每一点还至少与中的两点相连．从而，点至少要向点引八条边．由抽屉原理，知至少有一个点（不妨设为）向引不少于三条边，即存在中的三点与的距离为1，这是不可能的． 故． 取两个边长均为1的菱形、菱形，使得，． 易证，中任意三点均存在两点，其距离为1． 22．将一枚棋子放在一个的棋盘上，记为从左、上数第行第列的小方格，求所有的四元数组，使得从出发，经过每个小方格恰一次到达（每步为将棋子从一个小方格移到与之有共同边的另一个小方格）. 【答案】所求为，且当为偶数时，；当为奇数时，. 【解析】将棋盘按国际象棋方式黑边相间染色，其中，为黑色， 当为奇数时，任两个黑色的小方格满足条件，当为偶数时，任两个异色的小方格满足条件. 记以下结论为. 下面用数学归纳法证明， 先证下面的引理. 引理1        与等价 显然成立. 引理2        在棋盘中，不同列的异色的两个小方格满足条件. 引理2的证明：若同行，因二者异色，则其中间有偶数列，由如图方式知满足条件. 若不同行，因二者异色，则其中间有奇数列，由如图方式知满足条件. 引理3        若成立，则成立， 引理3的证明：对棋盘，分两种情况讨论： （1）若都不在前（后）两列，则在后（前）面的棋盘中，有成立，且在前（后）第三列中必有相邻方格是中棋子走过的路径中连续的两个方格（设为）,可用如图 方式将前（后）两列并入棋子原来的路径，使成立. （2）若一个在前两列，另一个在后两列，不妨设在前两列，则在第二列有至少两个方格与异色，其中至少有一个方格（记为）与不同行，由引理知在前棋盘中，满足条件，取第三列中与相邻的方格（与同色），则由成立，知在后棋盘中，满足条件. 故由,使成立. 由（1）、（2）知成立. 类似可证： 引理4        若成立，则成立. 回到原题 由引理知，为利用数学归纳法，只需证明成立即可. 对异色. 若相邻，则由如图 环路知满足条件. 若不相邻，当都在上（下）两行时，由引理2知在棋盘中，满足条件. 类似引理3 （1）知有的路径使成立，当一个在上两行，另一个在下两行时，类似引理3（2）知有 的路径使成立. 对，同黑. 先由图知成立. 再分两种情况证成立. 若都在前（后）三列，则由成立，知在前（后）棋盘中，满足条件，类似引理3（1）知在棋盘中有路径使成立. 若一个在前两列，另一个在后两列，不妨设在前两列，由引理2知，在第2列中存在白方格,在第4列中存在白方格，使得分别在前、后棋盘中，、分别满足条件，如图 方式将、相连，则使成立. 最后分两种情况证成立. 若都在前（后）三列，则由成立，类似引理可知在棋盘中，有路径使成立. 若一个在前两列，另一个在后两列，类似中第2种情况知在棋盘中有路径使成立. 故成立. 综上，所求为，且当为偶数时，； 当为奇数时，. 23．在椭圆外一直线上取个不同的点，过向椭圆作切线、，切点分别为、.记直线为. （1）若存在正整数、（、，），使得点在直线上，证明：点在直线上； （2）试求直线将椭圆分成的区域的个数. 【答案】（1）见解析；（2） 【解析】设椭圆:，直线：，. 则点关于椭圆的切点弦的方程为                    ① （1）直线：，由点在上知. 从而，点也满足方程①，即点也在直线上. （2）当时，直线：，即.    ② 由直线在椭圆外知. 将式②代入式①整理得. 从而，直线恒过定点. 而，故该定点在椭圆内.当时，直线：，即 .    ③ 联立椭圆与直线的方程并化简得. 由直线在椭圆外知 . 将式③代入式①整理得. 此时，直线恒过定点. 而，故该定点在椭圆内. 综上，直线交于椭圆内一定点. 故这条直线将椭圆分成个区域. 24．21世纪城的街道都是东西向和南北向,为了加强安全管理,在一些十字路口设置保安亭(任何两个保安亭都不在同一街道上),以两个保安亭为其两个顶点、街道为边围成的矩形称为一个安全区,安全区(包括边界)内保安亭的个数称为该安全区的安全强度.如果世纪城两个方向的街道都至少有条,且任何两条不平行的街道都交成一个十字路口,今按要求选定个十字路口设置保安亭,求安全强度最大的安全区的安全强度的最小值. 【答案】 【解析】设最南、最东、最北、最西边的一个保安亭分别为(可能有重合).分别过的东西向街道与分别过的南北向街道围成一个矩形,则所有保安亭都在内.令,并用表示安全区的安全强度. (1)若中至少有两个不同点为的顶点,则本身为安全区.此时,. (2)若中恰有一个为的顶点(设为A).此时,的不含的两边上各有一个保安亭(设为).则三个安全区覆盖了.于是,外的个保安亭都被上述三个安全区覆盖.从而,至少有一个安全区覆盖了这个保安亭中至少个保安亭.又覆盖了中两个点(以其中两个点为顶点), 所以,. (3)若都不是的顶点,则四个安全区覆盖了中除矩形外的所有保安亭.又安全区覆盖了矩形.于是, 外的个保安亭都被上述五个安全区覆盖.从而,至少有一个安全区覆盖了这个保安亭中至少个保安亭. 又覆盖了中两个点(以其中两个点为顶点),所以,. 由上可见, . 其次,将个保安亭分为五组,各组保安亭个数及分布如图所示,其中,边界四组中有个组含有个保安亭,其他的组都含有个保安亭. 对其中任何两个保安亭. 当属于同一组时,. 当中恰有一个属于中央一组时,安全区或者恰含中央一组中的一个点,或者恰含非中央一组中的一个点,所以,. 当都属于边界相邻两组时,安全区或者恰含其中一组中的一个点,或者恰含另一组中的一个点,所以,. 当都属于边界相对两组时,安全区恰含这两组中的一个点,且最多含有中央一组中的个点,所以,. 又显然存在保安亭,使,因此,. 故. 25．已知边长为的正方形及其内部的个点,其中无三点共线.证明:可以选取其中的三个点,以这三个点为顶点的三角形的面积不超过. 【答案】见解析 【解析】令这个点的凸包为边形. (1)若,则边形周长不超过 (由于凸包在正方形内部).故存在连续的两条边,其长度之和不大于2.则以这两条边上的三个顶点构成的三角形面积不大于. (2)若,则从凸包某个顶点出发的条对角线将其分成个三角形.将凸包内的所有点编号,并且依次进行如下操作:将每个点与包含它的最小的三角形的三个顶点连线.则每进行一次操作增加两个三角形,且这些三角形互不重叠.于是,对所有点操作后共得到个三角形.故必有一个三角形的面积不大于. 综上所述,原命题成立. 26．一士兵要在一个半径为的圆形区域内检查是否埋有地雷，他所用的检查仪器的有效作用范围的半径为．求该士兵从该圆边界上一点出发，至少需走多少米才能将区域检测完，且回到出发点? 【答案】 【解析】首先，求士兵从出发，将圆的边界上的所有点检测完回到的最短路径． 下面用反证法证明： （1）上任意两点连线段在所围区域内（含边界），即是凸的； （2）与圆内部无交点． （1）否则，设、，且线段在所围区域外（如图）． 用线段代替中、间的曲线，得到另一条封闭曲线． 则曲线在所围区域内（含边界）． 对圆边界上任一点，设士兵在上的点处检测，则． 取线段与的交点为，则． 故士兵沿也可以将圆的边界上所有点检测． 但的长度小于的长度，矛盾． （2）否则，设、，中、之间的曲线在圆内部（如图）． 过圆心作交圆于点，其中，与曲线在直线同侧． 设线段与圆交于点． 由的凸性知，曲线与的其余部分在直线两侧． 则， 即士兵沿无法检测点，矛盾． 由（1），（2）知是含点且将圆包含在内部的封闭曲线． 则的长度的最小值为（将想成套在圆上的绳子，当从点拉紧绳子时，得到绳子的最短长度为）． 易证当时，士兵可沿将圆内所有点检测． 题型九 对策问题 27．在一次数学会议上，任意两位数学家要么是朋友，要么是陌生人．在进餐期间，每位数学家在两个大餐厅中的其中一个就餐，每位数学家所在的餐厅中包含偶数个他（或她）的朋友．证明：数学家能被分到两个餐厅中的不同分法的数目是2的正整数次幂（即形如，其中，是某个正整数）． 【答案】见解析 【解析】设参加会议的有位数学家．对用数学归纳法． 当时，该数学家可以在两个餐厅中的任何一个餐厅就餐．因此，有种不同的分法． 假设当有位数学家参加会议时，有种不同的分法． 当有位数学家时，分两种情形讨论． （1）若存在一位数学家没有朋友，则该数学家可以在两个餐厅中任何一个餐厅就餐．于是，位数学家时不同分法的数目是位数学家参加会议时不同分法的数目的两倍．由归纳假设，知位数学家参加会议时不同分法的数目为． （2）若每位数学家至少有一个朋友，再分两种情形讨论：一是存在一位数学家有奇数个朋友；二是每位数学家均有偶数个朋友． （i）存在一位数学家，有奇数个朋友． 去掉，对于每一对的朋友，改变、之间的关系，即若、是朋友，则变为陌生人；若、是陌生人，则变为朋友． 先证明一个命题． 命题  去掉，对于每一对的朋友，改变、之间的关系．则满足条件的不同分法的数目不变． 证明  由假设，知在去掉之前就餐的餐厅中，他的朋友有偶数个．若这个偶数为0，则当离开此餐厅后，此餐厅中的数学家仍然满足条件；若这个偶数大于0，设为在此餐厅中的一个朋友，由假设，知在此餐厅中也有偶数个朋友，去掉后，在此餐厅中还剩下奇数个朋友．除了外，在此餐厅中有奇数个朋友，改变与的这奇数个朋友之间的关系，在此餐厅中朋友的数目变为偶数． 在另一餐厅中，有奇数个的朋友．改变的朋友之间的关系，则每个的朋友与偶数个数学家之间改变了关系，于是，这些数学家朋友数目的奇偶性不变． 此外，由于恰有一个餐厅中包含偶数个的朋友，故不含的每一个分法均可以由包含的一个分法唯一确定． 回到原题． 在这种情形下，位数学家不同分法的数目与位数学家不同分法的数目相同．由归纳假设，知位数学家不同分法的数目是2的正整数次幂．因此，位数学家不同分法的数目也是2的正整数次幂． （ii）每位数学家均有偶数个朋友． 在这种情形下的每种分法均有每位数学家在两个餐厅中的朋友的数目为偶数． 设是任意一对朋友，去掉、，考虑每一对满足下述条件的数学家，其中，是的朋友，是的朋友．则改变、之间的关系．同理，若是的朋友，是的朋友，也改变、之间的关系．若、均是和的朋友，则、之间的关系改变两次，即、之间的关系没有改变． 接下来考虑不同于、的任意一位数学家及要选择的一个餐厅（在这种情形下，数学家的数目至少为3，即这样的三人组是存在的）．设在此餐厅中有位朋友，在此餐厅中有位朋友．则、均为偶数．当去掉、后，在此餐厅中要么与、要么与、要么与（是、在此餐厅中共同的朋友的数目）、要么与0位数学家之间的关系发生了改变（这分别依赖于仅是的朋友、仅是的朋友、既是A又是的朋友、既不是又不是的朋友）． 因为、均为偶数，所以，朋友的数目的奇偶性没有改变，仍为偶数． 由于不含、的每一个分法均可以由包含这对数学家的一个分法唯一确定：将、加入到其有奇数个朋友的餐厅中，然后改变所有的朋友和的朋友之间的关系，于是，在去掉之前和去掉之后建立了一个一—对应． 在这种情形下，位数学家不同分法的数目与位数学家不同分法数目相同． 由归纳假设，知位数学家不同分法的数目是2的正整数次幂． 因此，位数学家不同分法的数目也是2的正整数次幂． 28．某公司印制了一批文化衫，每件文化衫可有红、黄、蓝三种不同的颜色和四种不同的图案.现将这批文化衫分发给名新员工，每名员工恰好分到图案不同的4件.试求的最小值，使得总存在两个人，他们所分到的某两种图案的4件文化衫的颜色全部相同. 【答案】19 【解析】的最小值为19. 当时，表1所示的答题情形不符合要求. 表1 （1） （2） （3） （4） 【注】表l中（1）、（2）、（3）、（4）为图案，为员工，、、分别表示红、黄、蓝三种颜色. 下面证明：当时，必存在两个人满足要求. 事实上，把所有人的文化衫的颜色和图案如上制成表格，若存在两个人的某两种图案的4件文化衫的颜色全部相同，则必存在一个矩形子表，这个子表四个角的方格中的字母（颜色）相同. 若对于某个颜色（以红色为例），设分到件红色文化衫.则当时（约定当时，），必存在四个角都是的矩形.这是因为，考虑每一列两个构成的“对子”，一共只有如表2所示的6种.当时，必有两列会出现相同的对子，从而，必有四个角都是的矩形. 表2 当时，任取其中19个人，他们的所有文化衫的颜色中，至少有一种颜色出现了不少于（次），不妨设为红色. 设其中分到（为非负整数）件红色文化衫.则. 由调整法易知，当取最小值时，对任意，有. 注意到，则在中有19个1和7个2时，取得最小值. 这表明，当时，必存在四个角都是同一个字母的矩形子表. 综上，所求的最小值为19. 题型十 图论 29．设n为一个正整数，三维空间内的点集S满足下述性质： （1）.空间内不存在n个平面，使得点集S中的每个点至少在这n个平面中的一个平面上； （2）.对于每个点，均存在n个平面，使得中的每个点均至少在这n个平面中的一个平面上. 求点集S中点的个数的最小值与最大值. 【答案】最小值为3n+1，最大值为. 【解析】先求的最小可能值. 由于过任意三点均可以作一个平面，故. 而当3n+1个点中，任意四点不共面时，即满足题设条件. 于是，的最小可能值为3n+1. 接下来求的最大可能值. 对于每一个， 设直线能覆盖. 由题设知. 设. 则为一个三元n次多项式，且，. 于是，在（为次数不超过n的三元多项式的向量空间）中是线性无关的. 因此，. 下面给出集合S中有个点的例子. 如图，设为个点构成的正四面体点阵. 则. 对于每个点，可以用n个平面覆盖.但不能用n个平面覆盖. 综上，集合S中点的个数的最大值为. 30．求的最大值，使得平面上有个点，其中任意三点中必存在两点间距离为1． 【答案】见解析 【解析】若存在 个点满足题设条件，用表示其中的八个点，当且仅当两点间的距离为1时，在这两点之间连一条边，构成图． 若存在一点（不妨设为）的度小于或等于3，则与不相连的至少四个点必两两相连，这显然是不可能的． 故任何一点的度至少为4． 在点集的凸包的顶点处取一个点集中的点（不妨设为），点与相连（按逆时针方向依次排列）．则（否则，无两点连线，矛盾）．由此均与中的至少一个相连．从而都恰与中的一个相连（否则，不妨假设与都相连，则中无两点相连，矛盾）． 又不可能同时与中的一点相连，于是，点中仅仅可能出现或（均有）． 因此中每一点还至少与中的两点相连．从而，点至少要向点引八条边．由抽屉原理，知至少有一个点（不妨设为）向引不少于三条边，即存在中的三点与的距离为1，这是不可能的． 故． 取两个边长均为1的菱形、菱形，使得，． 易证，中任意三点均存在两点，其距离为1． 31．将一枚棋子放在一个的棋盘上，记为从左、上数第行第列的小方格，求所有的四元数组，使得从出发，经过每个小方格恰一次到达（每步为将棋子从一个小方格移到与之有共同边的另一个小方格）. 【答案】所求为，且当为偶数时，；当为奇数时，. 【解析】将棋盘按国际象棋方式黑边相间染色，其中，为黑色， 当为奇数时，任两个黑色的小方格满足条件，当为偶数时，任两个异色的小方格满足条件. 记以下结论为. 下面用数学归纳法证明， 先证下面的引理. 引理1        与等价 显然成立. 引理2        在棋盘中，不同列的异色的两个小方格满足条件. 引理2的证明：若同行，因二者异色，则其中间有偶数列，由如图方式知满足条件. 若不同行，因二者异色，则其中间有奇数列，由如图方式知满足条件. 引理3        若成立，则成立， 引理3的证明：对棋盘，分两种情况讨论： （1）若都不在前（后）两列，则在后（前）面的棋盘中，有成立，且在前（后）第三列中必有相邻方格是中棋子走过的路径中连续的两个方格（设为）,可用如图 方式将前（后）两列并入棋子原来的路径，使成立. （2）若一个在前两列，另一个在后两列，不妨设在前两列，则在第二列有至少两个方格与异色，其中至少有一个方格（记为）与不同行，由引理知在前棋盘中，满足条件，取第三列中与相邻的方格（与同色），则由成立，知在后棋盘中，满足条件. 故由,使成立. 由（1）、（2）知成立. 类似可证： 引理4        若成立，则成立. 回到原题 由引理知，为利用数学归纳法，只需证明成立即可. 对异色. 若相邻，则由如图 环路知满足条件. 若不相邻，当都在上（下）两行时，由引理2知在棋盘中，满足条件. 类似引理3 （1）知有的路径使成立，当一个在上两行，另一个在下两行时，类似引理3（2）知有 的路径使成立. 对，同黑. 先由图知成立. 再分两种情况证成立. 若都在前（后）三列，则由成立，知在前（后）棋盘中，满足条件，类似引理3（1）知在棋盘中有路径使成立. 若一个在前两列，另一个在后两列，不妨设在前两列，由引理2知，在第2列中存在白方格,在第4列中存在白方格，使得分别在前、后棋盘中，、分别满足条件，如图 方式将、相连，则使成立. 最后分两种情况证成立. 若都在前（后）三列，则由成立，类似引理可知在棋盘中，有路径使成立. 若一个在前两列，另一个在后两列，类似中第2种情况知在棋盘中有路径使成立. 故成立. 综上，所求为，且当为偶数时，； 当为奇数时，. 32．在椭圆外一直线上取个不同的点，过向椭圆作切线、，切点分别为、.记直线为. （1）若存在正整数、（、，），使得点在直线上，证明：点在直线上； （2）试求直线将椭圆分成的区域的个数. 【答案】（1）见解析；（2） 【解析】设椭圆:，直线：，. 则点关于椭圆的切点弦的方程为                    ① （1）直线：，由点在上知. 从而，点也满足方程①，即点也在直线上. （2）当时，直线：，即.    ② 由直线在椭圆外知. 将式②代入式①整理得. 从而，直线恒过定点. 而，故该定点在椭圆内.当时，直线：，即 .    ③ 联立椭圆与直线的方程并化简得. 由直线在椭圆外知 . 将式③代入式①整理得. 此时，直线恒过定点. 而，故该定点在椭圆内. 综上，直线交于椭圆内一定点. 故这条直线将椭圆分成个区域. 33．平面上有n个点，其中无三点共线，将这n个点两两相连，用红、黄、绿三种颜色染这些线段，且任意三点所成的三角形的三条边均恰好有两种颜色，证明：． 【答案】证明见解析 【解析】首先，注意到没有点能引出六条同色线段．用反证法证明． 假设点A与其他六点B、C、D、E、F、G有相同颜色的线相连（不妨设为红色）． 根据题设，三角形只有两种颜色的边知，点B、C、D、E、F、G之间连线必为黄色或绿色．由此可知，在点B、C、D、E、F、G之间的连线存在一个同色三角形，与题设矛盾． 从而，每个点至多引出15条线段，即． 设． 将从同一点引出的两条异色边称为一对“好边”． 由题设知，好边的对数S满足． 设从一点引出x条红边、y条黄边、z条绿边． 则此点好边的对数为． ，其中， 故当或时，取得最小值， 即当x、y、z三者中有两个取5，一个取时，取得最小值． 故．则 ， 解得或．矛盾． 所以． 34．给定一个的方格棋盘，其中有n个格子上各放置一枚棋子．对每个棋子，以其所在格为中心作一个的边平行于相应棋盘边界的正方形，这个正方形称为该棋子的范围．已知每个棋子范围中恰有一个其他棋子，求n的最大值． 【答案】n的最大值为72． 【解析】对每个棋子，以其所在格为最左上角的格作一个的边平行于棋盘边界的正方形，这个正方形称为该棋子的小范围. 若棋子A在棋子B的范围中，易知B也在A范围中. 由题设知这些棋子可两两配对使每一对棋子互相在其范围中，所以n为偶数，并将配对的棋子分成一组，共组． 若棋子在从上至下第x行，从左至右第y列，则记此棋子坐标为． 对棋子A、B，设其坐标分别为， 所以A、B互相在另外一个棋子的范围中等价于使得的小范围与B的小范围有公共方格． 将原的棋盘的最下边与最右边分别加上两行、两列构成一个的大棋盘，则所有棋子的小范围都包含于大棋盘中，且同组棋子的小范围有公共方格，异组的棋子的小范围中没有公共方格． 考虑一组棋子，若它们不在同一行，则其小范围占至少4行，每一行占至少3格，所以它们的小范围占至少12格． 若它们在同一行，则它们不在同一列，同理可得它们的小范围占至少12格． 而不同组的棋子的小范围没有公共方格，所以所有棋子的小范围占了至少． 故． 构造：将的大棋盘分为9个的棋盘，对每个，内部如图所示放置8个棋子，故总共放了72个棋子均在原棋盘内，且每个棋子范围内恰有一个其他棋子． 35．求一切正整数，满足：可以将一个平面正n边形分割成有限个三角形，使得在这些三角形中，任意两个重叠部分的面积为零．并且任意两个都没有公共边（允许某些三角形的边有公共部分）． 【答案】n的值只能为3 【解析】如图，当时，满足题意． 下面证明当时不满足题意． 假设对于正边形，存在满足题意的分割．设在该分割中，共有l个三角形，所有的三角形总共有c个顶点．定义此时图中连结以上c个顶点的线段（内部不再含有这c个顶点中的点）为基本线段，设基本线段有e条，则由平面图的欧拉公式，有．① 考察图中这l个三角形的内角总和，由已知，多边形内部的每个顶点对于该总和的值贡献至少为， 则，即．② 接下来，按如下规则给每个三角形的边上标数，如果该边被图中的顶点分成了k段，则在每段上写上.那么，每条基本线段上被写的数字个数为1或2，并且写有1个数字的基本线段上所写数字的最大值为1，写有2个数字的基本线段上所写数字之和的最大值为． 因为的每条边上，一定存在至少一条基本线段，其仅作为一个三角形的边的一部分，故在的每条边上，都一定存在至少一条基本线段，上面恰写有一个数字． 对所有的三角形，考查其边上所写的数字总和，由以上分析，知应有： ， 即．③ 由①②③，得矛盾. 综上，知n的值只能为3． 36．某国有2020个城市，若干座城市对之间开通单向航线，使得每座城市恰有一班飞离的航线．求最小的正整数k，使得满足无论怎样开通航线总能将2020座城市分成k组，使得每组中任意一座城市不可能用不超过28次飞行到达这一组中的另一座城市． 【答案】57． 【解析】最小的正整数k为57． 考虑一个有2020个顶点的有向图G，且每个顶点的出度为1． 先证明这2020座城市至少分成57组． 假设图G有一个长度为57的有向圈，则对于圈中的任意两座城市一定有一座城市最多用28次飞行到达另一座城市．因此至少分成57组． 下证总是能分成57组． 定义：若城市A到城市B能用不超过28次飞行到达，则从城市B到城市A有一个箭头．那么每座城市的入度不超过28． 需要证明对于任一个有向图，分成57组，使得每组中任两顶点之间没箭头． 考虑归纳法：假设有n个顶点的有向图满足每个顶点的入度最多为28，则n个顶点能被分成57组，使得每组中两顶点之间没有箭头． 时，结论显然成立． 对于，假设时结论成立． 对于n个顶点的有向图H，由于每个顶点的入度最多为28，则存在一个顶点的出度最多为28． 不妨记顶点v的出度最多为28，将点v从有向图H中移除，得到一个有个顶点的图仍满足条件． 将这个顶点分成57组，每组中均没有两个顶点用一个箭头连接． 因为v点的入度和出度均最多为28，所以，在有向图H中最多有56个顶点与v相邻． 将点v放到在57组中无顶点与之相邻的那一组去，证毕！ 题型十一 染色问题 37．给定正整数m、n，一个的正方形由8个白色及1个黑色的的正方形构成，其中黑色正方形在正中间．一个的大正方形由个这样的的正方形构成．现将一些的白色正方形染成红色，使得每个白色正方形都至少与一个红色正方形有公共顶点．求最少的需要染红的正方形的数目． 【答案】. 【解析】称一个最小单位的立方体（正方形）被覆盖，如果它至少与一个红色立方体（正方形）有公 共顶点.我们称中心为黑色的正方形是一口“井”，给定呈矩阵排列的口井，至少需要个红色正方形才能覆盖． 取等例子（以为例）： 0为白色，1为红色，空白处为黑色 证明：设矩阵排列的口井至少需要个红色正方形， 只要证明． 引理：要么最左边两列至少有个红色正方形，要么最下边两行至少有个红色正方形． 引理证明：最左边两列的红色正方形与最左边每口井的交中至少有一个红色正方形（为了覆盖这个区域左边正中的小正方形），故最左两列红色正方形数目不少于m，而等号成立当且仅当这m个红色正方形恰是每口井左边正中的那个小正方形．同理最下两行红色正方形数目不少于n，而等号成立当且仅当这n个红色正方形恰是每口井下边正中的那个小正方形．两者等号不能同时取到．故必有上述一者成立． 回到原题： 若最左边两列至少有个红色正方形，去掉左边三列有． 若最下边两行至少有个红色正方形，去掉下边三行有， 从而必有， 又显然有，容易归纳证明． 38．将一个凸2019边形的每条边任意染为红､黄､蓝三种颜色之一，每种颜色的边各673条.证明：可作这个凸2019边形的2016条在内部互不相交的对角线将其剖分成2017个三角形，并将所作的每条对角线也染为红､黄､蓝三种颜色之一，使得每个三角形的三条边或者颜色全部相同或者颜色互不相同. 【答案】证明见解析 【解析】我们对n≥5归纳证明加强的命题：如果将凸n边形的边染为三种颜色a，b，c，并且三种颜色的边均至少有一条，那么可作满足要求的三角形剖分. 当n=5时，若三种颜色的边数为1､1､3，由对称性，只需考虑如下两种情形，分别可作图①中所示的三角形剖分. 若三种颜色的边数为1､2､2，由对称性，只需考虑如下三种情形，分别可作图②中所示的三角形剖分. 假设结论对n(n≥5)成立，考虑n+1的情形，将凸n+1边形记为. 情形1：有两种颜色的边各只有一条.不妨设a､b色边各只有一条.由于n+1≥6，故存在连续两条边均为c色，不妨设是.作对角线，并将染为c色，则三角形的三边全部同色.此时凸n边形的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分. 情形2：某种颜色的边只有一条，其余颜色的边均至少两条.不妨设a色边只有一条，于是可以选择两条相邻边均不是a色，不妨设均不是a色，作对角线，则有唯一的染色方式，使得三角形的三边全部同色或互不同色.此时凸n边形的三种颜色的边均至少有一条，由归纳假设，可对其作符合要求的三角形剖分. 情形3：每种颜色的边均至少两条.作对角线，则有唯一的染色方式，使得三角形的三边全部同色或互不同色.此时凸n边形的三种颜色的边均至少有一条由归纳假设，可对其作符合要求的三角形剖分. 综合以上3种情形，可知n+1的情形下结论也成立. 由数学归纳法，结论获证. 【点睛】解答染色问题，需要具有缜密的数学思维和较强的分析能力.纵观各种染色问题，它与同学们常用的数学方法，如奇偶分析、归纳法、反证法、抽屉原理、构造法、组合计数等有着紧密的联系. 39．设，为所有满足下列条件的整数数列的个数： （1），，且； （2）不存在、，使得. 试求的值. 【答案】2012 【解析】将长度为的圆周等分成份，分点依次标为0，1，…，.再将标的分点染为黑色，其他个分点染为白色.则题设数列与以下染法一一对应： （1）标0的点为黑点，且黑点将圆周分成段圆弧，每段弧长为1或2或3； （2）圆周上没有两个黑点为对径点，即黑点与白点一一对应，组成对径点. 显然，不存在相邻的三个黑点.否则，设、、为相邻黑点.则其对径点、、为相邻白点，但包含这三个白点的弧长大于3，矛盾. 从而，满足（1）、（2）的染法为标0的点为黑色，将各点染黑、白两色，使得其中没有相邻的三个点同色，再对应地将点染色（染黑色染白色）. 首先，对长为的圆弧各分点染两色，使得两端点为黑色，且没有相邻的三个点同色. 设其染法个数为.易知，，，. 对，考虑最后一段以黑点为端点的圆弧. 若其弧长为3，则相应染法个数为； 若其弧长为2，则相应染法个数为； 若其弧长为1，则其相邻的弧长为2或3，其染法个数为. 故. 下面求满足（1）、（2）的染法个数. 若点为黑色，则染法个数为. 若点为白色，而为白色，则、为黑色，1为白色.如果2为黑色，则染法个数为；如果2为白色，则3为黑色，染法个数为.从而， .① 逐项计算得 ，，，，，，，，，，. 由式①得 ， ， . 故. 40．平面上有一个阶完全图，对其边进行三染色，且每种颜色至少染一条边.现假设在完全图中至多选出k条边，且把这k条边的颜色全部变为给定三色中的某种颜色后，此图同时也可以被该种颜色的边连通.若无论初始如何染色，都可以达到目的，求k的最小值. 【答案】 【解析】先证明：.（这里表示不超过的最大的整数）. 假设三种颜色为1、2、3，n阶完全图的n个点分成三个点集A､B､C， 且. 做如下染色：集合A中的点之间连的边染1，集合B中的点之间连的边染2，集合C中的点之间连的边染3，集合A与B间的点连的边染2，集合B与C间的点连的边染3，集合C与A间的点连的边染1. 从而，若变色后最终得到染1的颜色的边形成的连通图， 由于集合B中的点出发的边均染的是2或3，于是，变色边数不小于. 类似地，若变色后最终得到染2或3的颜色的边形成的连通图，则变色边数不小于（或). 故. 再证明：. 对n用数学归纳法. 当时，结论成立. 假设时，结论成立.则n个点时： （1）若完全图中由某点出发的边有三种不同颜色， 由归纳假设，可通过改变其中条边的颜色得到同色连通图. （2）若完全图中由所有点出发的边均最多两种不同颜色， 记A为所有出发的边均染1或2的点组成的集合， 记B为所有出发的边均染2或3的点组成的集合， 记C为所有出发的边均染3或1的点组成的集合. 如果某些点连出的边都染颜色1，则把它归入集合A； 如果某些点连出的边都染颜色2，则把它归入集合B； 如果某些点连出的边都染颜色3，则把它归入集合C. 不失一般性，不妨设.则.若，则， 集合B中的点连向集合C中的点的边均染3.故由颜色3可以连通. 此时，任选集合B中一点，集合A中每个点与该点的连线的边颜色均变成3， 由知成立. 若，则，于是，完全图的边均染的是1或3. 这与条件“每种颜色至少染一条边”不符. 所以由归纳法知原结论成立. 1.（多选）（2024·清华大学强基计划）某区域仅有东西向或南北向道路，某人从区域中心出发后又回到起点，且路途中不经过重复区域，已知此人左转次，则其右转次数可以是（    ） A． B． C． D． 【答案】BD 【解析】如果原点处不同时出现东西向和南北向道路，则由于该人路途中不经过任何区域，故该人面向的方向从出发到回到起点总共旋转了. 而每次左转时，面向的方向逆时针旋转了，每次右转时，面向的方向顺时针旋转了. 故左转次数与右转次数之差一定是或. 所以右转次数只可能是或. 而对于下列路径： 左转次数和右转次数分别是和； 对于下列路径： 左转次数和右转次数分别是和. 故右转次数的所有可能值就是和. 如果原点处同时出现东西向和南北向道路，则将路线进行轻微平移，然后利用上一种情况的结论可知，在原点之外进行的右转次数一定是奇数，没有选项符合该条件. 以上表明B，D正确，且A，C错误. 故选：BD. 2．(2024·清华大学强基计划)已知正方体，初始时与重合，每一步都等可能得移动到相邻顶点，记移动步后仍在面上的概率为，则（    ） A．移动步后，仍在点的概率为 B． C． D．与的递推式为 【答案】BCD 【解析】可以注意到，在运动次后，点的位置只取决于：点沿着的方向或反方向运动的次数. 我们考虑的展开式，该式展开时，相当于从个中各选取一项并作乘积，遍历所有种选法并相加. 每个选法恰好也对应唯一一组点沿着的方向或反方向运动的次数，它们相乘后得到. 再将所有项相加，我们就得到了若干个形如的项之和，这里是点沿着的方向或反方向运动的次数分别为的概率. 对于A，由于移动步后，仍在点就相当于满足都是偶数，故所求概率即为的展开式中，三个字母的指数均为偶数的项的系数和. 设，则三个字母的指数均为偶数的项的系数和就是 . 代入得到该表达式的值为，这即为所求的概率，故A错误； 对于B，C，D，由于移动步后，仍在面上当且仅当满足是偶数，故即为的展开式中，的指数为偶数的项的系数和. 设，则的指数为偶数的项的系数和就是. 代入得到，所以. 故，，故B，C正确. 同时由有，故，所以，故D正确. 故选：BCD. 3．（2024·全国高中数学联赛四川预赛）给定正整数，数组称为“好数组”是指：均不为，且对任意的，均有．求“好数组”的组数． 【答案】组数为 【解析】引理1：对任意正整数，若时，则，且和同奇偶；若时，则，且和不同奇偶． 引理1的证明：对进行归纳． 当时，由知结论成立； 当时，注意到或者，从而结论也成立． 假设结论对时成立，下面考虑： 情形1：若． 由归纳假设知，，且和同奇偶，于是和不同奇偶． 由或者，知，且和同奇偶； 或者，且和不同奇偶． 情形2：若． 由归纳假设知，，且和不同奇偶，于是和同奇偶． 由或者，知，且和不同奇偶； 或者，且和同奇偶． 因此，结论对也成立． 由归纳原理知，对任意的正整数，结论均成立． 引理1得证． 记为中的数组的个数，注意． 约定，由题可知． （注意由引理1可知是偶数时是奇数时，所以上式对成立．） 引理2：对任意的正整数，有，①这里， 且，②这里，注意这里的． 补充定义．注意①蕴含着，这和题意一致． 引理2的证明：对进行归纳， 当时， 对①：或1，注意到：，； 对②：，注意到：．从而时，结论①、②成立． 当时， 对①：或1，注意到：，； 对②：，注意到：．从而时，结论①、②成立． 假设结论①、②对时成立，考察的情形： 对于①，分情况讨论：对任意， （1-1）．易知，此时结论①成立． （1-2）对任意，注意此时， ， （1-3），此时，成立． 所以结论①对任意成立． 对于②，分情况讨论：对任意， （1-1）若．易知，此时结论①成立． （1-2）对任意，注意此时， ． 所以结论②对任意成立． 由归纳原理知，对任意的正整数，结论①、②都成立． 引理2得证． 回到原题：注意到：所求的组数为， ， 及 ． 综上可知，所求的组数为． 【点睛】关键点点睛：利用数学归纳法证明和. 4．(2022·全国奥赛贵州初赛)已知半径为1的圆上有2022个点，求证：至少存在一个凸337边形，它的面积小于．（，） 【答案】证明见解析 【解析】由于， 故将2022个点分成6组，则至少有一个组T的点数不小于337个， 将圆周六等分，，将T组的点都放在弧上（有两个点可能是A，B）， 则凸337边形的面积小于弓形的面积， 而弓形的面积为， ∴至少存在一个凸337边形，它的面积小于. 5．(2023·第39届全国中学生冬令营)给定一个正99边形，将1，2，，99放入99边形的99个顶点处，若两种放置方法在旋转之后可以重合，则称这两种方法是同一个.称交换某两个相邻顶点上的数为一次操作，求最小的使得至多次操作可以将一种放置方法变为任意另外一种放置方法. 【答案】 【解析】的最小可能值为. 先证明，考虑从1，2，，99变换为99，98，，1的操作次数， 对于任意的三个数a,b,c，若两两之间均为操作过，则三者之间的顺序不发生改变，不可能变为后者， 故任意三个数中，必存在两个数进行过操作，可转换为图论模型：将99个数转化为99个点， 若两个数未进行过操作，则在两点间连一条边，由上述可知图中不存在三角形， 故由托兰定理知图中至多含条边，因此至少操作次，所以. 再证明，即证明至多次操作一定可以完成转化.将正99边形的99个顶点放置在圆周上， 设相邻两顶点间的弧长为1，对于和两种不同的放置方法， 定义表示在两个放置方法中所处位置间的劣弧长，称使的为不动数， 使的为动数，称不动数所处的顶点为不动点，并记所有动数的数目为， 运用数学归纳法证明对状态，可用不超过次操作及旋转使重合， 对进行归纳.当时，显然成立， 假设对小于时，命题成立，对于， 从在所在位置沿劣弧到在中所在位置连一条有向边，称之为有向边， （1）若存在两个动数，在中所在位置为（不妨从顺时针方向来看，到为一段劣弧） 使得劣弧上（不含）的点均为不动点，且为顺时针方向，为逆时针方向， 设之间顶点分别为，则依次交换上的数，共计次后得到， 则可知与之间仅交换了两个位置上的数，故， 而， 对，用归纳假设，至多次操作可将变为， 进而至多次操作可将变为， 不存在满足（1）的，我们先证明此时所有有向边均同向（不妨设均为顺时针）， 不妨为顺时针，其从点指向，若存在起点在上（包含点）为逆时针， 则取其中起点最靠近的，记其起点为， 则起点在逆时针方向且最靠近的有向边为顺时针，此时满足（1），矛盾， 故起点在上的有向边均为顺时针（），特殊地，起点为的有向边为顺时针， 依次类推，得到为首尾衔接的顺时针有向边，直至使得这些有向边覆盖了圆周， 进而由（）知所有有向边均为顺时针， ①若不存在不动点，将顺时针旋转，得到，且， 且，由归纳假设易知结论成立， ②若存在不动点我们称连续的不动点为一段不动点，设共有段不动点， 分别有个不动点，则， 对每一段不动点的前一个点不为不动点， 依次交换（这操作了步），共操作了次，再顺时针旋转，得到，此时相较，个不动点位置不变， 位于的点顺时针移动了（共t个这样的点），其余个点顺时针移动了1， 则， 而，对用归纳假设，至多次操作可将变为， 故至多次操作可将变为成立， 回到原题，记为逆时针旋转， 则， 知存在，使得， 故可用至多2401次操作将变为，进而旋转得到，命题得证， 综上所述，的最小可能值为. 6．（2023·全国高中数学联赛加试）求具有下述性质的最小正整数：若将中的每个数任意染为红色或者蓝色，则或者存在9个互不相同的红色的数满足，或者存在10个互不相同的蓝色的数满足. 【答案】408. 【解析】解：所求的最小正整数为408. 一方面，若时，将染为红色，染为蓝色， 此时最小的8个红数之和为， 最小的9个蓝数之和为，故不存在满足要求的9个红数或者10个蓝数. 对，可在上述例子中删去大于的数，则得到不符合要求的例子.因此不满足要求. 另一方面，我们证明具有题述性质. 反证法.假设存在一种的染色方法不满足要求， 设是所有红数的集合，是所有蓝数的集合. 将中的元素从小到大依次记为，中的元素从小到大依次记为，. 对于，或者，或者； 对于，或者，或者. 在中至少有9个蓝色的数或至少有8个红色的数. 情形1：中至少有9个蓝色的数. 此时.设区间中共有个中的元素. 记，则. 因为是中的所有正整数，故. 于是.（*） 特别地，.从而. 对任意，由（*）知. 从而 （考虑二次函数对称轴，即知时取得最大）. 又，这与，中有一个为408矛盾. 情形2：中至少有8个红色的数.论证类似于情形1. 此时.设区间中共有个中的元素. 记，则. 因为是中的所有正整数，故. 于是.特别地，.从而. 对任意，有. 从而 （在时取得最大）， 又，这与，中有一个为408矛盾. 由情形1、2知具有题述性质. 综上，所求最小正整数为408. 7．（2022·浙江宁波高中数学竞赛）甲、乙两人分别进行投硬币和掷图钉试验，每人各进行100次试验．设为前k次试验中硬币正面向上的次数，为前k次试验中图钉针尖朝下的次数，记． (1)若，问是否存在常数P，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有P的可能值；若不存在，请说明理由； (2)若，问是否存在常数Q，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有Q的可能值；若不存在，请说明理由． 【答案】(1)不存在；理由见解析 (2)存在，或． 【解析】（1）不存在，先考虑最后50次试验硬币正面向上，则对应的均小于0.5． 再考虑第2次至第51次试验硬币正面向上，则对应的均大于等于0.5． 这与最后50次试验硬币正面向上的情形没有公共的取值，故这样的P不存在. （2）存在，或，先考虑最后70次试验针尖向下，则对应的均小于0.7． 再考虑第2次至第71次试验针尖向下， 则对应的分别为， 所以符合要求的Q只可能取． 下证对，必存在时，使得． 设， 若第k次试验针尖朝上，则，则 ； 若第k次试验针尖朝下，则，则 当时，． 所以由介值性定理知，必存在，使得，即，得证． 8．（2022·全国中学生奥赛贵州初赛）甲乙二人轮流给一个正方体的棱涂色，首先，甲任选3条棱涂成红色，然后乙从余下的9条棱中任选3条涂成绿色，接着甲从余下的6条棱中任选3条涂成红色，最后乙将余下的3条棱涂成绿色，如果甲能将某个面上的4条边全都涂成红，甲就获胜，试问甲有必胜策略吗？说明理由． 【答案】甲没有必胜策略，理由见解析 【解析】将正方体的12条棱分成4组： ， ，． 当甲第一次涂红3条棱后，由抽屉原理知，上述4组棱中总有一组的3条棱均未被涂红． 乙只要将这一组的3条棱涂绿，则正方体的6个面就各有一条绿边． 可见，甲没有必胜策略． 9．（2022·全国高中数学联赛苏州选拨赛）定义：如果甲队赢了乙队，乙队赢了丙队，而丙队又赢了甲队，则称甲乙丙为一个“友好组”. (1)如果19支球队参加单循环比赛，求友好组个数的最大值； (2)如果20支球队参加单循环比赛，求友好组个数的最大值. 【答案】(1)285 (2)330 【解析】（1）当m为奇数时，令，由于共有支球队进行单循环比赛，故总共有场比赛.不妨设有x个友好组，考虑其反面，若甲乙丙三队为非友好组.不妨设甲队赢了乙队和丙队，此时，记甲队为非友好组的组长. 对甲队而言，可以在赢的所有队伍中任意选择两队构成非友好组. 因此，若队在比赛中赢了场，则，且以为组长的非友好组有个（补充定义：）， 于是所有非友好组的个数为.（其中等号成立当且仅当）. 故有. 当（）时，取到最大值，即. 构造例子：设在共支球队中，队胜，负，其中下标是在模的意义下的.则友好组的个数为.综上所述，当m为奇数时，友好组个数的最大值为； 故如果19支球队参加单循环比赛，友好组个数的最大值为 （2）当m为偶数时，令，则总共有场比赛.不妨设有x个友好组，考虑其反面，若甲乙丙三对为非友好组，不妨设甲队赢了乙队和丙队，此时，记甲队为非友好组的组长.对甲队而言，可以在赢的所有队伍中任意选择两队构成非友好组. 因此，若队在比赛中赢了场，则，且以为组长的非友好组有个（补充定义：）于是所有非友好组的个数为. 下求的最小值. 若在中，不妨设. 则令，，其余（且）， 故调整后的总和变小. 重复上述操作，直至任意两个数的差最多为1. 不妨设有y个a，个，则有， 整理有.由于，故. 由等式两边对应相等可知，，，即调整后有n个，n个n. 此时的值为，则， 故友好组个数的最大值为，即. 下面为取到最大值的例子：设在.共2n支球队中，当时，队胜；当时，队胜，下标均是在模2n的意义下. 综上所述，当m为偶数时，友好组个数的最大值为. 故如果20支球队参加单循环比赛，友好组个数的最大值为 10．（2024·全国鱼塘杯竞赛）对集合，定义其特征函数，考虑集合和正实数，定义为和式函数.设，则为闭区间列；如果集合对任意，有，则称是无交集合列，设集合. (1)证明：L和式函数的值域为有限集合； (2)设为闭区间列，是定义在上的函数.已知存在唯一的正整数，各项不同的非零实数，和无交集合列使得，并且，称为和式函数的典范形式.设为的典范数. （i）设，证明：； （ii）给定正整数，任取正实数和闭区间列，判断的典范数最大值的存在性.如果存在，给出最大值；如果不存在，说明理由. 【答案】(1)证明见解析 (2)（i）证明见解析（ii）存在，最大值为 【解析】（1）因为表达式中恒定，所以的取值只和有关 则当都相同的时候相同 注意到最多只有种取法，因此的值域大小不大于，从而是有限集. （2）（i）根据典范形式的唯一性，我们构造正整数，各项不同的非零实数，和无交集合列使得，并且， 设的取值集合为，设，则是无交集合列且非0（因为定义在上） 根据题意，任意，取，有，所以，那么，所以是无交集合列 此时对任意，恰好存在一个小区间，使得，所以的取值集合最多有这个数，因为这些数可能相等，所以. （ii）设是的最小值，是的最大值，那么，并且的端点数目有个，至多构成个区间 如果，其中分别为的端点，且之间没有其他端点，那么要么；要么 所以最多有种取值，所以 另一方面，令，取 并且取，容易验证恰好有种取值， 所以最大值为. 11．（2023·第39届全国中学生冬令营）对任意满足的非负实数组，记为的元素个数，求证：，并给出取等的充要条件. 【答案】证明见解析，恰有100个1，其余均为0 【解析】设中所有正实数为； 设中共有x个数不小于1，中共有y个数不小于1， 则， 由条件知， 则，另一方面，容易知道取等时有， 这代表中共有100个不小于1， 因此必有中恰有100个1，其余均为0，此即为的充要条件. 12．（2023·第39届全国中学生冬令营）给定素数，定义集合．对于，，定义如下：当时；当时．对于的一个子集，定义．若集合满足且对任意有则称集合为好集合．求最大正整数，使得可以找到个互不相同的好集合，，，，满足． 【答案】 【解析】引理一的证明： 设小弧长度分别为所有不同的连续s段小弧组成的弧长平方之为，则有： 由整数离散性及知， 当取最小值时，应有对任意的 回到原题，对好集合A，若|A|=k，设 则由上述可知 由于当时，可同时取到最小值，因此取最小值时恰同时取到最小值. 故由引理知，此时或特别地，或， 引理二：对于满足条件的好集合A，若，则必存在非负整数t，使得(其中). 引理二的证明：记，则. 若对于每个，均存在另一个使得， 则连一条到的有向线段，则图中必存在圈为下标)， 故，矛盾！ 故存在使得对任意的正整数，由引理一， 知，令即可，引理二得证. 由引理二，对任意，对任意好集合，若，则必存在好集合， 满足且.这是因为，可以不妨设，此时令，由知结论成立. 引理三：当T为好集时，T的补集也为好集. 引理三的证明： 对的补集有： $$ 同理， 故， 即当为好集时，也为好集，引理得证. 故对任意，对任意好集合，若，则必存在好集合，满足且. 引理四：对于任意，对任意的好集合T，若=t，则存在好集合S，满足且. 引理四的证明：不妨设，令(集合中的元素为在模意义下理解)， 则由于，知，此时被的补集所包含，引理四得证. 对好集合，设及， 若，则由引理1及引理. 若，且中至少两个间距取到3： 此时若有两个相邻间距均为3，则由引理一知不存在两个相邻间距均为4(否则连续两段小弧之和为6和8，矛盾). 此时若，则集合中对应长度等于4的小弧被拆分成两个长度等于2的小弧， 此时在中同时存在两个相邻的3及两个相邻的2，同上矛盾.故. 若不存在两个相邻间距均为3，则存在两组连续的弧，两端均为长度为3的小弧， 其内部由长度为4的小弧组成，且长度为4的小弧数量不同(否则所有的弧均匀分布，与为素数矛盾). 设上述两组弧中较短的一组共包含个长度为4的小弧，此时若则将4拆分成两个2， 则同时存在相邻段小弧中有个2及2个3与个2， 由引理一，由于这两组弧的弧长差为2，由引理一矛盾，故. 若，且中恰一个小弧弧长为3，则所有4变为两个2，此时.若，则. 下面计算l的最大可能值. 设为满足要求的l个集合中元素个数小于的集合，由已证结论： 若恒成立，则，否则必有 因此 对元素数大于的集合，由引理三，同理可得这样的集合个数不超过故 另一方面，若，由上述引理，知存在符合要求的集合，使得 若由上述引理，知存在符合要求的集合，使得 综上所述，l的最大可能值为 1 / 43 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $ 专题03 高中数学竞赛二试内容——组合数学 目录概览 A考点精研・竞赛考点专项攻坚 考点一 抽屉原理 2 考点二 极端原理 4 考点三 算两次原理 5 考点四 对策问题 6 考点五 容斥原理 6 题型六 递推问题 7 题型七 母函数法 8 题型八 组合几何 8 题型九 对策问题 11 题型十 图论 11 题型十一 染色问题 13 B实战进阶・竞赛选拔模拟特训（精选各地竞赛、强基试题11道） 【归纳重点知识】 1．定理1（容斥原理）（也称逐步淘汰公式）设是的子集，则 ． 定理2（容斥原理的对偶形式）设是的子集，则 （因为，所以） 2．极端原理 极端原理就是通过讨论“极端”对象来解题的方法，它考虑的是极端情况——最大或最小. 因此，它往往在题目中增加一个（最大或最小）条件，从而使问题巧妙地得以解决.同时， 它常跟反证法结合，通过与“最大”与“最小”的矛盾来解决问题. 通常考虑的极端情况，可以是边最长（最短），最大数（或最小数）等，其在不等式、不定方程、图论及一些组合问题（特别是一些存在性问题）中都经常被用到. 3.抽屉原理 (1)第I型抽屉原理：把个物体放入个抽屉，则至少有一个抽屉的物品不少于个，其中 (2)第II型抽屉原理：把个物体放入个抽屉，则至少有一个抽屉的物品不多于个，其中 4．基本的组合恒等式 简单的组合恒等式的化简和证明，可以直接运用课本所学的基本组合恒等式.事实上，许多竞赛中出现的较复杂的组合数记算或恒等式证明，也往往运用这些基本组合恒等式，通过转化，分解为若干个简单的组合恒等式而加以解决.常见的组合恒等式有： ①； ②； ③； ④； ⑤； ⑥ 考点一 抽屉原理 1．设有限集，对任意，定义．证明以下结论： (1)存在，使得； (2)．其中表示集合中的元素个数，． 2．请阅读以下材料并完成以下问题： 【材料一】范数是定义在向量空间上的一个函数，它为向量空间中的每个向量赋予一个非负的实数值，直观上可以理解为向量的“长度”或“大小”. -范数：在维向量空间中，向量的-范数定义为，其中.如当时，得到1-范数，即，它表示向量各个分量绝对值之和，例如. 再以常见的二维欧几里得空间为例，对于向量，其欧几里得范数（也称为2-范数）定义为，这正是我们熟悉的从原点到向量终点的直线距离，符合我们对向量长度的直观认知. 【材料二】桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果.这一现象就是我们所说的“抽屉原理”. 抽屉原理是德国数学家狄利克雷（P.G.T.Dirichlet，1805~1859）首先提出来的，也称狄利克雷原理.抽屉原理的一般含义为：如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有个元素放到个集合中去，其中必定有一个集合里至少有两个元素. 【材料三】在维向量空间中，对，其中，，定义. (1)若，且，其中，；记为奇数的向量个数为. ①求； ②求（用含的式子表示，其中）； (2)若正整数，若定义集合，其中，，，且；请求出的元素个数；若已知，满足对任意，都有，求的最大值. 3．设为不小于3的正整数，集合满足.设为平面，点，对任意，点，且点满足. (1)若，且，求直线与所成角的大小； (2)证明：； (3)对任意，规定.设点满足.证明：存在，使得对任意，都有，或且与在的不同侧. 考点二 极端原理 4．设集合是由平面上任意三点不共线的4039个点构成的集合，且其中2019个点为红色，2020个点为蓝色；在平面上画出一组直线，可以将平面分成若干区域，若一组直线对于点集满足下述两个条件，称这是一个“好直线组”： （1）这些直线不经过该点集中的任何一个点； （2）每个区域中均不会同时出现两种颜色的点. 求的最小值，使得对于任意的点集，均存在由条直线构成的“好直线组”. 5．名乒乓球选手单打比赛若干场后，任意两个选手已赛过的对手恰好都不完全相同.试证明：总可以从中去掉一名选手，而使在余下的选手中，任意两个选手已赛过的对手仍然都不完全相同. 6．一个由空间中的点组成的集合满足性质：中任意两点之间的距离互不相同．假设中的点的坐标都是整数，并且、、．证明：集合的元素个数小于． 考点三 算两次原理 7．已知集合. (1)“算两次”思想在组合数学中有着重要应用．例如：对于一个元集合的所有子集个数，一方面有，另一方面：对于所有子集，每个中的元素有“出现”和“不出现”两种选择，由分布计数原理可得，因此有．令，试用算两次思想化简； (2)对于的子集个数还可以这样理解：，展开式中每一项都唯一对应着的一个子集．令，试化简； (3)对偶原理也是组合数学的重要方法，例如数学王子高斯小时候在计算的值时，他把与配对，与配对，从而化变量为常量，大大简化了计算．这其实就是对偶原理的一种体现．令，其中是中元素从小到大的一个排列，试用对偶原理化简. 8．数学家波利亚说：“为了得到一个方程，我们必须把同一个量以两种不同的方法表示出来，即将一个量算两次，从而建立相等关系”这就是算两次原理，又称为富比尼原理.例如：如图甲，在△ABC中，D为BC的中点，则，，两式相加得，.因为D为BC的中点，所以，于是.请用“算两次”的方法解决下列问题： (1)如图乙，在四边形ABCD中，E，F分别为AD，BC的中点，证明：. (2)如图丙，在四边形中，E，F分别在边AD，BC上，且，，，，与的夹角为，求向量与向量夹角的余弦值. 考点四 对策问题 9．甲、乙两人分别进行投硬币和掷图钉试验，每人各进行100次试验．设为前k次试验中硬币正面向上的次数，为前k次试验中图钉针尖朝下的次数，记． (1)若，问是否存在常数P，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有P的可能值；若不存在，请说明理由； (2)若，问是否存在常数Q，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有Q的可能值；若不存在，请说明理由． 10．在一张无限大的方格表上的每个方格中填有一个实数．已知任意一个由格线构成的正方形中的数之和的绝对值不超过1．证明：任意一个由格线构成的矩形中的数之和的绝对值不超过4． 考点五 容斥原理 11．从集合的子集中先后取出两个不同的子集、，求以下事件发生的概率： （1），且； （2）Card 12．给定正整数，对于正整数，集合.集族满足如下条件： （1）的每个集合都是的元子集； （2）中的任意两个集合至多有一个公共元素； （3）的任意一个元素恰出现在中的两个集合中. 试求的最大值. 13．一些选手参加数学竞赛，其中有些选手互相认识，有些选手互相不认识，而任何两个不相识的选手都恰有两个共同的熟人．若与认识，但没有共同的熟人，求证：、认识的熟人一样多． 14．国际数学奥林匹克主试委员会有个国家参加，每个国家由领队和副领队两人参加，会前与会者互相握手，但领队不与本国的副领队握手，会后主办国的领队询问与会者握手的次数，所有人的回答却各不相同，主办国的副领队握手次.求实数、的值. 题型六 递推问题 15．已知数列满足，． (1)若是递增数列，求实数的取值范围； (2)若，且对任意大于的正整数，恒有，求的最小值． 16．数列满足且．证明：其中无理数． 17．已知数列满足，，. （1）若对任意的正整数，有，求实数的取值范围； （2）若，且对任意大于1的正整数，有恒成立，求的最小值. 题型七 母函数法 18．已知的非空子集，满足其元素之和为5的倍数．求上述子集的个数． 19.求位十进制数中出现偶数个5的数的个数． 题型八 组合几何 20．设n为一个正整数，三维空间内的点集S满足下述性质： （1）.空间内不存在n个平面，使得点集S中的每个点至少在这n个平面中的一个平面上； （2）.对于每个点，均存在n个平面，使得中的每个点均至少在这n个平面中的一个平面上. 求点集S中点的个数的最小值与最大值. 21．求的最大值，使得平面上有个点，其中任意三点中必存在两点间距离为1． 22．将一枚棋子放在一个的棋盘上，记为从左、上数第行第列的小方格，求所有的四元数组，使得从出发，经过每个小方格恰一次到达（每步为将棋子从一个小方格移到与之有共同边的另一个小方格）. 23．在椭圆外一直线上取个不同的点，过向椭圆作切线、，切点分别为、.记直线为. （1）若存在正整数、（、，），使得点在直线上，证明：点在直线上； （2）试求直线将椭圆分成的区域的个数. 【答案】（1）见解析；（2） 【解析】设椭圆:，直线：，. 则点关于椭圆的切点弦的方程为                    ① （1）直线：，由点在上知. 从而，点也满足方程①，即点也在直线上. （2）当时，直线：，即.    ② 由直线在椭圆外知. 将式②代入式①整理得. 从而，直线恒过定点. 而，故该定点在椭圆内.当时，直线：，即 .    ③ 联立椭圆与直线的方程并化简得. 由直线在椭圆外知 . 将式③代入式①整理得. 此时，直线恒过定点. 而，故该定点在椭圆内. 综上，直线交于椭圆内一定点. 故这条直线将椭圆分成个区域. 24．21世纪城的街道都是东西向和南北向,为了加强安全管理,在一些十字路口设置保安亭(任何两个保安亭都不在同一街道上),以两个保安亭为其两个顶点、街道为边围成的矩形称为一个安全区,安全区(包括边界)内保安亭的个数称为该安全区的安全强度.如果世纪城两个方向的街道都至少有条,且任何两条不平行的街道都交成一个十字路口,今按要求选定个十字路口设置保安亭,求安全强度最大的安全区的安全强度的最小值. 25．已知边长为的正方形及其内部的个点,其中无三点共线.证明:可以选取其中的三个点,以这三个点为顶点的三角形的面积不超过. 26．一士兵要在一个半径为的圆形区域内检查是否埋有地雷，他所用的检查仪器的有效作用范围的半径为．求该士兵从该圆边界上一点出发，至少需走多少米才能将区域检测完，且回到出发点? 题型九 对策问题 27．在一次数学会议上，任意两位数学家要么是朋友，要么是陌生人．在进餐期间，每位数学家在两个大餐厅中的其中一个就餐，每位数学家所在的餐厅中包含偶数个他（或她）的朋友．证明：数学家能被分到两个餐厅中的不同分法的数目是2的正整数次幂（即形如，其中，是某个正整数）． 28．某公司印制了一批文化衫，每件文化衫可有红、黄、蓝三种不同的颜色和四种不同的图案.现将这批文化衫分发给名新员工，每名员工恰好分到图案不同的4件.试求的最小值，使得总存在两个人，他们所分到的某两种图案的4件文化衫的颜色全部相同. 题型十 图论 29．设n为一个正整数，三维空间内的点集S满足下述性质： （1）.空间内不存在n个平面，使得点集S中的每个点至少在这n个平面中的一个平面上； （2）.对于每个点，均存在n个平面，使得中的每个点均至少在这n个平面中的一个平面上. 求点集S中点的个数的最小值与最大值. 30．求的最大值，使得平面上有个点，其中任意三点中必存在两点间距离为1． 31．将一枚棋子放在一个的棋盘上，记为从左、上数第行第列的小方格，求所有的四元数组，使得从出发，经过每个小方格恰一次到达（每步为将棋子从一个小方格移到与之有共同边的另一个小方格）. 32．在椭圆外一直线上取个不同的点，过向椭圆作切线、，切点分别为、.记直线为. （1）若存在正整数、（、，），使得点在直线上，证明：点在直线上； （2）试求直线将椭圆分成的区域的个数. 33．平面上有n个点，其中无三点共线，将这n个点两两相连，用红、黄、绿三种颜色染这些线段，且任意三点所成的三角形的三条边均恰好有两种颜色，证明：． 34．给定一个的方格棋盘，其中有n个格子上各放置一枚棋子．对每个棋子，以其所在格为中心作一个的边平行于相应棋盘边界的正方形，这个正方形称为该棋子的范围．已知每个棋子范围中恰有一个其他棋子，求n的最大值． 35．求一切正整数，满足：可以将一个平面正n边形分割成有限个三角形，使得在这些三角形中，任意两个重叠部分的面积为零．并且任意两个都没有公共边（允许某些三角形的边有公共部分）． 36．某国有2020个城市，若干座城市对之间开通单向航线，使得每座城市恰有一班飞离的航线．求最小的正整数k，使得满足无论怎样开通航线总能将2020座城市分成k组，使得每组中任意一座城市不可能用不超过28次飞行到达这一组中的另一座城市． 题型十一 染色问题 37．给定正整数m、n，一个的正方形由8个白色及1个黑色的的正方形构成，其中黑色正方形在正中间．一个的大正方形由个这样的的正方形构成．现将一些的白色正方形染成红色，使得每个白色正方形都至少与一个红色正方形有公共顶点．求最少的需要染红的正方形的数目． 38．将一个凸2019边形的每条边任意染为红､黄､蓝三种颜色之一，每种颜色的边各673条.证明：可作这个凸2019边形的2016条在内部互不相交的对角线将其剖分成2017个三角形，并将所作的每条对角线也染为红､黄､蓝三种颜色之一，使得每个三角形的三条边或者颜色全部相同或者颜色互不相同. 39．设，为所有满足下列条件的整数数列的个数： （1），，且； （2）不存在、，使得. 试求的值. 40．平面上有一个阶完全图，对其边进行三染色，且每种颜色至少染一条边.现假设在完全图中至多选出k条边，且把这k条边的颜色全部变为给定三色中的某种颜色后，此图同时也可以被该种颜色的边连通.若无论初始如何染色，都可以达到目的，求k的最小值. 1.（多选）（2024·清华大学强基计划）某区域仅有东西向或南北向道路，某人从区域中心出发后又回到起点，且路途中不经过重复区域，已知此人左转次，则其右转次数可以是（    ） A． B． C． D． 2．(2024·清华大学强基计划)已知正方体，初始时与重合，每一步都等可能得移动到相邻顶点，记移动步后仍在面上的概率为，则（    ） A．移动步后，仍在点的概率为 B． C． D．与的递推式为 3．（2024·全国高中数学联赛四川预赛）给定正整数，数组称为“好数组”是指：均不为，且对任意的，均有．求“好数组”的组数． 4．(2022·全国奥赛贵州初赛)已知半径为1的圆上有2022个点，求证：至少存在一个凸337边形，它的面积小于．（，） 5．(2023·第39届全国中学生冬令营)给定一个正99边形，将1，2，，99放入99边形的99个顶点处，若两种放置方法在旋转之后可以重合，则称这两种方法是同一个.称交换某两个相邻顶点上的数为一次操作，求最小的使得至多次操作可以将一种放置方法变为任意另外一种放置方法. 6．（2023·全国高中数学联赛加试）求具有下述性质的最小正整数：若将中的每个数任意染为红色或者蓝色，则或者存在9个互不相同的红色的数满足，或者存在10个互不相同的蓝色的数满足. 7．（2022·浙江宁波高中数学竞赛）甲、乙两人分别进行投硬币和掷图钉试验，每人各进行100次试验．设为前k次试验中硬币正面向上的次数，为前k次试验中图钉针尖朝下的次数，记． (1)若，问是否存在常数P，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有P的可能值；若不存在，请说明理由； (2)若，问是否存在常数Q，不论试验过程中如何变化，均存在某个，使得？若存在，求出所有Q的可能值；若不存在，请说明理由． 8．（2022·全国中学生奥赛贵州初赛）甲乙二人轮流给一个正方体的棱涂色，首先，甲任选3条棱涂成红色，然后乙从余下的9条棱中任选3条涂成绿色，接着甲从余下的6条棱中任选3条涂成红色，最后乙将余下的3条棱涂成绿色，如果甲能将某个面上的4条边全都涂成红，甲就获胜，试问甲有必胜策略吗？说明理由． 9．（2022·全国高中数学联赛苏州选拨赛）定义：如果甲队赢了乙队，乙队赢了丙队，而丙队又赢了甲队，则称甲乙丙为一个“友好组”. (1)如果19支球队参加单循环比赛，求友好组个数的最大值； (2)如果20支球队参加单循环比赛，求友好组个数的最大值. 10．（2024·全国鱼塘杯竞赛）对集合，定义其特征函数，考虑集合和正实数，定义为和式函数.设，则为闭区间列；如果集合对任意，有，则称是无交集合列，设集合. (1)证明：L和式函数的值域为有限集合； (2)设为闭区间列，是定义在上的函数.已知存在唯一的正整数，各项不同的非零实数，和无交集合列使得，并且，称为和式函数的典范形式.设为的典范数. （i）设，证明：； （ii）给定正整数，任取正实数和闭区间列，判断的典范数最大值的存在性.如果存在，给出最大值；如果不存在，说明理由. 11．（2023·第39届全国中学生冬令营）对任意满足的非负实数组，记为的元素个数，求证：，并给出取等的充要条件. 12．（2023·第39届全国中学生冬令营）给定素数，定义集合．对于，，定义如下：当时；当时．对于的一个子集，定义．若集合满足且对任意有则称集合为好集合．求最大正整数，使得可以找到个互不相同的好集合，，，，满足． 1 / 43 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $