培玉 · 一试
一试训练题
将集合 分拆为 个互不相交的非空子集 的并，并且对于每一个 （），其中任意两个不同的元素的和都不是完全平方数，求 的最小值。
作答
这是解答题，请在纸上写出完整过程。写完后对照解答给自己评分。
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
冲突图：每个数作一点，不能同组的两数连边；同组不得有边。三个两两相连的点必须分入三个不同组。
想法从哪来：先试按奇偶分两组，会发现偶数内部仍有平方和，单靠奇偶不能解决。此时应把任务拆成“至少几组”和“怎样分组”：把和为平方数的两数看成冲突，寻找三个两两冲突的数，就能先锁住下界。构造的方向来自平方数模四只能余零或一，因此两类奇数可各自安放，再挑选与它们不冲突的偶数。这里同余只是筛去大多数数对，不能替代最后核验；余零的偶数和还要逐对检查。下界与一份覆盖全部元素的合法构造相遇，才真正得到最小值。
先寻找一小组三个数，它们彼此冲突便能逼出分组数下界。构造时利用平方数模四的余数，将奇数先分开，再把合适的偶数放入；同余未能排除的同组偶数对还须明确补查。
解答
因为 、、，这三个数两两不能同组，所以 。
下面给出三组构造：
三个集合非空、两两不交，且并为 。在 或 中，两个奇数之和为2模4，奇偶两数之和为3模4，都不可能是平方数。对同组中的两个偶数，若它们之和为2模4也可排除；其余可能的和经逐对计算只属于
其中没有平方数。这也覆盖 中的所有可能平方和数对。因此三组构造满足条件，所求最小值为 。
复核
构造中的三组大小分别为14、14、8，合计36且元素不重不漏。奇奇与奇偶的危险和已由模4排除，剩下偶数和中可疑的平方只有4、16、36、64，它们均不在正式解答列出的有限和集合里。下界用的6、19、30又恰落在三组各一处，构造与冲突三角形相容。
方法总结
冲突分组先以一个小团给下界，再用同余组织人工可读构造。模4不是完整证明：它不能排除余0的和，必须把余下的有限候选逐类核掉；这样可用很少的核验替代几百对裸枚举。
为什么评为 F4（会透露解法方向）
三对禁配给出三色下界后，仍须安排奇数与偶数的混合分组，并核验模4不能自动排除的偶数数对。
已记下，谢谢！