培玉 · 一试
2023 年甘肃预赛
从 中取 个不同的数构成集合 ，使得 中一定有 个不同的数 ，满足 能被 整除，则 的最小值为。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
抽屉原理：超过余数种数的对象必有同余。这里对象是无序且不重复元素的二元子集；1至20每个模20剩余类恰出现一次。
想法从哪来：四个数的正负交替和，先移项看成两组数对的和同余。这样一个k元集合能产生多少个无序数对、余数有多少种，便直接给出抽屉原理的阈值。但碰撞的两个数对是否一定有四个不同元素，还需证明：若共用一个元素，消去后剩下两个数在完整剩余系内同余，只能是同一个数，反而使数对相同。证明保证性后，最小阈值还差一个少一元素的反例。构造时可从模二十的零类开始逐次添数，要求新增数对和不撞旧和；最后列齐全部数对余数作为证书，避免漏掉交叉配对。
条件等价于两组互不相同的二元组具有相同的模 和。对所有无序数对使用抽屉原理，并给出六元反例证明界限最优。
解答
若 含 个数，则共有
个无序数对，而它们的和模 只有 种余数。故存在两个不同数对的和模 相同。两个数对不可能恰好共用一个元素；否则消去该元素后，另外两个数模 同余，而它们都取自 ，只能相等。因此这两个数对共含四个不同的数，适当记为 与 ，便有
另一方面，取
其十五个无序数对的和模 依次构成
彼此不同，故其中不存在所要求的四个数。因此 还不能保证，最小值为
复核
构造中的六个数互不相同；15个余数的个数正好等于全部无序数对数，已排除任何重复配对和。
方法总结
形如 的四元关系应改写成两两和相等；保证性结论用数对抽屉原理，上界最优性用模意义下的弱 Sidon 集构造。
为什么评为 F4（会透露解法方向）
上界需证同余数对不共用元素，下界还要构造六元素且所有无序数对和模20互异的集合。
已记下，谢谢！