2024年全国第13届数学竞赛命题研讨资料（组合部分）

湖南省长沙市第一中学 2024第13届数学竞赛命题研讨资料（组合部分） (详解版) 韩序舜 1 ★★★ 答案 解析 对于正整数 , 有 个集合，满足 : 每个集合有 个元素; 任意两个集合恰有一个公共元素; 所有 个集合交集为空集. 求 的 大值. 由题意，在这 个集合中，存在一个被共用的元素不止一个的集合．( 否则，每一个集合和其他集合共用 同一个元素，会导致所有集合共用同一个元素 ) 设该集合为 , 其中的元素为 . 不妨设元素 , 被其他集合共用，设包含元素 的集合有 个，分别为 , , , , 包含元素 的集合有 个，分别为 , , , . 考虑对于满足 , 的正整数 , , , 我们有 : 因为，若 ，则会导致 和 的公共元素至少有 和 ，与题目条件 矛盾． 于是 与 , , , 之间两两的公共元素互不相同，而 中的元素中，能与 , , , 共 用的只有 个，（ 不能共用）故 . 同理可知， 中，每个元素至多属于 之外的 个集合，于是集合的总个数 至多为 个． 另一方面，我们给出下列构造满足条件 : 取 ； 在平面直角坐标系上取点集 , 取 , , ； 2024年全国高中数学联赛竞赛第1题15分 一、组合问题 1 对 , ，集合 包含以下 个元素 : 第一个为 ，第 个元素 为如下产生的点：过点 作斜率为 的直线，与直线 产生交点 ，再将横坐标 在模 的意义下变为 到 之间的数．如集合 . 容易验证，上述 个集合满足条件，所以 的 大值为 . 注 该题目为对下述题目的引申思考 : 设有 个集合，每个集合有 个元素，任意两个集合的并集有 个元素，问此 个集合的 并集有多少个元素 ? 另外，本题的构造和 定理有某些共通之处，其内容为：平面上不共线的 个点两 两相连，至少会得到 条直线，等号成立当且仅当这些线构成一个射影平面，或者构成一个拟束．本题构 造中的 类似于射影平面中的无穷远直线的情形，而问题 中的结构类似于拟束的情形． 江西科技学院附属中学 张敬德 2 ★★★ 答案 解析 某次研讨会共有 人参与，每人至少认识其中 人，试求 的 小值，使得其中必存在彼此认识的 人. 设这 人的集合为 , 所认识的人的集合记为 , , 则 , 若 , 是 中认识的 人，则 . 当 , 不妨设 , 即 , , 彼此认识, 则 . 2024年全国高中数学联赛竞赛第2题15分 二、组合问题 2 当 , 不妨设 , 即 , , , 彼此认识, 则 . 依此类推，可得 , , , 彼此认识, 则 ． 当 ，不妨设 ，即 , , , 彼此认识． 由 ，得 , 即 . 下面再说明 是 小的．否则，若 ，我们将 个人均分成 , , , 这 组，每组 人．令同组的人互不相识，不同组的人均彼此认识，则 中任一人所认识的人数均为 . 现在我们从 中任取 人，则必有 人来自同一组，他们互不相识，这与题设“必存 在彼此认识的 人”矛盾． 综上所述， 的 小值为 . 北京大学附属中学 陈宣桦 3 ★★★ 答案 解析 在单位正方形内部放置 个不同的点，证明 : 一定可以选取其中 个点顺次用线段连接，使得这 条线 段的长度之和不超过 ; 同时，对于正整数 , 一定可以选取其中 个点顺次用线段连 接，使得这 条线段的长度之和不超过 . 见解析 证明 引理一 : 在 的矩形中放置不超过 个点，一定可以顺次连接它们，使得总 长度不超过 . 不妨设矩形顶点为 , 不妨补成 个点，总长度不减，设所有点的坐标为 . 按照横坐标从小到大 个一组，将所有点均分为 份，则可划分 个 矩形使得每组 的 个点都在一个矩形的内部或边上，且 . 首先将每个矩形中的点按纵坐标从小到大进行连接，形成 个组. 2024年全国高中数学联赛竞赛第3题15分 三、组合问题 3 然后如下图所示，可以有两种方式构建组间连接线段，使得整体是一个折线. 考虑将所有线段的长度放大为其横纵投影之和来估计线段组的总长度. 从纵投影看，两种方案皆至多占 个 ; 除了组间连接线段之外，第 组的线段的横投影不超过 , 合计不超过 . 因此上述两种连接方式线段总长都不超过 ( 是此方式组间连接线段的水平投影 长度之和). 注意到两种连接方式的组间连接线段的水平投影长度之和不超过 , 因此至少有一种连接方式的总长不超 过 . 引理二 : 在边长为 的正方形中有 个点，则可以选取 个点顺次连接总长不超过 , 若将 个点的横坐标从小到大排列，则纵坐标构成一个长为 的序列; 则或者存在一个长为 的不增子列，或者存在一个长为 的不减子列 ( 定理 ) 表示在点列中，则或者存在一个长为 的向右上 ( 含向右或向上 ) 的子列，或者存在一个长为 的向右下 ( 含向右或向下 ) 的子列，考虑将其顺次连接总长放缩为投影长度，则恰为首尾两点的横坐标之差 加上纵坐标之差. 现在将边长为 的正方形旋转 后进行点的选取，如图所示，可注意到任两点的横纵坐标差之和不会超 过 . 1 2 2 利用引理二选取 个点，由抽屉原理得前 个点和后 个点中必有一组总长不超过 . 对于第二小问，将正方形如图分割为中心对称的“井字形”,不妨设其中中心正方形的边长为 , 则 区域的边长为 , 若其中有至少 个点，则由引理二存在 个点顺次连接总长不超过 . A B C D E F G H I 若不存在，则同理有 , , . 相加减去总和得 : . 可不妨设 中至少有 个点 因此由引理一，可以全部连接这些点使得总长不会超过 , 而共有 条线段，至 少可以依次分成 组 个线段. 令其中至少有一组不大于 , 取 , 则存在 个 点顺次连接总长不超过 . 注 注意到放置更多的点只会使结果更优，在北京市邀请赛中选择了 个点, 此时 . 取 , 则可以得到 , 在原题中仅要求总长小于 . 本题是对旅行商 问题的一个小方面的探索. 学而思广州分校 余泽伟 4 ★★★ 对 , , , , 为大于 的正整数, , 为 个储存位置，把 填入这 个储存位置中，每个位置恰填一个数. 定义一次操作 : 选取一个 , 把 根据除第 个维度以外坐标相同分组，共 组，把每组的 个数 按第 个维度坐标升序重新排列填回 中. 对于不能再有变化的状态称为稳定状态. 求 小的 , 使对任意的初始状态，都可用不超过 次操作变为稳定 2024年全国高中数学联赛竞赛第4题15分 四、组合问题 4 答案 解析 先证 . 在 中填入 ，有定义知每个数在一次操作中只能改变一个维度的坐标，而 稳定状态 应在 中，所以 . 再证 时必能变为稳定状态，具体操作为依次选择 即可. 定义 : 一种状态下操作 均无变化，称这种状态为 “ 稳定”. 下面归纳证明依次操作 后为 “ 稳定”. 当 时，成立. 当 成立时，对 反证，若 “ 稳定” 状态 下，再操作 后状态 不为 " 稳定”, 则由定义知 不为 “ 稳定”. , 的 中为 , 中为 , 其中 , , 均为坐标的第 个维度. 记 的 中为 , 中为 , 均为坐标 的第 个维度，其中 , , 因操作 后状态为 , 则两个数列单调递增， 任意重排两个数列，仍存在 , 而操作前状态为 , 的 中为 , 中为 , 与 为 “ 稳定” 矛盾．即 成立. 综上所述, 的 小值为 . 江西师大附中 陈思洲 5 ★★★ 答案 解析 城市之间有 个不同的航线，每条航线的起点、终点为 城市且均为双向航线．每两条航线除 城市 外还恰有一个公共站点，任意三条航线间无公共站点．小数同学想要完成这样的挑战 : 从 城市乘航班出发，每到 某两个航线的公共站点，就立即换乘与原航班方向相反的航班 ( 如原先采坐的是 的航班，则立即换乘 方向的航班 ), 挑战乘一定次数后到达 城市．请问 : 对什么样的 , 小数可以保证完成挑战 ? 对所有奇数 成立． 对所有奇数 成立．为便于叙述，将两城市 和所有公共站点称为 “点位”, 设 条航线分别为 , , , . 2024年全国高中数学联赛竞赛第5题15分 五、组合问题 5 一方面 : 当 为偶数时，构造一种航线安排使其无法完成挑战 : 取 与 其中 , . 满足它们两条航线的公共站点在 航线上比 与 的公共站点更接近 城市; 在 航线上比 与 的公共站点更接近 城市． 此时，对于配对的两航线 与 , 小数无论从这两条中的哪条航线离开 , 在到达 与 的公共站 点后, 必然会沿原航线 或 返回到 城, 故无法完成挑战. 另一方面，当 为奇数时，小数的策略是 “每到一个公共站点，立马换另一条航线继续出发，直到到达 或 停止” 小数在选取了该策略后，选择某个航线出发，则有以下事实 : 小数在有限次搭乘后一定会停止，即回到 城或到达 城 设 条航线间的 个公共站点分别为 , , , . 并记 城为 , 城为 . 假设小数从 城出发后不再回到 城或 城，设他 经过的点位为 . 由于点位只有有 限多个，故存在 , 使得 , 在 中出现一次以上． 此时取 小的 , 使得存在 , 满足 且 . 若 , 则 为 即 , 故 表示 城，矛盾; 若 , 设 , , 则 与 均在 中出现．设 出现在航线 上，则 与 均在以航线 有公共站点 的另一条航线上，且均与 的方向相反．于是 与 在同一天航线上且方向相同则 , 这与 的 小性矛盾. 小数从 城选择相同的航线出发，结果是一样的 若小数从 城乘航线 出发后，依次经过点位 , , , 后通过航线 回到 城．则对称地有 : 若小数从 城沿着航线 出发，也将依次通过点 , , , , 并通过航线 回到 城． 回到原问题，假设小数无法到达 城 则对 , 存在 , 使小数通 过航线 出发以后必可以通过航线 回到 城．由 得, . 此时将 与 配对，由于 为奇数，故存在 使得 . 设从 城沿航线 出发后依次经过点位 , , , 后沿航线 回到 城．则由 和 得到 , , , 与 , , , 是相同的， 故 与 相同. 若 为偶数，则令 , 则 与 相同，矛盾． 若 为奇数，则令 , 则 与 相同，故从 到 的航线与 到 的航线相同，这与小数需要在公共站点换乘矛盾．于是小数不能回到 城，故当 为奇数时，小数 必然能够到达 城. 学而思总部 王正 6 ★★★ 答案 解析 已知 星球上有一亿座城市，初始时城市之间没有任何航线，现有一个航空公司准备建立 条双向航线， 每条航线连接两个不同城市，且无两条航线连接相同的两个城市 每座城市的 “繁荣度” 定义为从该城市出发的航线数 目．每条航线的 “收益” 为它所连接的两个城市的繁荣度之乘积. 求这 条航线的收益之和的 大可能值. 我们将城市看作顶点，航线看作边，构成的图为 . 每条航线的收益为它连结的两个顶点的度之乘积. 设有 个点 , , , 的度不为 , 设 的度为 . 若记 , 则 且 . 对于一点 , 我们下面估计从 出发的所有航线的收益之和．设其它 个点中与 相连的点为 , , , 与 不连的点为 , , . 因为 , 且 , 因此有 ， 即与 连边的所有点的度之和 ，因此从 出发的所有航线的收益之和 . 因此所有航线的收益之和 ． 由于这 个点之间至多连 条边，因此 ，因此 ．故收益之和 ． 构造：任选 座城市，让其中任两个城市之间有双向航线．此时有 条边，每条边的 “收益” 为 ，总收益为 ． 综上， 大值为 . 注 此题为第 届 第 题． 2024年全国高中数学联赛竞赛第6题15分 六、组合问题 6 七、组合问题 7 学而思总部 王正 7 ★★★ 答案 解析 在凸多面体 中，称 的一个面上两条有公共顶点的边构成一个 “角” ( 两条边的公共顶点成为 “角” 的顶点 ). 求证 : 可以将所有 “角” 分为两组，使得对 的每个面 , 位于 上的 “角” 不全在同一组; 且对 的每个顶点 , 以 为顶 点的 “角” 不全在同一组. 见解析 建立空间直角坐标系，使得 轴与 任意两顶点连出的直线均不垂直 ( 由于这些直线过原点的垂面不可能 覆盖整个空间，因此这显然可以做到 ). 对 的每个面，将其 坐标 大 ( 下面简称为 “ 高” ) 的顶点所在角分到第一组，将其 低的顶点所在角 分到第二组．记整个多面体 高和 低的顶点分别为 和 . 则目前为止，有如下事实 : 事实 对于 和 之外的顶点 , 至少有两个以 为顶点的角还未被分组 ( 因为从 出发必有朝上的 边和朝下的边，因此必有两个角是一边朝上一边朝下的，这样的角不可能是平面中 高或 低的角 ) 如果有某个面的顶点同时包含 和 , 将该面中 所在角挪到第二组, 所在角挪到第一组 现在 和 处的角均既有黑色又有白色．对于还未分组的角 , 将其依次分到含 “以 为顶点已分组的角” 较少 的组，由事实 可知这样操作后每个顶点处的角不全在同一组．每个面的角也不全在同一组是显然的． 如果任何面的顶点不同时包含 和 , 则任取一个含 的面，将其中 所在角挪到第二组，其中本来第 二组中的角挪到第一组; 再任取一个含 的面，将其中 所在角挪到第一组，其中本来第一组中的角挪到 第二组．现在 和 处的角均既有黑色又有白色，且依然满足事实 对于还未分组的角 , 将其 依次分到含 “以 为顶点已分组的角” 较少的组，由事实 可知这样操作后每个顶点处的角不全在同一组． 每个面的角也不全在同一组是显然的． 综上，原题结论成立． 注 此题为第 届 第 题. 浙江省诸暨市海亮高级中学 周毅博 8 ★★★ 2024年全国高中数学联赛竞赛第7题15分 2024年全国高中数学联赛竞赛第8题15分 八、组合问题 8 答案 解析 考虑正 棱柱，连接每个侧面的面对角线产生 个交点，并去掉侧棱，现在我们对这 个交点及 个顶点进 行三染色，相邻顶点不能同色，不考虑旋转、翻折情况，求染色方式种数. 考虑正 棱柱，连接每个侧面的面对角线产生 个交点，并去掉侧棱，现在我们对这 个交点及 个顶点 进行三染色，相邻顶点不能同色，绕中轴旋转重合算一种，求染色方式种数. 见解析 记上底面的各顶点为 , , , ,下底面对应的顶点为 , , , , 面 的 对角线交点为 , 所有下角标均在模 下表示，三染色分别用 赋值，同样也是在模 下表示. 下定义 “顺三角形” 为顺时针方向赋值加 ( 模 意义下 ) 的三角形; “逆三角形” 为逆时针方向赋值加 ( 模 意义下 ) 的三角形. 此时，只需确定初始 的赋值，及所有三角形的顺逆情况，即可确定唯一确定的赋值 于是我们只需要研 究 “顺逆三角形” 的情形即可. 首先，我们先通过上底面 , , , , 研究 , 的顺逆情况． 注意到当 , 是顺三角形时, ； 当 , 是逆三角形时, ； 而 , 故设有 个顺三角形, 个逆三角形, 则 当 时, , 上底面共有 . ⅱ 当 时, , 上底面共有 . ⅲ 当 时, , 上底面共有 . 下面，我们再考虑下底面的情形． 情形一：若 , 此时右边 , 顺逆不同, 且可导出 , 则可推 出此时所有上下对应的三角形都是顺逆不同的． 即当上底面顺逆情形确定时，取顺逆不同的下底面与之唯一对应． 情形二：若 , 此时可知 , 则可导出所有 均相同, 此时可知上底面是交替出现的, 对应 的下底面恰好错开一格． 此时要满足条件 , 则 . 即若 时, 当上底面交替的种数会多一种下底面的对应方式, 计算后为 种；若 时， 无多余情形． 故 后答案为： 当 时, , 上底面共有 . 当 时, , 上底面共有 . 当 时, , 上底面共有 . 我们先考虑固定不旋转的情形，此时满足要求的染色图形形成的集合记为 ，有 . 下根据 小旋转重合步数 对所有结果进行分类，注意到转 次后必回，则 ． 情形一：若 ，此时上底面每个顶点染色相同，矛盾． 情形二：若 ，此时上底面 ，则这五个三角形只能为 “ 逆 顺” 或者 “ 顺 逆”，由对 称性，先讨论 “ 逆 顺”，则旋转后的必可以逆开头，若赋 ，则有 � � � � � . 对 赋值有三种，故共有 类. 同理 “ 顺 逆” 也有 类．即 情形，共 类，每类会在 中出现 次； 情形三：若 ，设有 类，每一类旋转 次回，故每类在 中出现 次． 我们对 进行算两次，得 ． 下面，我们再考虑下底面的情形： 情形一：若 , 此时右边 , 顺逆不同, 且可导出 , 则可推 出此时所有上下对应的三角形都是顺逆不同的． 即当上底面顺逆情形确定时，取顺逆不同的下底面与之唯一对应． 情形二：若 , 此时可知 , 则可导出所有 均相同，此时可知上底面是交替出现的，对 应的下底面恰好错开一格． 此时要满足条件 , 则 ． 因为 时, 故无多余情形． 综上共 种. 北京市海淀区教师进修学校附属实验学校 郭城 9 ★★★ 为 , 是 行 列的数阵, 表示 中第 行第 列的数, , , 且 同时满足 : 每行恰有五个 ; 任意两行不相同．记集合 中元素的个数为 . 若对任意 , , 中都恰有 行满足第 列和第 列的数均为 . 求证 : . 2024年全国高中数学联赛竞赛第9题15分 九、组合问题 9 答案 解析 见解析 表中 行, 每行共 个 对, 即 的数对共有 ; 满足 的 共有 组, 由题设, 恰有 行满足 , 共 记 中有 项 为 , 项为 . 满足 的 数对共有 组. 由题设, 恰有 行满足 , 故 同时, . 得到, . 注 命题的推论含 : 此表格行数 至多 . 对于 中的元素 , 满足 的 数对共有 组; 满足 的 数对共有 组. . . 可以根据这些等式构建其他问题．或调整 中为 的项数来更正上界. 命题核心围绕算两次．求证的结论和本题的条件 “若对任意 , 中都恰有 行满足第 列和第 列 的数均为 .” 可以调整至更难或更简单的难度. 成都外国语学校 朱世衡 10 ★★★ 答案 甲乙两人玩如下的游戏 : 对于一个事先取定的正整数 , 甲先选出集合 的 个子集 , , , , 每个子集都含 个元素 接下来, 乙选出 个整数 , , , . 后, 甲选一个整数 . 若存在一个 以及 , 使得 , 则乙获胜; 否则甲获胜 请根据 的 取值讨论谁有必胜策略. 见解析 2024年全国高中数学联赛竞赛第10题15分 十、组合问题 10 解析 下面证明, 当 时, 甲有必胜策略; 当 时, 乙有必胜策略 记 . 当 时, 下面说明甲的必胜策略 : 甲取 个集合为 . 即是 中所有满足 余数在 范围内的所有元素. 然后乙取出 个数 , , , . 对任意 , 我们将 所有元素平移 后构成集合 , 即 . 下面我们归纳证明 , 这样一定有一个元素不在任意 中, 取 即可. 下面仅说明, 当 时, 乙的必胜策略, 这样 乙都必胜． 对于甲选择的 , , , , 记 . 我们将归纳证明乙可以挨个选择 , , , , 使得对于某个 , 我们总可以适当的选择 , 使得对应的 满足 . ( 即 至少可以覆盖 中一半的元素 ). 下面对 进行归纳 : 奠基 : 时, 任取 , 此时 至少可以覆盖 中一半元素, 从而 . 归纳 : 对于 , 已经找到了 , , , , 使得对应的 ; 满足 下面考虑如何找 . 注意到当让 , 取遍 , 则 将 中每个元素覆盖了 次, 所以对 中的元素共计覆盖了 次. 这样必存在一个 , 至少覆盖 中 个元素． 选择这个 , 这样 . 归纳完毕． 这样乙可以换个选择 , , , 之后, , 这意味着 , 从而甲任选一 个整数 , 都存在一个 以及 , 使得 , 这样乙必胜． 证毕． 十一、组合问题 11 浙江温州育英国际实验学校 陈华毅 11 ★★★ 答案 解析 在 的方格表上, 随机放置一颗白子与黑子在不同的格内 现有甲、乙两人, 甲先移动白子, 乙再移动黑子, 交替 进行, 且满足下述规则 : 移动只可在横向或纵向改变一格, 同一颗棋子横向与纵向移动必须交替进行 若乙移动后, 恰使 黑子与白子落在同一格内, 乙获胜; 否则, 甲获胜 问 : 乙有必胜策略的概率 ? 记两颗棋子横向与纵向的距离为 , 总距离 , 其中 , . 当 为奇数时, 对方格表进行黑白染色, 每个格子仅与异色的格子相邻 ( 上、下、左、右四个格子 ), 此 时白子和黑子分别在异色的格子内, 进行若干次移动后, 仍在异色格子内, 不可能落在同一格. 当 为偶数时, 此时 , 对 , 的奇偶性进行讨论. , 均为偶数, 此时乙第一次移动方向在横纵向选择中与甲保持一致 ( 即甲第一次横向移动, 乙也横向移 动, 甲第一次纵向移动, 乙也纵向移动 ). 乙可进行操作使每一次甲、乙行动完后, , 不增 由于方格表大小 有限, 白子不可能一直往黑子反方向移动, 甲总会在某次移动后, 使 , 其中之一减少 , 此时乙可移动黑子 向白子靠近, 此时 , 少其中之一共减少 . 不断操作, 直至 , 其中之一为 , 不妨 为 . 每次 改变时, 乙总能保证移动后 仍为 , 则同理不断操 作能使 为 . 此时乙有必胜策略. , 均为奇数, 此时乙第一次移动方向在横纵向选择中与甲不同 ( 即甲第一次横向移动, 乙纵向移动, 甲 第一次纵向移动, 乙横向移动 ). 将甲、乙各操作两次称为一轮, 乙可通过操作, 使每轮操作后 不增 由于方 格表大小有限, 总会在若干轮后, 使 减少, 而每轮操作后 , 的奇偶性均不变, 必会出现 , 其中之一为 , 不妨 为 . 此时每轮操作乙可保证 恒为 ( 乙先在 方向上改变, 则先令 ), 则只用考虑 方 向 而每轮操作 不增且总存在某些轮使 减少, 由于奇偶性不变, 直至 . 此时 , 再考虑甲一开始移动的方向, 不妨为 方向, 若甲移动使 , 则乙再移动 方向, 此时 黑白子已在同一格 每轮一开始, 甲只能在 方向上, 远离黑子运动, 乙可对应移动使每轮结束 . 而方格表大小有限, 总会在某轮后, 甲不能在 方向上, 远离黑子运动, 此时 , 则此轮中黑白子可落入 同一格. 故当 为偶数时, 乙有必胜策略, 当 为奇数时, 乙无必胜策略. 乙有必胜策略的概率 . 2024年全国高中数学联赛竞赛第11题15分 北京明诚外国语学校 于睿元 12 ★★★ 答案 解析 我们称一个数列是 “好的” , 如果这个数列首项是 , 且该数列从第二项开始, 每一项都可以被表示为数列前某些项的 和．记 为长为的这样的数列的个数，是否存在正整数 , 使得存在正整数 , 对于任意正整数 , 均有 ? 不存在 若不然, 存在 满足对于 , 均有 . 令 为长为 的且前 项依次为 的好数列的个数． 显然, , 对任意 成立 根据定义, . 接下来我们说明, 对于任意 , . 实际上, 对于每一个长为 的且前 项依次为 的好数列, 不妨设其每一项依次为 , , , . 则由假设知, 以下 项两两不同 : ; ; . 所以对于每一个长为 的好数列, 以其为前 项的长为 的好数列至少有个 个, 所以对于 任意 , . 所以 , 其中 . 取 使得 , 则 矛盾 ! 综上所述, 上述 不存在． 注 在尝试估计下一项的大小时, 发现好数列的下一位至少可以是前若干项的前缀和, 但我们需要精细化这些 前缀和, 以找到一个更好的估计. 内蒙古通辽实验中学 包永胜 2024年全国高中数学联赛竞赛第12题15分 十二、组合问题 12 十三、组合问题 13 13 ★★★ 答案 解析 牧民苏和家中共有 匹马, 为那达慕赛马将把马匹分成了 个参赛组, 每个参赛组有 匹马．证明, 可以找到两 个参赛组, 两者中至少有 个共同马匹. 见解析 将 马匹编号为 至 号, 以 记 号马匹所参加的参赛组数目, 则有 . 任意选取两个参赛组 选法当然有 种 引入示性函数 如果 号马匹是这两个参赛组的公共马匹; 否则. 易知 . 于是 就是这两个参赛组的共同成员的人数, 这是一个随机变量 为了完成题目的解答, 我们来计算 的数学期望, 即平 均值 由组合数的凸性, 易知 所以存在两个参赛组, 他们中的公共马匹数不少于 匹. 北京师范大学附属实验中学 舒惠泽 14 ★★★ 答案 解析 请问是否可以将一个 元集合的所有 元子集每三个分为一组, 使得每组的三个子集的并集是全集 ? 可以 下面直接给出构造． 2024年全国高中数学联赛竞赛第13题15分 2024年全国高中数学联赛竞赛第14题15分 十四、组合问题 14 注 正在研究 元集合的所有 元子集情况, 感觉难度挺大, 在此抛砖引玉一下. 湖南师大附中 陈天择 15 ★★★ 答案 解析 证明 : 存在正整数 , 对任意的正整数 , 存在正整数的集合 , 恰有 个子集元素和为 . 见解析 对 充分大, 设正整数 使 , 则 , 并记 , 取集合 为 大为 的连续 个正整数构成的集合; 集合 为 的 大的连续 个正整数构成的集合, 为 的全体 构成的集合．取 . 下证 : 对 子集 , 满足 的元素和为 , 则要么 恰包含 中某一个元素, 要么 恰包含 中某两个 元素; 且已知包含 中某一个元素, 或包含 中某两个元素时, 元素和为 的 的子集恰有一个．如已证, 则满足条件的子集个数恰为 个. 证 : 取 充分大使 ; ; 则 均存在且无重复元素. 2024年全国高中数学联赛竞赛第15题15分 十五、组合问题 15 取 充分大使 , 则 中 小的两个元素之和大于 , 则 至多包含 中一个元素. 如 包含 中某一个元素, 此时其余元素之和 , 则 不包含 中元素, 且由 进制结论知 的自然数均存在唯一的 的子集的元素之和表示, 即恰有一个. 如 不包含 中元素, 取 充分大使 ; . 注意到 全体元素 与 大元素之和 , 说明 不能只包含 或 个 中元素; 中三个 小元素和 ; 说明 不能包含 个以上的 中元素．则 恰包含 中某两个元素; 此时其余 元素之和 ; 由 进制结论知 的自然数均存在唯一的 的子集的元素之和表示, 即恰有一个. 计算知 即可满足全部充分大条件, 即 成立. 综上，证毕. 注 实际上 时, ; , , 已满足条件. 湖南师大附中 隆希辰 16 ★★★ 答案 解析 在 的棋盘中, 每个单位方格均填上数字 , 每次操作取有公共边的两个单位方格, 将其中的数 同时加 . 能否通过 次操作, 使得各行、各列数之和均为同一个值 ? 如果可以, 求 的 小值. 可以．当 为偶数时, 小值为 , 当 为奇数时, 小值为 . 为偶时, 构造如下 : 时, 行的两格同时加 , 行的两格同时加 即可; , 时, 次操作后行和列和均为 . 时, 前 行 列经过 次操作后行和列和均为 ; 第 行, 、 列同时加 ; 第 行, 、 列同时加 共 次操作后行和列和均为 . 的证明如下 : 至少有一次操作, 一次操作至少让行和或者列和加 , 故行和列和至少为 . 方格表中数 字和至少为 , 一次操作使方格表中数字和加 , 故 . 为奇数时, 构造如下 : 时, 构造如右图, 每条线段表示一次操作, 一次操作线段端点所在两个方格各加 . , 时, 次操作后行和列和均为 ; 2024年全国高中数学联赛竞赛第16题15分 十六、组合问题 16 时, 前 行 列经过 次操作后行和列和均 为 , 第 行, 、 列同时加 两次 第 行, 、 列同时加 两次 共 次操作后行和列和均为 . 的证明如下 : 首先, 设行和为 , 则 方格表中总数和 , 故 为偶数 注意到, 若 一次操作同行的两个方格各加一, 那么每行的和的奇偶性不变 设 为第 行行 和, 为使第 行与第 行中方格同时加一的操作次数 , , . 故 . 于是 , 即同时改变两行的操作次数为偶数次. 同理可得, 同时改变两列的操作次数也是偶数次, 故 . 于是 , 即 , 故 . . 2024 第13届数学竞赛命题研讨资料（组合部分）（解析） 一、组合问题 1 湖南省长沙市第一中学 韩序舜 1、【来源】 2024年全国高中数学联赛竞赛第1题15分 对于正整数 , 有 个集合，满足 : 每个集合有 个元素; 任意两个集合恰有一个公共元素; 所有 个集合交集为空集. 求 的最大值. 二、组合问题 2 江西科技学院附属中学 张敬德 2、【来源】 2024年全国高中数学联赛竞赛第2题15分 某次研讨会共有 人参与，每人至少认识其中 人，试求 的最小值，使得其中必存在彼此认识的 人. 三、组合问题 3 北京大学附属中学 陈宣桦 3、【来源】 2024年全国高中数学联赛竞赛第3题15分 在单位正方形内部放置 个不同的点，证明 : 一定可以选取其中 个点顺次用线段连接，使得这 条线段的长度之和不超过 ; 同时，对于正整数 , 一定可以选取其中 个点顺次用线段连接，使得这 条线段的长度之和不超过 . 四、组合问题 4 学而思广州分校 余泽伟 4、【来源】 2024年全国高中数学联赛竞赛第4题15分 对 , , , , 为大于 的正整数, , 为 个储存位置，把 填入这 个储存位置中，每个位置恰填一个数. 定义一次操作 : 选取一个 , 把 根据除第 个维度以外坐标相同分组，共 组，把每组的 个数按第 个维度坐标升序重新排列填回 中. 对于不能再有变化的状态称为稳定状态. 求最小的 , 使对任意的初始状态，都可用不超过 次操作变为稳定 五、组合问题 5 江西师大附中 陈思洲 5、【来源】 2024年全国高中数学联赛竞赛第5题15分 城市之间有 个不同的航线，每条航线的起点、终点为 城市且均为双向航线．每两条航线除 城市外还恰有一个公共站点，任意三条航线间无公共站点．小数同学想要完成这样的挑战 : 从 城市乘航班出发，每到某两个航线的公共站点，就立即换乘与原航班方向相反的航班 ( 如原先采坐的是 的航班，则立即换乘 方向的航班 ), 挑战乘一定次数后到达 城市．请问 : 对什么样的 , 小数可以保证完成挑战 ? 六、组合问题 6 学而思总部 王正 6、【来源】 2024年全国高中数学联赛竞赛第6题15分 已知 星球上有一亿座城市，初始时城市之间没有任何航线，现有一个航空公司准备建立 条双向航线，每条航线连接两个不同城市，且无两条航线连接相同的两个城市 每座城市的 “繁荣度” 定义为从该城市出发的航线数目．每条航线的 “收益” 为它所连接的两个城市的繁荣度之乘积. 求这 条航线的收益之和的最大可能值. 七、组合问题 7 学而思总部 王正 7、【来源】 2024年全国高中数学联赛竞赛第7题15分 在凸多面体 中，称 的一个面上两条有公共顶点的边构成一个 “角” ( 两条边的公共顶点成为 “角” 的顶点 ). 求证 : 可以将所有 “角” 分为两组，使得对 的每个面 , 位于 上的 “角” 不全在同一组; 且对 的每个顶点 , 以 为顶点的 “角” 不全在同一组. 八、组合问题 8 浙江省诸暨市海亮高级中学 周毅博 8、【来源】 2024年全国高中数学联赛竞赛第8题15分 考虑正 棱柱，连接每个侧面的面对角线产生 个交点，并去掉侧棱，现在我们对这 个交点及 个顶点进行三染色，相邻顶点不能同色，不考虑旋转、翻折情况，求染色方式种数. 考虑正 棱柱，连接每个侧面的面对角线产生 个交点，并去掉侧棱，现在我们对这 个交点及 个顶点进行三染色，相邻顶点不能同色，绕中轴旋转重合算一种，求染色方式种数. 九、组合问题 9 北京市海淀区教师进修学校附属实验学校 郭城 9、【来源】 2024年全国高中数学联赛竞赛第9题15分 为 , 是 行 列的数阵, 表示 中第 行第 列的数, , , 且 同时满足 : 每行恰有五个 ; 任意两行不相同．记集合 中元素的个数为 . 若对任意 , , 中都恰有 行满足第 列和第 列的数均为 . 求证 : . 一十、组合问题 10 成都外国语学校 朱世衡 10、【来源】 2024年全国高中数学联赛竞赛第10题15分 甲乙两人玩如下的游戏 : 对于一个事先取定的正整数 , 甲先选出集合 的 个子集 , , , , 每个子集都含 个元素 接下来, 乙选出 个整数 , , , . 最后, 甲选一个整数 . 若存在一个 以及 , 使得 , 则乙获胜; 否则甲获胜 请根据 的取值讨论谁有必胜策略. 一十一、组合问题 11 浙江温州育英国际实验学校 陈华毅 11、【来源】 2024年全国高中数学联赛竞赛第11题15分 在 的方格表上, 随机放置一颗白子与黑子在不同的格内 现有甲、乙两人, 甲先移动白子, 乙再移动黑子, 交替进行, 且满足下述规则 : 移动只可在横向或纵向改变一格, 同一颗棋子横向与纵向移动必须交替进行 若乙移动后, 恰使黑子与白子落在同一格内, 乙获胜; 否则, 甲获胜 问 : 乙有必胜策略的概率 ? 一十二、组合问题 12 北京明诚外国语学校 于睿元 12、【来源】 2024年全国高中数学联赛竞赛第12题15分 我们称一个数列是 “好的” , 如果这个数列首项是 , 且该数列从第二项开始, 每一项都可以被表示为数列前某些项的和．记 为长为的这样的数列的个数，是否存在正整数 , 使得存在正整数 , 对于任意正整数 , 均有 ? 一十三、组合问题 13 内蒙古通辽实验中学 包永胜 13、【来源】 2024年全国高中数学联赛竞赛第13题15分 牧民苏和家中共有 匹马, 为那达慕赛马将把马匹分成了 个参赛组, 每个参赛组有 匹马．证明, 可以找到两个参赛组, 两者中至少有 个共同马匹. 一十四、组合问题 14 北京师范大学附属实验中学 舒惠泽 14、【来源】 2024年全国高中数学联赛竞赛第14题15分 请问是否可以将一个 元集合的所有 元子集每三个分为一组, 使得每组的三个子集的并集是全集 ? 一十五、组合问题 15 湖南师大附中 陈天择 15、【来源】 2024年全国高中数学联赛竞赛第15题15分 证明 : 存在正整数 , 对任意的正整数 , 存在正整数的集合 , 恰有 个子集元素和为 . 一十六、组合问题 16 湖南师大附中 隆希辰 16、【来源】 2024年全国高中数学联赛竞赛第16题15分 在 的棋盘中, 每个单位方格均填上数字 , 每次操作取有公共边的两个单位方格, 将其中的数同时加 . 能否通过 次操作, 使得各行、各列数之和均为同一个值 ? 如果可以, 求 的最小值. 1 、【答案】 ; 【解析】 由题意，在这 个集合中，存在一个被共用的元素不止一个的集合．( 否则，每一个集合和其他集合共用同一个元素，会导致所有集合共用同一个元素 ) 设该集合为 , 其中的元素为 . 不妨设元素 , 被其他集合共用，设包含元素 的集合有 个，分别为 , , , , 包含元素 的集合有 个，分别为 , , , . 考虑对于满足 , 的正整数 , , , 我们有 : 因为，若 ，则会导致 和 的公共元素至少有 和 ，与题目条件矛盾． 于是 与 , , , 之间两两的公共元素互不相同，而 中的元素中，能与 , , , 共用的只有 个，（ 不能共用）故 . 同理可知， 中，每个元素至多属于 之外的 个集合，于是集合的总个数 至多为 个． 另一方面，我们给出下列构造满足条件 : 取 ； 在平面直角坐标系上取点集 , 取 , , ； 对 , ，集合 包含以下 个元素 : 第一个为 ，第 个元素 为如下产生的点：过点 作斜率为 的直线，与直线 产生交点 ，再将横坐标 在模 的意义下变为 到 之间的数．如集合 . 容易验证，上述 个集合满足条件，所以 的最大值为 . 注：该题目为对下述题目的引申思考 : 设有 个集合，每个集合有 个元素，任意两个集合的并集有 个元素，问此 个集合的并集有多少个元素 ? 另外，本题的构造和 定理有某些共通之处，其内容为：平面上不共线的 个点两两相连，至少会得到 条直线，等号成立当且仅当这些线构成一个射影平面，或者构成一个拟束．本题构造中的 类似于射影平面中的无穷远直线的情形，而问题 中的结构类似于拟束的情形． 2 、【答案】 ; 【解析】 设这 人的集合为 , 所认识的人的集合记为 , , 则 , 若 , 是 中认识的 人，则 . 当 , 不妨设 , 即 , , 彼此认识, 则 . 当 , 不妨设 , 即 , , , 彼此认识, 则 . 依此类推，可得 , , , 彼此认识, 则 ． 当 ，不妨设 ，即 , , , 彼此认识． 由 ，得 , 即 . 下面再说明 是最小的．否则，若 ，我们将 个人均分成 , , , 这 组，每组 人．令同组的人互不相识，不同组的人均彼此认识，则 中任一人所认识的人数均为 . 现在我们从 中任取 人，则必有 人来自同一组，他们互不相识，这与题设“必存在彼此认识的 人”矛盾． 综上所述， 的最小值为 . 3 、【答案】 见解析; 【解析】 证明：引理一 : 在 的矩形中放置不超过 个点，一定可以顺次连接它们，使得总长度不超过 . 不妨设矩形顶点为 , 不妨补成 个点，总长度不减，设所有点的坐标为 . 按照横坐标从小到大 个一组，将所有点均分为 份，则可划分 个 矩形使得每组的 个点都在一个矩形的内部或边上，且 . 首先将每个矩形中的点按纵坐标从小到大进行连接，形成 个组. 然后如下图所示，可以有两种方式构建组间连接线段，使得整体是一个折线. 考虑将所有线段的长度放大为其横纵投影之和来估计线段组的总长度. 从纵投影看，两种方案皆至多占 个 ; 除了组间连接线段之外，第 组的线段的横投影不超过 , 合计不超过 . 因此上述两种连接方式线段总长都不超过 ( 是此方式组间连接线段的水平投影长度之和). 注意到两种连接方式的组间连接线段的水平投影长度之和不超过 , 因此至少有一种连接方式的总长不超过 . 引理二 : 在边长为 的正方形中有 个点，则可以选取 个点顺次连接总长不超过 , 若将 个点的横坐标从小到大排列，则纵坐标构成一个长为 的序列; 则或者存在一个长为 的不增子列，或者存在一个长为 的不减子列 ( 定理 ) 表示在点列中，则或者存在一个长为 的向右上 ( 含向右或向上 ) 的子列，或者存在一个长为 的向右下 ( 含向右或向下 ) 的子列，考虑将其顺次连接总长放缩为投影长度，则恰为首尾两点的横坐标之差加上纵坐标之差. 现在将边长为 的正方形旋转 后进行点的选取，如图所示，可注意到任两点的横纵坐标差之和不会超过 . 利用引理二选取 个点，由抽屉原理得前 个点和后 个点中必有一组总长不超过 . 对于第二小问，将正方形如图分割为中心对称的“井字形”,不妨设其中中心正方形的边长为 , 则 区域的边长为 , 若其中有至少 个点，则由引理二存在 个点顺次连接总长不超过 . 若不存在，则同理有 , , . 相加减去总和得 : . 可不妨设 中至少有 个点 因此由引理一，可以全部连接这些点使得总长不会超过 , 而共有 条线段，至少可以依次分成 组 个线段. 令其中至少有一组不大于 , 取 , 则存在 个点顺次连接总长不超过 . 注   注意到放置更多的点只会使结果更优，在北京市邀请赛中选择了 个点, 此时 . 取 , 则可以得到 , 在原题中仅要求总长小于 . 本题是对旅行商 问题的一个小方面的探索. 4 、【答案】 ; 【解析】 先证 . 在 中填入 ，有定义知每个数在一次操作中只能改变一个维度的坐标，而稳定状态 应在 中，所以 . 再证 时必能变为稳定状态，具体操作为依次选择 即可. 定义 : 一种状态下操作 均无变化，称这种状态为 “ 稳定”. 下面归纳证明依次操作 后为 “ 稳定”. 当 时，成立. 当 成立时，对 反证，若 “ 稳定” 状态 下，再操作 后状态 不为 " 稳定”, 则由定义知 不为 “ 稳定”. , 的 中为 , 中为 , 其中 , , 均为坐标的第 个维度. 记 的 中为 , 中为 , 均为坐标的第 个维度，其中 , , 因操作 后状态为 , 则两个数列单调递增，任意重排两个数列，仍存在 , 而操作前状态为 , 的 中为 , 中为 , 与 为 “ 稳定” 矛盾．即 成立. 综上所述, 的最小值为 . 5 、【答案】 对所有奇数 成立．; 【解析】 对所有奇数 成立．为便于叙述，将两城市 和所有公共站点称为 “点位”, 设 条航线分别为 , , , . 一方面 : 当 为偶数时，构造一种航线安排使其无法完成挑战 : 取 与 其中 , . 满足它们两条航线的公共站点在 航线上比 与 的公共站点更接近 城市; 在 航线上比 与 的公共站点更接近 城市． 此时，对于配对的两航线 与 , 小数无论从这两条中的哪条航线离开 , 在到达 与 的公共站点后, 必然会沿原航线 或 返回到 城, 故无法完成挑战. 另一方面，当 为奇数时，小数的策略是 “每到一个公共站点，立马换另一条航线继续出发，直到到达 或 停止” 小数在选取了该策略后，选择某个航线出发，则有以下事实 : 小数在有限次搭乘后一定会停止，即回到 城或到达 城 设 条航线间的 个公共站点分别为 , , , . 并记 城为 , 城为 . 假设小数从 城出发后不再回到 城或 城，设他经过的点位为 . 由于点位只有有限多个，故存在 , 使得 , 在 中出现一次以上．此时取最小的 , 使得存在 , 满足 且 . 若 , 则 为 即 , 故 表示 城，矛盾; 若 , 设 , , 则 与 均在 中出现．设 出现在航线 上，则 与 均在以航线 有公共站点 的另一条航线上，且均与 的方向相反．于是 与 在同一天航线上且方向相同则 , 这与 的最小性矛盾. 小数从 城选择相同的航线出发，结果是一样的 若小数从 城乘航线 出发后，依次经过点位 , , , 后通过航线 回到 城．则对称地有 : 若小数从 城沿着航线 出发，也将依次通过点 , , , , 并通过航线 回到 城． 回到原问题，假设小数无法到达 城 则对 , 存在 , 使小数通过航线 出发以后必可以通过航线 回到 城．由 得, . 此时将 与 配对，由于 为奇数，故存在 使得 . 设从 城沿航线 出发后依次经过点位 , , , 后沿航线 回到 城．则由 和 得到 , , , 与 , , , 是相同的，故 与 相同. 若 为偶数，则令 , 则 与 相同，矛盾． 若 为奇数，则令 , 则 与 相同，故从 到 的航线与 到 的航线相同，这与小数需要在公共站点换乘矛盾．于是小数不能回到 城，故当 为奇数时，小数必然能够到达 城. 6 、【答案】 ; 【解析】 我们将城市看作顶点，航线看作边，构成的图为 . 每条航线的收益为它连结的两个顶点的度之乘积. 设有 个点 , , , 的度不为 , 设 的度为 . 若记 , 则 且 . 对于一点 , 我们下面估计从 出发的所有航线的收益之和．设其它 个点中与 相连的点为 , , , 与   不连的点为 , , . 因为 , 且 , 因此有 ， 即与 连边的所有点的度之和 ，因此从 出发的所有航线的收益之和 . 因此所有航线的收益之和 ． 由于这 个点之间至多连 条边，因此 ，因此 ．故收益之和 ． 构造：任选 座城市，让其中任两个城市之间有双向航线．此时有 条边，每条边的 “收益” 为 ，总收益为 ． 综上，最大值为 . 注：此题为第 届 第 题． 7 、【答案】 见解析; 【解析】 建立空间直角坐标系，使得 轴与 任意两顶点连出的直线均不垂直 ( 由于这些直线过原点的垂面不可能覆盖整个空间，因此这显然可以做到 ). 对 的每个面，将其 坐标最大 ( 下面简称为 “最高” ) 的顶点所在角分到第一组，将其最低的顶点所在角分到第二组．记整个多面体最高和最低的顶点分别为 和 . 则目前为止，有如下事实 : 事实 对于 和 之外的顶点 , 至少有两个以 为顶点的角还未被分组 ( 因为从 出发必有朝上的边和朝下的边，因此必有两个角是一边朝上一边朝下的，这样的角不可能是平面中最高或最低的角 ) 如果有某个面的顶点同时包含 和 , 将该面中 所在角挪到第二组, 所在角挪到第一组 现在 和 处的角均既有黑色又有白色．对于还未分组的角 , 将其依次分到含 “以 为顶点已分组的角” 较少的组，由事实 可知这样操作后每个顶点处的角不全在同一组．每个面的角也不全在同一组是显然的． 如果任何面的顶点不同时包含 和 , 则任取一个含 的面，将其中 所在角挪到第二组，其中本来第二组中的角挪到第一组; 再任取一个含 的面，将其中 所在角挪到第一组，其中本来第一组中的角挪到第二组．现在 和 处的角均既有黑色又有白色，且依然满足事实 对于还未分组的角 , 将其依次分到含 “以 为顶点已分组的角” 较少的组，由事实 可知这样操作后每个顶点处的角不全在同一组．每个面的角也不全在同一组是显然的． 综上，原题结论成立． 注:此题为第 届 第 题. 8 、【答案】 见解析 ; 【解析】 记上底面的各顶点为 , , , ,下底面对应的顶点为 , , , , 面 的对角线交点为 , 所有下角标均在模 下表示，三染色分别用 赋值，同样也是在模 下表示. 下定义 “顺三角形” 为顺时针方向赋值加 ( 模 意义下 ) 的三角形; “逆三角形” 为逆时针方向赋值加 ( 模 意义下 ) 的三角形. 此时，只需确定初始 的赋值，及所有三角形的顺逆情况，即可确定唯一确定的赋值 于是我们只需要研究 “顺逆三角形” 的情形即可. 首先，我们先通过上底面 , , , , 研究 , 的顺逆情况． 注意到当 , 是顺三角形时, ； 当 , 是逆三角形时, ； 而 , 故设有 个顺三角形, 个逆三角形, 则 当 时, , 上底面共有 . 当 时, , 上底面共有 . 当 时, , 上底面共有 . 下面，我们再考虑下底面的情形． 情形一：若 , 此时右边 , 顺逆不同, 且可导出 , 则可推出此时所有上下对应的三角形都是顺逆不同的． 即当上底面顺逆情形确定时，取顺逆不同的下底面与之唯一对应． 情形二：若 , 此时可知 , 则可导出所有 均相同, 此时可知上底面是交替出现的, 对应的下底面恰好错开一格． 此时要满足条件 , 则 . 即若 时, 当上底面交替的种数会多一种下底面的对应方式, 计算后为 种；若 时，无多余情形． 故最后答案为： 当 时, , 上底面共有 . 当 时, , 上底面共有 . 当 时, , 上底面共有 . 我们先考虑固定不旋转的情形，此时满足要求的染色图形形成的集合记为 ，有 . 下根据最小旋转重合步数 对所有结果进行分类，注意到转 次后必回，则 ． 情形一：若 ，此时上底面每个顶点染色相同，矛盾． 情形二：若 ，此时上底面 ，则这五个三角形只能为 “ 逆 顺” 或者 “ 顺 逆”，由对称性，先讨论 “ 逆 顺”，则旋转后的必可以逆开头，若赋 ，则有           . 对 赋值有三种，故共有 类. 同理 “ 顺 逆” 也有 类．即 情形，共 类，每类会在 中出现 次； 情形三：若 ，设有 类，每一类旋转 次回，故每类在 中出现 次． 我们对 进行算两次，得 ． 下面，我们再考虑下底面的情形： 情形一：若 , 此时右边 , 顺逆不同, 且可导出 , 则可推出此时所有上下对应的三角形都是顺逆不同的． 即当上底面顺逆情形确定时，取顺逆不同的下底面与之唯一对应． 情形二：若 , 此时可知 , 则可导出所有 均相同，此时可知上底面是交替出现的，对应的下底面恰好错开一格． 此时要满足条件 , 则 ． 因为 时, 故无多余情形． 综上共 种. 9 、【答案】 见解析; 【解析】 表中 行, 每行共 个 对, 即 的数对共有 ; 满足 的 共有 组, 由题设, 恰有 行满足 , 共 记 中有 项 为 , 项为 . 满足 的 数对共有 组. 由题设, 恰有 行满足 , 故 同时, . 得到, . 注   命题的推论含 : 此表格行数 至多 . 对于 中的元素 , 满足 的 数对共有 组; 满足 的 数对共有 组. . . 可以根据这些等式构建其他问题．或调整 中为 的项数来更正上界. 命题核心围绕算两次．求证的结论和本题的条件 “若对任意 , 中都恰有 行满足第 列和第 列的数均为 .” 可以调整至更难或更简单的难度. 10 、【答案】 见解析; 【解析】 下面证明, 当 时, 甲有必胜策略; 当 时, 乙有必胜策略 记 . 当 时, 下面说明甲的必胜策略 : 甲取 个集合为 . 即是 中所有满足 余数在 范围内的所有元素. 然后乙取出 个数 , , , . 对任意 , 我们将 所有元素平移 后构成集合 , 即 . 下面我们归纳证明 , 这样一定有一个元素不在任意 中, 取 即可. 下面仅说明, 当 时, 乙的必胜策略, 这样 乙都必胜． 对于甲选择的 , , , , 记 . 我们将归纳证明乙可以挨个选择 , , , , 使得对于某个 , 我们总可以适当的选择 , 使得对应的 满足 . ( 即 至少可以覆盖 中一半的元素 ). 下面对 进行归纳 : 奠基 : 时, 任取 , 此时 至少可以覆盖 中一半元素, 从而 . 归纳 : 对于 , 已经找到了 , , , , 使得对应的 ; 满足 下面考虑如何找 . 注意到当让 , 取遍 , 则 将 中每个元素覆盖了 次, 所以对 中的元素共计覆盖了 次. 这样必存在一个 , 至少覆盖 中 个元素． 选择这个 , 这样 . 归纳完毕． 这样乙可以换个选择 , , , 之后, , 这意味着 , 从而甲任选一个整数 , 都存在一个 以及 , 使得 , 这样乙必胜． 证毕． 11 、【答案】 ; 【解析】 记两颗棋子横向与纵向的距离为 , 总距离 , 其中 , . 当 为奇数时, 对方格表进行黑白染色, 每个格子仅与异色的格子相邻 ( 上、下、左、右四个格子 ), 此时白子和黑子分别在异色的格子内, 进行若干次移动后, 仍在异色格子内, 不可能落在同一格. 当 为偶数时, 此时 , 对 , 的奇偶性进行讨论. , 均为偶数, 此时乙第一次移动方向在横纵向选择中与甲保持一致 ( 即甲第一次横向移动, 乙也横向移动, 甲第一次纵向移动, 乙也纵向移动 ). 乙可进行操作使每一次甲、乙行动完后, , 不增 由于方格表大小有限, 白子不可能一直往黑子反方向移动, 甲总会在某次移动后, 使 , 其中之一减少 , 此时乙可移动黑子向白子靠近, 此时 , 少其中之一共减少 . 不断操作, 直至 , 其中之一为 , 不妨 为 . 每次 改变时, 乙总能保证移动后 仍为 , 则同理不断操作能使 为 . 此时乙有必胜策略. , 均为奇数, 此时乙第一次移动方向在横纵向选择中与甲不同 ( 即甲第一次横向移动, 乙纵向移动, 甲第一次纵向移动, 乙横向移动 ). 将甲、乙各操作两次称为一轮, 乙可通过操作, 使每轮操作后 不增 由于方格表大小有限, 总会在若干轮后, 使 减少, 而每轮操作后 , 的奇偶性均不变, 必会出现 , 其中之一为 , 不妨 为 . 此时每轮操作乙可保证 恒为 ( 乙先在 方向上改变, 则先令 ), 则只用考虑 方向 而每轮操作 不增且总存在某些轮使 减少, 由于奇偶性不变, 直至 . 此时 , 再考虑甲一开始移动的方向, 不妨为 方向, 若甲移动使 , 则乙再移动 方向, 此时黑白子已在同一格 每轮一开始, 甲只能在 方向上, 远离黑子运动, 乙可对应移动使每轮结束 . 而方格表大小有限, 总会在某轮后, 甲不能在 方向上, 远离黑子运动, 此时 , 则此轮中黑白子可落入同一格. 故当 为偶数时, 乙有必胜策略, 当 为奇数时, 乙无必胜策略. 乙有必胜策略的概率 . 12 、【答案】 不存在; 【解析】 若不然, 存在 满足对于 , 均有 . 令 为长为 的且前 项依次为 的好数列的个数． 显然, , 对任意 成立 根据定义, . 接下来我们说明, 对于任意 , . 实际上, 对于每一个长为 的且前 项依次为 的好数列, 不妨设其每一项依次为 , , , . 则由假设知, 以下 项两两不同 : ;  ;  . 所以对于每一个长为 的好数列, 以其为前 项的长为 的好数列至少有个 个, 所以对于任意 , . 所以 , 其中 . 取 使得 , 则 矛盾 ! 综上所述, 上述 不存在． 注:在尝试估计下一项的大小时, 发现好数列的下一位至少可以是前若干项的前缀和, 但我们需要精细化这些前缀和, 以找到一个更好的估计. 13 、【答案】 见解析; 【解析】 将 马匹编号为 至 号, 以 记 号马匹所参加的参赛组数目, 则有 . 任意选取两个参赛组 选法当然有 种 引入示性函数 如果 号马匹是这两个参赛组的公共马匹; 否则. 易知 . 于是 就是这两个参赛组的共同成员的人数, 这是一个随机变量 为了完成题目的解答, 我们来计算 的数学期望, 即平均值 由组合数的凸性, 易知 所以存在两个参赛组, 他们中的公共马匹数不少于 匹. 14 、【答案】 可以; 【解析】 下面直接给出构造． 注  正在研究 元集合的所有 元子集情况, 感觉难度挺大, 在此抛砖引玉一下. 15 、【答案】 见解析; 【解析】 对 充分大, 设正整数 使 , 则 , 并记 , 取集合 为最大为 的连续 个正整数构成的集合; 集合 为 的最大的连续 个正整数构成的集合, 为 的全体 构成的集合．取 . 下证 : 对 子集 , 满足 的元素和为 , 则要么 恰包含 中某一个元素, 要么 恰包含 中某两个元素; 且已知包含 中某一个元素, 或包含 中某两个元素时, 元素和为 的 的子集恰有一个．如已证, 则满足条件的子集个数恰为 个. 证 : 取 充分大使 ; ; 则 均存在且无重复元素. 取 充分大使 , 则 中最小的两个元素之和大于 , 则 至多包含 中一个元素. 如 包含 中某一个元素, 此时其余元素之和 , 则 不包含 中元素, 且由 进制结论知 的自然数均存在唯一的 的子集的元素之和表示, 即恰有一个. 如 不包含 中元素, 取 充分大使 ; . 注意到 全体元素与 最大元素之和 , 说明 不能只包含 或 个 中元素; 中三个最小元素和 ; 说明 不能包含 个以上的 中元素．则 恰包含 中某两个元素; 此时其余元素之和 ; 由 进制结论知 的自然数均存在唯一的 的子集的元素之和表示, 即恰有一个. 计算知 即可满足全部充分大条件, 即 成立.综上，证毕. 注：实际上 时, ; , , 已满足条件. 16 、【答案】 可以．当 为偶数时, 最小值为 , 当 为奇数时, 最小值为 .; 【解析】 为偶时, 构造如下 : 时, 行的两格同时加 , 行的两格同时加 即可; , 时, 次操作后行和列和均为 . 时, 前 行 列经过 次操作后行和列和均为 ; 第 行, 、 列同时加 ; 第 行, 、 列同时加 共 次操作后行和列和均为 . 的证明如下 : 至少有一次操作, 一次操作至少让行和或者列和加 , 故行和列和至少为 . 方格表中数字和至少为 , 一次操作使方格表中数字和加 , 故 . 为奇数时, 构造如下 : 时, 构造如右图, 每条线段表示一次操作, 一次操作线段端点所在两个方格各加 . , 时, 次操作后行和列和均为 ; 时, 前 行 列经过 次操作后行和列和均为 , 第 行, 、 列同时加 两次 第 行, 、 列同时加 两次 共 次操作后行和列和均为 . 的证明如下 : 首先, 设行和为 , 则 方格表中总数和 , 故 为偶数 注意到, 若一次操作同行的两个方格各加一, 那么每行的和的奇偶性不变 设 为第 行行和, 为使第 行与第 行中方格同时加一的操作次数 , , . 故 . 于是 , 即同时改变两行的操作次数为偶数次. 同理可得, 同时改变两列的操作次数也是偶数次, 故 . 于是 , 即 , 故 . . 第页， 共页 学科网（北京）股份有限公司 $$ 2024 第13届数学竞赛命题研讨资料（组合部分）（题目） 一、组合问题 1 湖南省长沙市第一中学 韩序舜 1、【来源】 2024年全国高中数学联赛竞赛第1题15分 对于正整数 , 有 个集合，满足 : 每个集合有 个元素; 任意两个集合恰有一个公共元素; 所有 个集合交集为空集. 求 的最大值. 二、组合问题 2 江西科技学院附属中学 张敬德 2、【来源】 2024年全国高中数学联赛竞赛第2题15分 某次研讨会共有 人参与，每人至少认识其中 人，试求 的最小值，使得其中必存在彼此认识的 人. 三、组合问题 3 北京大学附属中学 陈宣桦 3、【来源】 2024年全国高中数学联赛竞赛第3题15分 在单位正方形内部放置 个不同的点，证明 : 一定可以选取其中 个点顺次用线段连接，使得这 条线段的长度之和不超过 ; 同时，对于正整数 , 一定可以选取其中 个点顺次用线段连接，使得这 条线段的长度之和不超过 . 四、组合问题 4 学而思广州分校 余泽伟 4、【来源】 2024年全国高中数学联赛竞赛第4题15分 对 , , , , 为大于 的正整数, , 为 个储存位置，把 填入这 个储存位置中，每个位置恰填一个数. 定义一次操作 : 选取一个 , 把 根据除第 个维度以外坐标相同分组，共 组，把每组的 个数按第 个维度坐标升序重新排列填回 中. 对于不能再有变化的状态称为稳定状态. 求最小的 , 使对任意的初始状态，都可用不超过 次操作变为稳定 五、组合问题 5 江西师大附中 陈思洲 5、【来源】 2024年全国高中数学联赛竞赛第5题15分 城市之间有 个不同的航线，每条航线的起点、终点为 城市且均为双向航线．每两条航线除 城市外还恰有一个公共站点，任意三条航线间无公共站点．小数同学想要完成这样的挑战 : 从 城市乘航班出发，每到某两个航线的公共站点，就立即换乘与原航班方向相反的航班 ( 如原先采坐的是 的航班，则立即换乘 方向的航班 ), 挑战乘一定次数后到达 城市．请问 : 对什么样的 , 小数可以保证完成挑战 ? 六、组合问题 6 学而思总部 王正 6、【来源】 2024年全国高中数学联赛竞赛第6题15分 已知 星球上有一亿座城市，初始时城市之间没有任何航线，现有一个航空公司准备建立 条双向航线，每条航线连接两个不同城市，且无两条航线连接相同的两个城市 每座城市的 “繁荣度” 定义为从该城市出发的航线数目．每条航线的 “收益” 为它所连接的两个城市的繁荣度之乘积. 求这 条航线的收益之和的最大可能值. 七、组合问题 7 学而思总部 王正 7、【来源】 2024年全国高中数学联赛竞赛第7题15分 在凸多面体 中，称 的一个面上两条有公共顶点的边构成一个 “角” ( 两条边的公共顶点成为 “角” 的顶点 ). 求证 : 可以将所有 “角” 分为两组，使得对 的每个面 , 位于 上的 “角” 不全在同一组; 且对 的每个顶点 , 以 为顶点的 “角” 不全在同一组. 八、组合问题 8 浙江省诸暨市海亮高级中学 周毅博 8、【来源】 2024年全国高中数学联赛竞赛第8题15分 考虑正 棱柱，连接每个侧面的面对角线产生 个交点，并去掉侧棱，现在我们对这 个交点及 个顶点进行三染色，相邻顶点不能同色，不考虑旋转、翻折情况，求染色方式种数. 考虑正 棱柱，连接每个侧面的面对角线产生 个交点，并去掉侧棱，现在我们对这 个交点及 个顶点进行三染色，相邻顶点不能同色，绕中轴旋转重合算一种，求染色方式种数. 九、组合问题 9 北京市海淀区教师进修学校附属实验学校 郭城 9、【来源】 2024年全国高中数学联赛竞赛第9题15分 为 , 是 行 列的数阵, 表示 中第 行第 列的数, , , 且 同时满足 : 每行恰有五个 ; 任意两行不相同．记集合 中元素的个数为 . 若对任意 , , 中都恰有 行满足第 列和第 列的数均为 . 求证 : . 一十、组合问题 10 成都外国语学校 朱世衡 10、【来源】 2024年全国高中数学联赛竞赛第10题15分 甲乙两人玩如下的游戏 : 对于一个事先取定的正整数 , 甲先选出集合 的 个子集 , , , , 每个子集都含 个元素 接下来, 乙选出 个整数 , , , . 最后, 甲选一个整数 . 若存在一个 以及 , 使得 , 则乙获胜; 否则甲获胜 请根据 的取值讨论谁有必胜策略. 一十一、组合问题 11 浙江温州育英国际实验学校 陈华毅 11、【来源】 2024年全国高中数学联赛竞赛第11题15分 在 的方格表上, 随机放置一颗白子与黑子在不同的格内 现有甲、乙两人, 甲先移动白子, 乙再移动黑子, 交替进行, 且满足下述规则 : 移动只可在横向或纵向改变一格, 同一颗棋子横向与纵向移动必须交替进行 若乙移动后, 恰使黑子与白子落在同一格内, 乙获胜; 否则, 甲获胜 问 : 乙有必胜策略的概率 ? 一十二、组合问题 12 北京明诚外国语学校 于睿元 12、【来源】 2024年全国高中数学联赛竞赛第12题15分 我们称一个数列是 “好的” , 如果这个数列首项是 , 且该数列从第二项开始, 每一项都可以被表示为数列前某些项的和．记 为长为的这样的数列的个数，是否存在正整数 , 使得存在正整数 , 对于任意正整数 , 均有 ? 一十三、组合问题 13 内蒙古通辽实验中学 包永胜 13、【来源】 2024年全国高中数学联赛竞赛第13题15分 牧民苏和家中共有 匹马, 为那达慕赛马将把马匹分成了 个参赛组, 每个参赛组有 匹马．证明, 可以找到两个参赛组, 两者中至少有 个共同马匹. 一十四、组合问题 14 北京师范大学附属实验中学 舒惠泽 14、【来源】 2024年全国高中数学联赛竞赛第14题15分 请问是否可以将一个 元集合的所有 元子集每三个分为一组, 使得每组的三个子集的并集是全集 ? 一十五、组合问题 15 湖南师大附中 陈天择 15、【来源】 2024年全国高中数学联赛竞赛第15题15分 证明 : 存在正整数 , 对任意的正整数 , 存在正整数的集合 , 恰有 个子集元素和为 . 一十六、组合问题 16 湖南师大附中 隆希辰 16、【来源】 2024年全国高中数学联赛竞赛第16题15分 在 的棋盘中, 每个单位方格均填上数字 , 每次操作取有公共边的两个单位方格, 将其中的数同时加 . 能否通过 次操作, 使得各行、各列数之和均为同一个值 ? 如果可以, 求 的最小值. 1 、【答案】 ; 【解析】 由题意，在这 个集合中，存在一个被共用的元素不止一个的集合．( 否则，每一个集合和其他集合共用同一个元素，会导致所有集合共用同一个元素 ) 设该集合为 , 其中的元素为 . 不妨设元素 , 被其他集合共用，设包含元素 的集合有 个，分别为 , , , , 包含元素 的集合有 个，分别为 , , , . 考虑对于满足 , 的正整数 , , , 我们有 : 因为，若 ，则会导致 和 的公共元素至少有 和 ，与题目条件矛盾． 于是 与 , , , 之间两两的公共元素互不相同，而 中的元素中，能与 , , , 共用的只有 个，（ 不能共用）故 . 同理可知， 中，每个元素至多属于 之外的 个集合，于是集合的总个数 至多为 个． 另一方面，我们给出下列构造满足条件 : 取 ； 在平面直角坐标系上取点集 , 取 , , ； 对 , ，集合 包含以下 个元素 : 第一个为 ，第 个元素 为如下产生的点：过点 作斜率为 的直线，与直线 产生交点 ，再将横坐标 在模 的意义下变为 到 之间的数．如集合 . 容易验证，上述 个集合满足条件，所以 的最大值为 . 注：该题目为对下述题目的引申思考 : 设有 个集合，每个集合有 个元素，任意两个集合的并集有 个元素，问此 个集合的并集有多少个元素 ? 另外，本题的构造和 定理有某些共通之处，其内容为：平面上不共线的 个点两两相连，至少会得到 条直线，等号成立当且仅当这些线构成一个射影平面，或者构成一个拟束．本题构造中的 类似于射影平面中的无穷远直线的情形，而问题 中的结构类似于拟束的情形． 2 、【答案】 ; 【解析】 设这 人的集合为 , 所认识的人的集合记为 , , 则 , 若 , 是 中认识的 人，则 . 当 , 不妨设 , 即 , , 彼此认识, 则 . 当 , 不妨设 , 即 , , , 彼此认识, 则 . 依此类推，可得 , , , 彼此认识, 则 ． 当 ，不妨设 ，即 , , , 彼此认识． 由 ，得 , 即 . 下面再说明 是最小的．否则，若 ，我们将 个人均分成 , , , 这 组，每组 人．令同组的人互不相识，不同组的人均彼此认识，则 中任一人所认识的人数均为 . 现在我们从 中任取 人，则必有 人来自同一组，他们互不相识，这与题设“必存在彼此认识的 人”矛盾． 综上所述， 的最小值为 . 3 、【答案】 见解析; 【解析】 证明：引理一 : 在 的矩形中放置不超过 个点，一定可以顺次连接它们，使得总长度不超过 . 不妨设矩形顶点为 , 不妨补成 个点，总长度不减，设所有点的坐标为 . 按照横坐标从小到大 个一组，将所有点均分为 份，则可划分 个 矩形使得每组的 个点都在一个矩形的内部或边上，且 . 首先将每个矩形中的点按纵坐标从小到大进行连接，形成 个组. 然后如下图所示，可以有两种方式构建组间连接线段，使得整体是一个折线. 考虑将所有线段的长度放大为其横纵投影之和来估计线段组的总长度. 从纵投影看，两种方案皆至多占 个 ; 除了组间连接线段之外，第 组的线段的横投影不超过 , 合计不超过 . 因此上述两种连接方式线段总长都不超过 ( 是此方式组间连接线段的水平投影长度之和). 注意到两种连接方式的组间连接线段的水平投影长度之和不超过 , 因此至少有一种连接方式的总长不超过 . 引理二 : 在边长为 的正方形中有 个点，则可以选取 个点顺次连接总长不超过 , 若将 个点的横坐标从小到大排列，则纵坐标构成一个长为 的序列; 则或者存在一个长为 的不增子列，或者存在一个长为 的不减子列 ( 定理 ) 表示在点列中，则或者存在一个长为 的向右上 ( 含向右或向上 ) 的子列，或者存在一个长为 的向右下 ( 含向右或向下 ) 的子列，考虑将其顺次连接总长放缩为投影长度，则恰为首尾两点的横坐标之差加上纵坐标之差. 现在将边长为 的正方形旋转 后进行点的选取，如图所示，可注意到任两点的横纵坐标差之和不会超过 . 利用引理二选取 个点，由抽屉原理得前 个点和后 个点中必有一组总长不超过 . 对于第二小问，将正方形如图分割为中心对称的“井字形”,不妨设其中中心正方形的边长为 , 则 区域的边长为 , 若其中有至少 个点，则由引理二存在 个点顺次连接总长不超过 . 若不存在，则同理有 , , . 相加减去总和得 : . 可不妨设 中至少有 个点 因此由引理一，可以全部连接这些点使得总长不会超过 , 而共有 条线段，至少可以依次分成 组 个线段. 令其中至少有一组不大于 , 取 , 则存在 个点顺次连接总长不超过 . 注   注意到放置更多的点只会使结果更优，在北京市邀请赛中选择了 个点, 此时 . 取 , 则可以得到 , 在原题中仅要求总长小于 . 本题是对旅行商 问题的一个小方面的探索. 4 、【答案】 ; 【解析】 先证 . 在 中填入 ，有定义知每个数在一次操作中只能改变一个维度的坐标，而稳定状态 应在 中，所以 . 再证 时必能变为稳定状态，具体操作为依次选择 即可. 定义 : 一种状态下操作 均无变化，称这种状态为 “ 稳定”. 下面归纳证明依次操作 后为 “ 稳定”. 当 时，成立. 当 成立时，对 反证，若 “ 稳定” 状态 下，再操作 后状态 不为 " 稳定”, 则由定义知 不为 “ 稳定”. , 的 中为 , 中为 , 其中 , , 均为坐标的第 个维度. 记 的 中为 , 中为 , 均为坐标的第 个维度，其中 , , 因操作 后状态为 , 则两个数列单调递增，任意重排两个数列，仍存在 , 而操作前状态为 , 的 中为 , 中为 , 与 为 “ 稳定” 矛盾．即 成立. 综上所述, 的最小值为 . 5 、【答案】 对所有奇数 成立．; 【解析】 对所有奇数 成立．为便于叙述，将两城市 和所有公共站点称为 “点位”, 设 条航线分别为 , , , . 一方面 : 当 为偶数时，构造一种航线安排使其无法完成挑战 : 取 与 其中 , . 满足它们两条航线的公共站点在 航线上比 与 的公共站点更接近 城市; 在 航线上比 与 的公共站点更接近 城市． 此时，对于配对的两航线 与 , 小数无论从这两条中的哪条航线离开 , 在到达 与 的公共站点后, 必然会沿原航线 或 返回到 城, 故无法完成挑战. 另一方面，当 为奇数时，小数的策略是 “每到一个公共站点，立马换另一条航线继续出发，直到到达 或 停止” 小数在选取了该策略后，选择某个航线出发，则有以下事实 : 小数在有限次搭乘后一定会停止，即回到 城或到达 城 设 条航线间的 个公共站点分别为 , , , . 并记 城为 , 城为 . 假设小数从 城出发后不再回到 城或 城，设他经过的点位为 . 由于点位只有有限多个，故存在 , 使得 , 在 中出现一次以上．此时取最小的 , 使得存在 , 满足 且 . 若 , 则 为 即 , 故 表示 城，矛盾; 若 , 设 , , 则 与 均在 中出现．设 出现在航线 上，则 与 均在以航线 有公共站点 的另一条航线上，且均与 的方向相反．于是 与 在同一天航线上且方向相同则 , 这与 的最小性矛盾. 小数从 城选择相同的航线出发，结果是一样的 若小数从 城乘航线 出发后，依次经过点位 , , , 后通过航线 回到 城．则对称地有 : 若小数从 城沿着航线 出发，也将依次通过点 , , , , 并通过航线 回到 城． 回到原问题，假设小数无法到达 城 则对 , 存在 , 使小数通过航线 出发以后必可以通过航线 回到 城．由 得, . 此时将 与 配对，由于 为奇数，故存在 使得 . 设从 城沿航线 出发后依次经过点位 , , , 后沿航线 回到 城．则由 和 得到 , , , 与 , , , 是相同的，故 与 相同. 若 为偶数，则令 , 则 与 相同，矛盾． 若 为奇数，则令 , 则 与 相同，故从 到 的航线与 到 的航线相同，这与小数需要在公共站点换乘矛盾．于是小数不能回到 城，故当 为奇数时，小数必然能够到达 城. 6 、【答案】 ; 【解析】 我们将城市看作顶点，航线看作边，构成的图为 . 每条航线的收益为它连结的两个顶点的度之乘积. 设有 个点 , , , 的度不为 , 设 的度为 . 若记 , 则 且 . 对于一点 , 我们下面估计从 出发的所有航线的收益之和．设其它 个点中与 相连的点为 , , , 与   不连的点为 , , . 因为 , 且 , 因此有 ， 即与 连边的所有点的度之和 ，因此从 出发的所有航线的收益之和 . 因此所有航线的收益之和 ． 由于这 个点之间至多连 条边，因此 ，因此 ．故收益之和 ． 构造：任选 座城市，让其中任两个城市之间有双向航线．此时有 条边，每条边的 “收益” 为 ，总收益为 ． 综上，最大值为 . 注：此题为第 届 第 题． 7 、【答案】 见解析; 【解析】 建立空间直角坐标系，使得 轴与 任意两顶点连出的直线均不垂直 ( 由于这些直线过原点的垂面不可能覆盖整个空间，因此这显然可以做到 ). 对 的每个面，将其 坐标最大 ( 下面简称为 “最高” ) 的顶点所在角分到第一组，将其最低的顶点所在角分到第二组．记整个多面体最高和最低的顶点分别为 和 . 则目前为止，有如下事实 : 事实 对于 和 之外的顶点 , 至少有两个以 为顶点的角还未被分组 ( 因为从 出发必有朝上的边和朝下的边，因此必有两个角是一边朝上一边朝下的，这样的角不可能是平面中最高或最低的角 ) 如果有某个面的顶点同时包含 和 , 将该面中 所在角挪到第二组, 所在角挪到第一组 现在 和 处的角均既有黑色又有白色．对于还未分组的角 , 将其依次分到含 “以 为顶点已分组的角” 较少的组，由事实 可知这样操作后每个顶点处的角不全在同一组．每个面的角也不全在同一组是显然的． 如果任何面的顶点不同时包含 和 , 则任取一个含 的面，将其中 所在角挪到第二组，其中本来第二组中的角挪到第一组; 再任取一个含 的面，将其中 所在角挪到第一组，其中本来第一组中的角挪到第二组．现在 和 处的角均既有黑色又有白色，且依然满足事实 对于还未分组的角 , 将其依次分到含 “以 为顶点已分组的角” 较少的组，由事实 可知这样操作后每个顶点处的角不全在同一组．每个面的角也不全在同一组是显然的． 综上，原题结论成立． 注:此题为第 届 第 题. 8 、【答案】 见解析 ; 【解析】 记上底面的各顶点为 , , , ,下底面对应的顶点为 , , , , 面 的对角线交点为 , 所有下角标均在模 下表示，三染色分别用 赋值，同样也是在模 下表示. 下定义 “顺三角形” 为顺时针方向赋值加 ( 模 意义下 ) 的三角形; “逆三角形” 为逆时针方向赋值加 ( 模 意义下 ) 的三角形. 此时，只需确定初始 的赋值，及所有三角形的顺逆情况，即可确定唯一确定的赋值 于是我们只需要研究 “顺逆三角形” 的情形即可. 首先，我们先通过上底面 , , , , 研究 , 的顺逆情况． 注意到当 , 是顺三角形时, ； 当 , 是逆三角形时, ； 而 , 故设有 个顺三角形, 个逆三角形, 则 当 时, , 上底面共有 . 当 时, , 上底面共有 . 当 时, , 上底面共有 . 下面，我们再考虑下底面的情形． 情形一：若 , 此时右边 , 顺逆不同, 且可导出 , 则可推出此时所有上下对应的三角形都是顺逆不同的． 即当上底面顺逆情形确定时，取顺逆不同的下底面与之唯一对应． 情形二：若 , 此时可知 , 则可导出所有 均相同, 此时可知上底面是交替出现的, 对应的下底面恰好错开一格． 此时要满足条件 , 则 . 即若 时, 当上底面交替的种数会多一种下底面的对应方式, 计算后为 种；若 时，无多余情形． 故最后答案为： 当 时, , 上底面共有 . 当 时, , 上底面共有 . 当 时, , 上底面共有 . 我们先考虑固定不旋转的情形，此时满足要求的染色图形形成的集合记为 ，有 . 下根据最小旋转重合步数 对所有结果进行分类，注意到转 次后必回，则 ． 情形一：若 ，此时上底面每个顶点染色相同，矛盾． 情形二：若 ，此时上底面 ，则这五个三角形只能为 “ 逆 顺” 或者 “ 顺 逆”，由对称性，先讨论 “ 逆 顺”，则旋转后的必可以逆开头，若赋 ，则有           . 对 赋值有三种，故共有 类. 同理 “ 顺 逆” 也有 类．即 情形，共 类，每类会在 中出现 次； 情形三：若 ，设有 类，每一类旋转 次回，故每类在 中出现 次． 我们对 进行算两次，得 ． 下面，我们再考虑下底面的情形： 情形一：若 , 此时右边 , 顺逆不同, 且可导出 , 则可推出此时所有上下对应的三角形都是顺逆不同的． 即当上底面顺逆情形确定时，取顺逆不同的下底面与之唯一对应． 情形二：若 , 此时可知 , 则可导出所有 均相同，此时可知上底面是交替出现的，对应的下底面恰好错开一格． 此时要满足条件 , 则 ． 因为 时, 故无多余情形． 综上共 种. 9 、【答案】 见解析; 【解析】 表中 行, 每行共 个 对, 即 的数对共有 ; 满足 的 共有 组, 由题设, 恰有 行满足 , 共 记 中有 项 为 , 项为 . 满足 的 数对共有 组. 由题设, 恰有 行满足 , 故 同时, . 得到, . 注   命题的推论含 : 此表格行数 至多 . 对于 中的元素 , 满足 的 数对共有 组; 满足 的 数对共有 组. . . 可以根据这些等式构建其他问题．或调整 中为 的项数来更正上界. 命题核心围绕算两次．求证的结论和本题的条件 “若对任意 , 中都恰有 行满足第 列和第 列的数均为 .” 可以调整至更难或更简单的难度. 10 、【答案】 见解析; 【解析】 下面证明, 当 时, 甲有必胜策略; 当 时, 乙有必胜策略 记 . 当 时, 下面说明甲的必胜策略 : 甲取 个集合为 . 即是 中所有满足 余数在 范围内的所有元素. 然后乙取出 个数 , , , . 对任意 , 我们将 所有元素平移 后构成集合 , 即 . 下面我们归纳证明 , 这样一定有一个元素不在任意 中, 取 即可. 下面仅说明, 当 时, 乙的必胜策略, 这样 乙都必胜． 对于甲选择的 , , , , 记 . 我们将归纳证明乙可以挨个选择 , , , , 使得对于某个 , 我们总可以适当的选择 , 使得对应的 满足 . ( 即 至少可以覆盖 中一半的元素 ). 下面对 进行归纳 : 奠基 : 时, 任取 , 此时 至少可以覆盖 中一半元素, 从而 . 归纳 : 对于 , 已经找到了 , , , , 使得对应的 ; 满足 下面考虑如何找 . 注意到当让 , 取遍 , 则 将 中每个元素覆盖了 次, 所以对 中的元素共计覆盖了 次. 这样必存在一个 , 至少覆盖 中 个元素． 选择这个 , 这样 . 归纳完毕． 这样乙可以换个选择 , , , 之后, , 这意味着 , 从而甲任选一个整数 , 都存在一个 以及 , 使得 , 这样乙必胜． 证毕． 11 、【答案】 ; 【解析】 记两颗棋子横向与纵向的距离为 , 总距离 , 其中 , . 当 为奇数时, 对方格表进行黑白染色, 每个格子仅与异色的格子相邻 ( 上、下、左、右四个格子 ), 此时白子和黑子分别在异色的格子内, 进行若干次移动后, 仍在异色格子内, 不可能落在同一格. 当 为偶数时, 此时 , 对 , 的奇偶性进行讨论. , 均为偶数, 此时乙第一次移动方向在横纵向选择中与甲保持一致 ( 即甲第一次横向移动, 乙也横向移动, 甲第一次纵向移动, 乙也纵向移动 ). 乙可进行操作使每一次甲、乙行动完后, , 不增 由于方格表大小有限, 白子不可能一直往黑子反方向移动, 甲总会在某次移动后, 使 , 其中之一减少 , 此时乙可移动黑子向白子靠近, 此时 , 少其中之一共减少 . 不断操作, 直至 , 其中之一为 , 不妨 为 . 每次 改变时, 乙总能保证移动后 仍为 , 则同理不断操作能使 为 . 此时乙有必胜策略. , 均为奇数, 此时乙第一次移动方向在横纵向选择中与甲不同 ( 即甲第一次横向移动, 乙纵向移动, 甲第一次纵向移动, 乙横向移动 ). 将甲、乙各操作两次称为一轮, 乙可通过操作, 使每轮操作后 不增 由于方格表大小有限, 总会在若干轮后, 使 减少, 而每轮操作后 , 的奇偶性均不变, 必会出现 , 其中之一为 , 不妨 为 . 此时每轮操作乙可保证 恒为 ( 乙先在 方向上改变, 则先令 ), 则只用考虑 方向 而每轮操作 不增且总存在某些轮使 减少, 由于奇偶性不变, 直至 . 此时 , 再考虑甲一开始移动的方向, 不妨为 方向, 若甲移动使 , 则乙再移动 方向, 此时黑白子已在同一格 每轮一开始, 甲只能在 方向上, 远离黑子运动, 乙可对应移动使每轮结束 . 而方格表大小有限, 总会在某轮后, 甲不能在 方向上, 远离黑子运动, 此时 , 则此轮中黑白子可落入同一格. 故当 为偶数时, 乙有必胜策略, 当 为奇数时, 乙无必胜策略. 乙有必胜策略的概率 . 12 、【答案】 不存在; 【解析】 若不然, 存在 满足对于 , 均有 . 令 为长为 的且前 项依次为 的好数列的个数． 显然, , 对任意 成立 根据定义, . 接下来我们说明, 对于任意 , . 实际上, 对于每一个长为 的且前 项依次为 的好数列, 不妨设其每一项依次为 , , , . 则由假设知, 以下 项两两不同 : ;  ;  . 所以对于每一个长为 的好数列, 以其为前 项的长为 的好数列至少有个 个, 所以对于任意 , . 所以 , 其中 . 取 使得 , 则 矛盾 ! 综上所述, 上述 不存在． 注:在尝试估计下一项的大小时, 发现好数列的下一位至少可以是前若干项的前缀和, 但我们需要精细化这些前缀和, 以找到一个更好的估计. 13 、【答案】 见解析; 【解析】 将 马匹编号为 至 号, 以 记 号马匹所参加的参赛组数目, 则有 . 任意选取两个参赛组 选法当然有 种 引入示性函数 如果 号马匹是这两个参赛组的公共马匹; 否则. 易知 . 于是 就是这两个参赛组的共同成员的人数, 这是一个随机变量 为了完成题目的解答, 我们来计算 的数学期望, 即平均值 由组合数的凸性, 易知 所以存在两个参赛组, 他们中的公共马匹数不少于 匹. 14 、【答案】 可以; 【解析】 下面直接给出构造． 注  正在研究 元集合的所有 元子集情况, 感觉难度挺大, 在此抛砖引玉一下. 15 、【答案】 见解析; 【解析】 对 充分大, 设正整数 使 , 则 , 并记 , 取集合 为最大为 的连续 个正整数构成的集合; 集合 为 的最大的连续 个正整数构成的集合, 为 的全体 构成的集合．取 . 下证 : 对 子集 , 满足 的元素和为 , 则要么 恰包含 中某一个元素, 要么 恰包含 中某两个元素; 且已知包含 中某一个元素, 或包含 中某两个元素时, 元素和为 的 的子集恰有一个．如已证, 则满足条件的子集个数恰为 个. 证 : 取 充分大使 ; ; 则 均存在且无重复元素. 取 充分大使 , 则 中最小的两个元素之和大于 , 则 至多包含 中一个元素. 如 包含 中某一个元素, 此时其余元素之和 , 则 不包含 中元素, 且由 进制结论知 的自然数均存在唯一的 的子集的元素之和表示, 即恰有一个. 如 不包含 中元素, 取 充分大使 ; . 注意到 全体元素与 最大元素之和 , 说明 不能只包含 或 个 中元素; 中三个最小元素和 ; 说明 不能包含 个以上的 中元素．则 恰包含 中某两个元素; 此时其余元素之和 ; 由 进制结论知 的自然数均存在唯一的 的子集的元素之和表示, 即恰有一个. 计算知 即可满足全部充分大条件, 即 成立.综上，证毕. 注：实际上 时, ; , , 已满足条件. 16 、【答案】 可以．当 为偶数时, 最小值为 , 当 为奇数时, 最小值为 .; 【解析】 为偶时, 构造如下 : 时, 行的两格同时加 , 行的两格同时加 即可; , 时, 次操作后行和列和均为 . 时, 前 行 列经过 次操作后行和列和均为 ; 第 行, 、 列同时加 ; 第 行, 、 列同时加 共 次操作后行和列和均为 . 的证明如下 : 至少有一次操作, 一次操作至少让行和或者列和加 , 故行和列和至少为 . 方格表中数字和至少为 , 一次操作使方格表中数字和加 , 故 . 为奇数时, 构造如下 : 时, 构造如右图, 每条线段表示一次操作, 一次操作线段端点所在两个方格各加 . , 时, 次操作后行和列和均为 ; 时, 前 行 列经过 次操作后行和列和均为 , 第 行, 、 列同时加 两次 第 行, 、 列同时加 两次 共 次操作后行和列和均为 . 的证明如下 : 首先, 设行和为 , 则 方格表中总数和 , 故 为偶数 注意到, 若一次操作同行的两个方格各加一, 那么每行的和的奇偶性不变 设 为第 行行和, 为使第 行与第 行中方格同时加一的操作次数 , , . 故 . 于是 , 即同时改变两行的操作次数为偶数次. 同理可得, 同时改变两列的操作次数也是偶数次, 故 . 于是 , 即 , 故 . . 第页， 共页 学科网（北京）股份有限公司 $$