同一骨架 2023 年北京预赛 · P006652
“任意安排都必有一组”的阈值题，需要保证方向与坏构造两半。先把对象分成彼此不发生目标关系的组，用容量或鸽巢给出必然性；最小或最大保证值还必须由满足全部原限制的分组反例锁定。
前题先找两两比例接近的一批整数迫使同组数对，再以同余类拉开间距；后题把参观时间化为区间，贪心分成互不重叠组，用两种群体规模的乘积界，并反向构造分离时间段。
培玉 · 一试
2025 年贵州预赛
十六划分中的邻近数对
F4填空题组合计数综合
已知集合 （ 且 ）的任意一个 划分 ，一定存在某个集合 （ 且 ），在 中有两个元素 满足
则 的最小值为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
先独立尝试，再展开工具说明与想法来源。
想想一道相关的题
先回想这道题的想法，再试试当前题。
思路
鸽巢原理：多于组数的对象分入这些组，至少一组有两个对象。按模十六分类指余数相同的整数放在同组，此时任意两数之差是十六的非零倍数。
想法从哪来：把“比例接近”先改写成差距限制：较大数与较小数的差不超过较小数的五分之一。越靠近区间末端，允许的差越大，所以先寻找末端一段连续整数，而不必一开始研究所有划分。要塞进十六组并强迫碰撞，就试十七个数；让这一段的两端之比也不超过上限，段内任意一对就都合格。 这只提供充分性，最小值还需要反向构造。既然十六组是固定的，试按模十六分组，使同组两数至少隔十六；再用较小规模的末端位置，检验这一间隔始终大于允许差距。上界与坏划分便在同一个临界点衔接。
本题需要同时证明一个上界和一个反例。为保证任意 划分都出现所需数对，可寻找 个两两之比不超过 的连续整数并使用鸽巢原理；为证明更小的规模不够，则按 模 分组，使同组两数的差至少为 。
解答
先证明 时题目中的结论一定成立。考虑集合中的 个数
将它们放入 个集合 中，由鸽巢原理，至少有两个数 落在同一个 中。此时 且 ，故
所以 时任意 划分都满足题意。
再证明 时结论不一定成立。将 按模 的余数分成 个集合，即同余于 的数分别放入一组。若同一组中有 ，则
又因 ，必有 ，于是
从而
因此这个 划分中没有任何一组含有满足 的两个元素。
综上， 尚不能保证，而 已能保证，所以
复核
到 恰有 个整数，且其中任意较小数至少为 、较大数至多为 ，所以鸽巢所得的任意同组数对都符合比例上界。模 的反例划分覆盖 到 且各组互不相交；同组最小差为 ，而可能的较小数不超过 ， 故比例不等式严格反向，反例有效。
方法总结
“任意 划分中必有同组数对”通常先寻找 个彼此都满足目标关系的对象，用 鸽巢原理给出充分性；最小值问题还必须为前一个整数构造坏划分。若目标关系由两数之差 控制，按模 分类常能让同组元素保持足够大的间距。
为什么评为 F4（会透露解法方向）
既要发现80至96的17个数强制同组，又要用模16分组证明95不足，上界与反构造采用不同组织。
联系 · 1 条
已记下，谢谢！