培玉 · 一试
2024 年北京预赛
F4填空题组合计数综合
已知 ，且 中任意两个数的差的绝对值不等于 ，也不等于 ，则 的最大值为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
独立集指图中两两不相邻的顶点集；长度13的环最多选6点，长度12的路径最多选6点。这两结论都可直接用相邻配对证明。
想法从哪来：两种禁差分开配对会互相打架；先把它们相加，得到一个自然的块长。在一个十三元块内，沿“加4、越界减13”的顺序走，两个方向的实际差恰好就是两种禁差，所有数又因4与13互素而走遍。这把原先的数集限制变成奇数个座位围成一圈、相邻座位不能同选。沿圈给每个已选座位配一个未选后继，就能得到每块的上界。末尾不满一块时要改看删去顶点后的路径。构造则不能各块随意交替：固定同一组模十三余数，才会同时避开跨块的禁差。
差 与差 在模 意义下是相反方向。每个连续十三元块可按步长 排成一个奇环。
解答
把每个连续的十三个整数按相对余数
排列。相邻两项（包括首尾）的差的绝对值均为 或 ，故它们构成一个 环，独立集至多有 个元素。
因 ，前 个完整块至多选 个；最后十二个数对应从上述环删去一个顶点所得的十二顶点路径，也至多选 个。因此
取所有模 余数属于
的整数，任意两数之差都不为 或 ，且在 至 中恰有 个。故
复核
所选六个余数在上述 环中两两不相邻；跨越相邻13元块的差 也对应同一对模 相邻余数，因此构造全局有效。
方法总结
两种禁差之和等于块长时，可把每块转为循环图；奇环独立数给上界，交替余数类给同步构造。
为什么评为 F4（会透露解法方向）
须发现4与9共同组成13环，用每块独立数6给出界，再设计模13余数集使跨块禁差也不出现。
已记下，谢谢！