专题22 组合数学（下）（数学竞赛真题汇编）高中数学全国通用

专题22 组合数学（下） 一、填空题 1．（2024·四川预赛）若，则的末尾数字0的个数为 ． 2．（2024·吉林预赛）已知甲、乙、丙、丁四位同学对某10道判断题的解答情况如下表： 若甲、乙、丙三人均答对7题，则丁答对的题数为_____． 3．（2024·浙江预赛）若对所有大于2024的正整数，成立，则 ． 4．（2024·浙江预赛）设为正整数，且，则 ． 5．（2024·上海预赛）计算 ． 6．（2023·吉林预赛）若在的任意一个排列中，总能找到连续6个数之和不小于，则实数的最大值为_____． 二、解答题 7．（2025·江苏预赛）有9支队伍进行单循环赛（任意两队之间进行一场比赛）．在比赛了一阶段后进行统计，发现任意3支队伍之间最多进行了两场比赛，求此时这9支队伍之间的比赛总场次的最大值，并说明理由． 8．（2025·北京预赛）有2025张数字卡片，上面分别写有数字1至45，每个数字卡恰有45张．现在，有45位高中生参加交换卡片的游戏，每次交换由两位同学参与，他们两人各自将某一张手中的卡片交给对方．每人最初持有45张卡片．求证：至少存在一种交换方案，每个卡片至多只参加一次交换，使得最终每人手中都有1至45号卡片各一张． 9．（2024·广西预赛）图G是指一个有序二元组，其中V称为顶点集，E称为边集．一个图G中的两点x，y的距离是指从x到y的最短路径的边数，记作．一个图G的直径是指G中任意两点的距离的最大值，记作，即．记是模的剩余类，定义上的加法和乘法，均是模的加法和乘法，例如在中，；，．在中，设．若存在使得，则称是的一个零因子．记的所有零因子的集合为．例如．的零因子图，记为，它是以为顶点集，两个不同的顶点，之间有一条边相连当且仅当．下图是的例子．证明：对一切的整数，都有． 10．（2023·北京预赛）某校举办数学文化节，据统计当天共有980多(不少于980，小于990)名同学进校参观，每位同学进校参观一段时间后离开(之后不会再进来)．若无论这些同学以怎样的时间安排参观，我们都能找到位同学，使得要么这位同学在某个时间都在校园内参观，要么任何时间他们中都没有两个人同时在校园内参观．求的最大值． 11．（2023·东莞预赛）已知，以为边长的正方形能互不重叠地全部放入一个边长为的正方形内，求的最小值． 12．（2023·山东预赛）的表格内填入1到100，第行第列填入．每次操作如下：取一个格子，或者将此格数字减少2，将两个相对的邻格同时加1；或者将此格数字增加2，将两个相对的邻格同时减1．证明：如果经过一些步骤后表格中又得到1到100的数字，则它们是按原来的顺序排列的． 13．（2022·福建预赛）某校数学兴趣小组有14位同学，他们组成了个不同的课题组．每个课题组有6位同学，每位同学至少参加2个课题组，且任意两个课题组至多有2位共同的同学，求的最大值． 14．（2022·苏州预赛）定义：如果甲队赢了乙队，乙队赢了丙队，而丙队又赢了甲队，则称甲乙丙为一个“友好组”． (1)如果19支球队参加单循环比赛，求友好组个数的最大值； (2)如果20支球队参加单循环比赛，求友好组个数的最大值． 15．（2022·吉林预赛）个学生参加一次数学考试，试卷由道题组成，考虑如下的统计结果：设是一个实数，至少有道题为难题（一道题是难题是指至少有个学生未解出此题），且至少有个学生及格（一个学生及格是指他至少解决了道题）．试分别就确定上述情形是否有可能，并说明理由． 16．（2022·贵州预赛）已知半径为1的圆上有2022个点，求证：至少存在一个凸337边形，它的面积小于) 一、解答题 1．（2025·全国联赛B卷）给定整数．设是由个不同的正整数构成的集合，记为集合的元素个数．证明：，并且存在集合使得． 2．（2024·全国联赛B卷）给定正整数．在一个的方格表上，由一些方格构成的集合称为“连通的”，如果对中任意两个不同的小方格，存在整数及中个方格，满足与有公共边． 求具有下述性质的最大整数：若将该方格表中的每个小方格任意染为黑色或白色，总存在一个连通的集合，使得中的黑格个数与白格个数之差的绝对值不小于． 3．（2023·全国联赛B卷）设是给定的整数，．求具有下述性质的最小正整数：若将中的每个数任意染为红色或者蓝色，则或者存在个红色的数（允许相同），满足，或者存在个蓝色的数（允许相同），满足． 4．（2022·全国联赛B卷）圆周上依次有100个点(其中与相邻)．现有5种颜色，要求中每个点染5种颜色之一，每种颜色至少染一个点．若对任意这样的染色方式，中总存在个连续的点含有至少3种颜色，求的最小值． 5．（2022·全国联赛A2卷）已知集合的四个500元子集，满足：对任意，均存在某个，使得．求正整数的最大可能值． 1 / 1 学科网（北京）股份有限公司 $ 专题22 组合数学（下） 一、填空题 1．（2024·四川预赛）若，则的末尾数字0的个数为 ． 【答案】3 【详解】由于， 故， 由于 ， 由于，末尾有3个0，且大小远远超过1000， 因此的末尾数字0的个数为3． 2．（2024·吉林预赛）已知甲、乙、丙、丁四位同学对某10道判断题的解答情况如下表： 若甲、乙、丙三人均答对7题，则丁答对的题数为_____． 【答案】6 【详解】若某两人对同一道题的答案是不同的，则其中必有一人答错． 因为甲与乙有6道题的答案不同，而甲与乙共错了6题， 故甲与乙错的题都在这对应的6题中， 由此可得第题的正确答案分别为×，√，√，×； 同理，甲与丙也有6道题的答案不同，乙与丙也有6道题的答案不同， 从而可得这10道判断题的正确答案． 题号 1 2 3 4 5 6 7 8 9 10 正确答案 × √ × √ √ √ √ √ × × 丁 × × √ √ × × √ √ × × 对比正确答案，可知丁答对了6题． 3．（2024·浙江预赛）若对所有大于2024的正整数，成立，则 ． 【答案】 【详解】因为，，， 设，为正整数， 那么，以及， 得到为正整数． 所以，，故． 4．（2024·浙江预赛）设为正整数，且，则 ． 【答案】9 【详解】记， 所以 又，，故 解得． 5．（2024·上海预赛）计算 ． 【答案】 【详解】由于 ， 于是，． 综上可． 6．（2023·吉林预赛）若在的任意一个排列中，总能找到连续6个数之和不小于，则实数的最大值为_____． 【答案】57 【详解】在的任意一个排列中，从左至右连续6个数为一组，共分为三组．由于三组的和为，则由抽屉原理，必至少有一组的和不小于57，即． 将排列为18，1，17，2，16，3，15，4，14，5，13，6，12，7，11，8，10，9，此时满足任意连续6个数之和均不超过57．所以实数的最大值为57． 二、解答题 7．（2025·江苏预赛）有9支队伍进行单循环赛（任意两队之间进行一场比赛）．在比赛了一阶段后进行统计，发现任意3支队伍之间最多进行了两场比赛，求此时这9支队伍之间的比赛总场次的最大值，并说明理由． 【答案】20． 【详解】将队伍看成点，两支队伍进行比赛则在相应两点间连边，从而翻译为图论问题，则要研究的是，若在9个点的简单图中没有三角形，求边数最大值．这正是托兰定理的直接而简单的特例．托兰定理是说，阶图中若不含（阶完全图），则图中的边数最大值在下述情况下取到：个点被分成点数尽可能均匀的组，同组的任意两点间无边相连，不同组的任意两点间有边相连．本题是这一特例． 为了使边数尽可能多，将9个点分成4个点和5个点的两组，同组的任意两点间无边相连，不同组的任意两点间有边相连，从而图中有20条边．下面只须再证明，无论怎样安排，这9个点间的边数总不超过20．设引出最多边的点为，它引出这条边，则间无边相连（否则立刻与构成了三角形），这样，对任意，它引出的边数不超过．而由的最大性知，对以外的个点中的任一个而言，引出的边数不超过．因此图中边的总数不超过． 8．（2025·北京预赛）有2025张数字卡片，上面分别写有数字1至45，每个数字卡恰有45张．现在，有45位高中生参加交换卡片的游戏，每次交换由两位同学参与，他们两人各自将某一张手中的卡片交给对方．每人最初持有45张卡片．求证：至少存在一种交换方案，每个卡片至多只参加一次交换，使得最终每人手中都有1至45号卡片各一张． 【详解】构造以这45个人和45个数字为顶点的二部图．若某人有某个数字的卡片，则在相应的人与数字之间连边（允许重边）．因为每个人都有45张卡片，且每个数字的卡片恰有45张，所以这是一个45-正则的二部图．于是由Hall定理，它可以分拆为45个完美匹配的并．现在，构造的方格表，在各列中依次放入这45个人的卡片，每个人占据一列．由前述结论，可以使每行卡片的数字互不相同． 接下来，将方格表关于主对角线作对称变换，这相当于做了多次双方交换卡片的操作，且每张卡片至多参与一次交换．此时每列卡片的数字互不相同，即每个人的45张卡片是45个不同数字，满足要求． 9．（2024·广西预赛）图G是指一个有序二元组，其中V称为顶点集，E称为边集．一个图G中的两点x，y的距离是指从x到y的最短路径的边数，记作．一个图G的直径是指G中任意两点的距离的最大值，记作，即．记是模的剩余类，定义上的加法和乘法，均是模的加法和乘法，例如在中，；，．在中，设．若存在使得，则称是的一个零因子．记的所有零因子的集合为．例如．的零因子图，记为，它是以为顶点集，两个不同的顶点，之间有一条边相连当且仅当．下图是的例子．证明：对一切的整数，都有． 【详解】设，．如果，那么．下设． （1）若，则是一条长为2的路径，因此． （2）若，，由零因子的定义知道，存在，使得． 若，则是一条长为2的路径，因此； 若，则是一条长为3的路径，因此． （3）若，，则类似（2）可证得或． （4）若且，则由零因子得定义，存在，使得，． 若，则是一条长为2的路径，因此． 若，但，则是一条长为3的路径，因此． 若，且，则是一条长为2的路径，因此． 综上所述．因此，． 10．（2023·北京预赛）某校举办数学文化节，据统计当天共有980多(不少于980，小于990)名同学进校参观，每位同学进校参观一段时间后离开(之后不会再进来)．若无论这些同学以怎样的时间安排参观，我们都能找到位同学，使得要么这位同学在某个时间都在校园内参观，要么任何时间他们中都没有两个人同时在校园内参观．求的最大值． 【详解】的最大值为32．设学生人数为，则． 一方面，将参观的同学分为32组，前面31组每组31人，第32组有人．每一组同时进出校园，且各组之间无重叠时间．则此时任何时间至多有31位同学在校园参观，至多可选出32位同学(每组选出1人)，满足任何时间他们中都没有两个人同时在校园内参观．于是． 另一方面，设的最大值为，考虑第一个出校园的同学，及在他出校园之前进校园的人称为第1组；第1组清场之后其余人再进场，仍考虑第一个出校园的同学，及在他出校园之前进校园的人称为第2组；重复上述分组方式，则存在相应的与第3组，与第组，直至所有名同学全部分组完毕． 在上述分组中，任何时间至多有1组同学在校园参观(由假设可知其中人数不超过)，且中没有两人同时在校园内参观，则．因此总人数不超过，矛盾． 综上，的最大值为32． 11．（2023·东莞预赛）已知，以为边长的正方形能互不重叠地全部放入一个边长为的正方形内，求的最小值． 【详解】如图，以为边长的正方形能互不重叠地放入一个边长为的正方形内，则． 对于， 于是以为边长的正方形可以互不重叠地全部放入长为1，高为的矩形内． 当时，以为边长的正方形可以互不重叠地全部放入长为1，高为的矩形内； 当时，以为边长的正方形可以互不重叠地全部放入长为1，高为的矩形内；； 因此边长为的正方形可以互不重叠地全部放入长为1，高为的一系列矩形内， 且， 即边长为，的正方形可以互不重叠地全部放入长为1，高为的矩形中． 又当时，以为边长的正方形可以互不重叠地放入长为1，高为的矩形内， 所以以为边长的正方形能互不重叠地全部放入一个边长为的正方形内． 综上，的最小值为． 12．（2023·山东预赛）的表格内填入1到100，第行第列填入．每次操作如下：取一个格子，或者将此格数字减少2，将两个相对的邻格同时加1；或者将此格数字增加2，将两个相对的邻格同时减1．证明：如果经过一些步骤后表格中又得到1到100的数字，则它们是按原来的顺序排列的． 【详解】将第行第列的格子记为表格的第个格子，某次操作后，该格子填入的数为． 令，下面证明为操作中的不变量． 经过一次操作后，第个格子的数为，第个格子的数为，第个格子的数为； 或者第个格子的数为，第个格子的数为，第个格子的数为； 或者第个格子的数为，第个格子的数为，第个格子的数为； 或者第个格子的数为，第个格子的数为，第个格子的数为． 则 ， 同理可检验其它情况下也有成立，因此为上述操作中的不变量． 由于初始值为，依排序不等式知，它是当为的任一排列中对应和式的最大值，且最大值时的排列方式是唯一的． 所以经过一些步骤后表格中又得到1到100的数字，则它们是按原来的顺序排列的． 13．（2022·福建预赛）某校数学兴趣小组有14位同学，他们组成了个不同的课题组．每个课题组有6位同学，每位同学至少参加2个课题组，且任意两个课题组至多有2位共同的同学，求的最大值． 【详解】将14位同学记为，课题组集合记为．则， ，且． 设属于中的个集合，则，且． 考虑三元数组的个数，其中． 一方面，固定，由于至多有2个属于三元数组， 于是； 另一方面，固定，由于属于中的个集合， 于是的个数为．从而 因此． 又14位同学按照下列方式组成的7个课题组符合要求： ． 综上，的最大值为7． 14．（2022·苏州预赛）定义：如果甲队赢了乙队，乙队赢了丙队，而丙队又赢了甲队，则称甲乙丙为一个“友好组”． (1)如果19支球队参加单循环比赛，求友好组个数的最大值； (2)如果20支球队参加单循环比赛，求友好组个数的最大值． 【详解】证明结论：当球队个数为奇数时，友好组个数的最大值为； 当球队个数为偶数时，友好组个数的最大值为． (1)当为奇数时，令，由于有支球队进行单循环比赛，则总共有场比赛．设有个友好组，考虑其反面，若甲乙丙三队为非友好组，设甲队赢了乙队和丙队，此时记甲队为非友好组的组长． 对甲队而言，可以在它赢的所有队伍中任意选择两队构成非友好组．因此，若队，在比赛中赢了场，则，且以为组长的非友好组有个(补充定义：．于是非友好组的个数为 等号成立时． 故有． 构造例子：在共支球队中，队胜，负， ，其中下标是在模意义下的，则友好组的个数为． (2)当为偶数时，同上分析，若队在比赛中赢了场，则， 且以为组长的非友好组有个(补充定义：)． 于是非友好组的个数为．下求的最小值． 若在中，不妨设．则令，其余,． 于是 故调整后变小． 重复上述操作，直至任意两个数的差至多为1．不妨设中有个 个，则有 ，由于，于是． 即调整后有个个． 故有． 构造例子：在共支球队中，当时，队胜； 当时，队胜，其中下标是在模意义下的， 则友好组的个数为． 综上，当球队个数为奇数时，友好组个数的最大值为； 当球队个数为偶数时，友好组个数的最大值为． 15．（2022·吉林预赛）个学生参加一次数学考试，试卷由道题组成，考虑如下的统计结果：设是一个实数，至少有道题为难题（一道题是难题是指至少有个学生未解出此题），且至少有个学生及格（一个学生及格是指他至少解决了道题）．试分别就确定上述情形是否有可能，并说明理由． 【详解】设难题有道，及格的学生有，并记道题为(其中前道题为难题)，个学生为(其中前个为及格学生)人．作一个的数表，若解决了，就在第行第列交叉的方格上填上1，否则填上0． 考虑左上角行列的部分，这部分有个数． 对任何一个及格学生，设他解决了道难题，道容易题，则，而 又，这说明左上角数表中每一行 至少有个行中至少有个1． 同理，对任何一道难题，设及格学生中有个未解决此题，不及格学生中有 个学生未解决此题，则，而 ．又， 这说明左上角数表中每一列至少有个列中至少有个0． 于是， 所以时，上述情形是不可能的． 当时，令解出解出解出，满足题意，即上述情形是可能的． 16．（2022·贵州预赛）已知半径为1的圆上有2022个点，求证：至少存在一个凸337边形，它的面积小于) 【详解】如图，正六边形将圆等分为六段圆弧，由于，则六段圆弧中必有一段圆弧上含2022个点中的至少337个点．不妨设在圆弧上依次存在点可与，于是． 而， 所以． 一、解答题 1．（2025·全国联赛B卷）给定整数．设是由个不同的正整数构成的集合，记为集合的元素个数．证明：，并且存在集合使得． 【详解】设，其中正整数． 对，令集合 则对，由正整数可知 ．① 再令集合，则 ．② 由①、②知是的两两不交的子集．又，且，，从而 ．③ 下面构造一个集合，使得． 取，则对任意，有，且为正整数，故，结合③知此时． 2．（2024·全国联赛B卷）给定正整数．在一个的方格表上，由一些方格构成的集合称为“连通的”，如果对中任意两个不同的小方格，存在整数及中个方格，满足与有公共边． 求具有下述性质的最大整数：若将该方格表中的每个小方格任意染为黑色或白色，总存在一个连通的集合，使得中的黑格个数与白格个数之差的绝对值不小于． 【解析】所求的最大值为． 首先证明，对任意摆放的黑格、白格，都有．定义：有公共边的格子称为“相邻”的． 设有个黑格，个白格，不妨设，取黑格较多的一行． 设有个黑，个白，另一行有个黑，个白．则． 由对称性，记黑格较多(相等则任取即可)的一行为第1行，另一行为第2行．记集合为：第1行所有格子以及第2行的所有黑色格子所组成的集合． 下面说明此时是连通的： (1)任选两个格子、如果都在第1行，则取该两个格子以及其中间的所有格子，从左至右依次记为，由于与均有竖直相邻边． (2)任选两个格子，如果存在格子在第2行，由于第1行所有格子均是中的元素，则选择第2行格子相邻的第1行格子，这样就转化为(1)的情况． 由(1)(2)可以说明是连通的． 由于，则，得，即证． 下面给出的构造． 不妨设黑色格子不少于白色格子． 如下图，对所有格进行黑白相间染色．从图1中自左至右依次截取图形，我们考察黑色格子与白色格子数量之差． 若差值为2，则黑色格子为2，白色格子为0，此时选择该两个黑色格子，不妨设在图形右上格子，则的左边、下边相邻的格子不是集合的元素，故不存在满足与有公共边，即至少之一成立，这与差值为2的构造矛盾．故每一个图形的黑色格子与白色格子之差至多为1．共有个图形，至多剩余一个的图形，且黑色格子与白色格子各一个，则其黑色格子与白色格子之差至多为1．总上所述，． 3．（2023·全国联赛B卷）设是给定的整数，．求具有下述性质的最小正整数：若将中的每个数任意染为红色或者蓝色，则或者存在个红色的数（允许相同），满足，或者存在个蓝色的数（允许相同），满足． 【详解】若，将染为蓝色，染为红色．则对任意个红色的数，有，对任意个蓝色的数，有，上述例子不满足要求． 对，可在上述例子中删去大于的数，则得到不符合要求的例子．因此所求． 下面证明具有题述性质． 假设可将中的每个数染为红色或蓝色，使得结论不成立． 情形一：若1是红色的数，则红色的数均不超过，否则可取一个红色的数，再取，则，与假设矛盾． 故均为蓝色的数，此时取 有 与假设矛盾． 情形二：若1是蓝色的数，则同情形一可知蓝色的数均不超过，故均是红色的数．此时取，与类似，可得矛盾． 故时结论成立． 综上，所求最小的正整数． 4．（2022·全国联赛B卷）圆周上依次有100个点(其中与相邻)．现有5种颜色，要求中每个点染5种颜色之一，每种颜色至少染一个点．若对任意这样的染色方式，中总存在个连续的点含有至少3种颜色，求的最小值． 【详解】解法1：首先，让分别染颜色1，2，3，4，其余点染颜色5．此时中任意25个连续的点只含有两种颜色，不符合要求．从而至少为26． 以下假设有一种染色方式，使得任意26个连续的点含有至多两种颜色．对该染色方式，在中选取尽可能多的连续的点，使这些点中不含全部5种颜色，从而恰好含有4种颜色(否则可再添入这些连续的点的一个相邻点，仍不含全部5种颜色)．不妨设选出的点是，且这个点不含颜色1．由极端性，可知与均染有颜色1． 对，用表示染有颜色的点的最大下标，则． 由对称性，可不妨设，则，且易知． 对每个，我们证明． 事实上，假如，考虑26个连续的点(下标模100理解，下同)，其中染有颜色染有颜色，而所染的颜色异于和(当时，必有；当时，由于，故)，即这些点中含有至少3种颜色，与假设矛盾． 从而有，这与矛盾． 以上表明，对任意符合要求的染色方式，中总存在26个连续的点含有至少3种颜色． 综上，所求的最小值为26． 解法2：首先，让分别染颜色1，2，3，4，其余点染颜色5．此时中任意25个连续的点只含有两种颜色，不符合要求．从而至少为26． 以下证明符合要求． 考虑任何一种染色方式，对，用表示中染颜色的点的个数，其中． 考虑含有颜色1的弧段的数目，其中下标模100理解． 若任意26个连续的点都含有颜色1，则． 若存在26个连续的点不含颜色1，不妨设染为颜色1的所有个点分别为，则是个两两不同的弧段，从而． 这表明． 同理，对于，含有颜色的弧段的数目满足 所以，其中记． 若中存在一个数不小于75，不妨设，则 若都小于75，则 所以 由抽屉原理，必存在一个弧段被至少种颜色对应到，该弧段所覆盖的26个点含有至少3种颜色． 综上，所求的最小值为26． 5．（2022·全国联赛A2卷）已知集合的四个500元子集，满足：对任意，均存在某个，使得．求正整数的最大可能值． 【详解】所求最大的． 一方面，当时，令 则，且． 考虑．对任意，若其中有一个属于，则同时属于中的某个集合；若均不属于，则同时属于．在中任意添加中一个元素，使其成为500元集合，这便得到的四个500元子集满足要求． 另一方面，若，则不存在满足要求的四个500元子集． 用反证法，假设存在满足要求的四个500元子集，易知的每个元素至少属于其中两个子集，设有个元素恰属于其中两个子集，则 故．记这个元素构成的集合为，则．将中的元素按所属的情况分为6类，对，记是中恰属于的元素的集合． 易知与必有一个是空集，不妨设．同样地，与必有一个是空集，不妨设．同理，与必有一个是空集． 若，则，从而，这样，矛盾． 若，则，从而中的每个元素至少属于中的两个集合，这样，矛盾． 1 / 1 学科网（北京）股份有限公司 $