易混 2023 年北京预赛 · P005920
两题都涉及平方关系,但可压缩的信息不同。要求平方和被某整数整除时,剩余类能完整判定这条整除关系;要求两个数之和确为完全平方数时,同余只是必要筛选,还须实际构造满足等式的数对。
前题根据禁配类型选出尽可能多的数;后题要迫使两色中出现目标数对,可先构造两色无法避开的三点结构。
把集合
任意划分为两个不交的非空子集。证明:至少有一个子集中包含两个数,这两个数之和为完全平方数。
这是解答题,请在纸上写出完整过程。写完后对照解答给自己评分。
把两个子集看成两种颜色。
只需在原集合中找出三个数,使其两两之和都是平方数;三点用两色染色必有同色的一对。
注意到 都属于 ,并且
把这三个数放入两个子集时,由抽屉原理,至少两个数落入同一子集;而任意一对的和都是完全平方数。因此结论成立。
三个构造数均在闭区间 内且互不相同,三组和分别核对为连续三个整数的平方。
二划分中要强迫出现同类关系,可把对象及目标数对视为图;构造一个三角形即可用二染色不可能性结束证明。
核心是寻找区间内三个数两两和为平方,可先选47²、48²、49²再反解三个数;一旦构造1056、1153、1248,二分结论立即成立。
核心工具:抽屉原理与极端构造
易混 2023 年北京预赛 · P005920
两题都涉及平方关系,但可压缩的信息不同。要求平方和被某整数整除时,剩余类能完整判定这条整除关系;要求两个数之和确为完全平方数时,同余只是必要筛选,还须实际构造满足等式的数对。
前题根据禁配类型选出尽可能多的数;后题要迫使两色中出现目标数对,可先构造两色无法避开的三点结构。
已记下,谢谢!