同一骨架 2021 年山东预赛 · P007040
把禁配关系整理清楚后，一组互不相交的禁配对能迫使每对至少舍去一个元素，从而给允许集合的大小上界。达到上界仍需整体构造；若先压缩数值，还必须证明单射，并核实用于配对上界的限制在像中仍然成立。
前题先沿二进制链把元素单射移到上半区间，再用相邻整数互素配对；后题先用最大公因数参数化列全禁配边，以互不相交的边给上界，再用顶点覆盖的补集构造。
培玉 · 一试
2024 年广西预赛
F4解答题组合计数综合
设 为数集 的 元子集，且 中的任意两个数既不互素又不存在整除关系。求 的最大值。
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
提示
先独立尝试，再展开工具说明与想法来源。
想想一道相关的题
先回想这道题的想法，再试试当前题。
思路
倍增链是奇数m开头的 ；每条链在(N/2,N]中恰有一项。相邻正整数互素，乘以整数不会破坏原有公因数。
想法从哪来：两个限制同时出现，上半区间的偶数很容易给出一个候选，但上界不能简单把互素数两两配对，因为原集合可能散在整个区间。先利用无整除关系，把所有整数按奇数部分相同分成倍增链，每条链至多占一个位置。再将入选点沿链推到上半区间，既无碰撞，也保留原来共有的质因数。这样所有入选数都挤到一个短区间里，可以按相邻整数互素来配对，得到上界。构造选上半区间偶数时，公因数条件自动满足，而无整除关系还要用“大数小于小数的两倍”单独说明。
“不整除”提示按奇数部分分成二进制链；将每条链的入选数推到上半区间后，再利用相邻奇偶数互素配对。
解答
将 按相同奇数部分分成互不相交的链
同一条链中任意两数存在整除关系，故 在每条链中至多取一数。把每个入选数沿所在链乘以适当的 的幂，映到该链中唯一位于
的数。这是单射，且乘以 的幂不会破坏两数的公因数，因此像集仍然任意两数不互素。
把上半区间配成 对
每对是两个相邻正整数，因而互素，像集在每对中至多取一个。故 。
取
共有 个数。它们都是偶数，且任意较大者小于较小者的两倍，所以既不互素又无整除关系。因此
复核
每条二进制链在 中恰有一项；构造集合的最小元素为 ，而 ，故不可能整除。
方法总结
整除反链可用二进制链压到上半区间；“任意两数不互素”再与相邻数互素配对结合，给出精确上界。
为什么评为 F4（会透露解法方向）
须把每个入选数沿二进制链搬到上半区间，证明单射且保留不互素性，才能以相邻互素对给出更强上界。
联系 · 1 条
已记下，谢谢！