同一骨架 2024 年广西预赛 · P006494
把禁配关系整理清楚后，一组互不相交的禁配对能迫使每对至少舍去一个元素，从而给允许集合的大小上界。达到上界仍需整体构造；若先压缩数值，还必须证明单射，并核实用于配对上界的限制在像中仍然成立。
前题先沿二进制链把元素单射移到上半区间，再用相邻整数互素配对；后题先用最大公因数参数化列全禁配边，以互不相交的边给上界，再用顶点覆盖的补集构造。
培玉 · 一试
2021 年山东预赛
F4解答题组合计数综合
如果任取 的一组数中，总有两个不同数的乘积是这两个数和的整数倍， 问最少要取多少个数？
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
提示
先独立尝试，再展开工具说明与想法来源。
想想一道相关的题
先回想这道题的想法，再试试当前题。
思路
独立集是不含边的顶点子集；顶点覆盖与每条边至少相交。匹配中的每条边迫使独立集至少舍弃一个不同顶点，因此匹配提供上界、覆盖补集提供构造。
想法从哪来：先把一对数的整除关系用最大公因数拆开，两个互素部分的和与它们的乘积也互素，所以必须整除公共因子。这个参数化给出有限范围内所有合法数对，保证后续图模型的边没有漏掉。题目要保证取到一条合法边，等价于问最多能取多少个互不连边的数。找一组端点互异的合法数对，任何无边集合每对至少舍一数，给出上界；要证明锋利，还需展示同样大小的顶点覆盖，删掉它便留出无边反例。不是任意图都有匹配数等于覆盖数，所以这里必须实际给出并核对两份有限证书。
先刻画一对数何时满足条件。把两数除以最大公因数后，整除条件迫使这个最大公因数含有两个互素部分之和； 在 的范围内可完整列出所有合法数对，再用一组互不相交的合法边给上界，用一个顶点覆盖的补集给下界。
解答
设 ，写 ，其中 。条件 等价于
而 ，故 。因此所有合法数对都可写成
由较大数不超过 ，对 (1) 作有限枚举，得到全部合法数对：
在 (2) 中有以下 对两两不共享数字的合法数对：
若所取的一组数中没有合法数对，则每一对至多取一个，所以至多取 个。
另一方面，删去
后剩下 个数。由完整清单 (2) 可见，每个合法数对都至少含有一个被删去的数， 故这 个数中没有合法数对。于是 个还不能保证，而 个一定能保证。 所以最少要取
个数。
复核
参数化 (1) 说明清单 (2) 没有遗漏；12对互不相交给出强制删去至少12个数的上界，所列12元集合又确为全部合法边的顶点覆盖。
方法总结
“任取若干点必含一条边”就是有限图的独立集问题；数论参数化负责列边，匹配与顶点覆盖分别给出两侧界。
为什么评为 F4（会透露解法方向）
先穷尽合法数对的互素参数表示，再寻找12对不相交边给保证界，并构造同样大小的顶点覆盖证最优。
联系 · 1 条
已记下，谢谢！