每日一题[3174]寻找奇环

把集合 $A=\{1011,1012, \cdots, 2022\}$ 任意划分为两个不交的非空子集.证明:至少有一个子集中包含两个数,这两个数之和为完全平方数.

解析    用 $1012$ 个点表示这些数,如果两个数之和为完全平方数,则在它们对应的点之间连线,得到一个包含 $1012$ 个节点的无向图.问题转化为在这个无向图中不存在长度为奇数的环. 尝试证明存在长度为 $3$ 的环,即\[\begin{cases} a+b=x^2,\\ b+c=y^2,\\ c+a=z^2,\end{cases}\] 不妨设 $a<b<c$,于是 $x<z<y$,考虑到集合 $A$ 中的数两两之和的取值集合为 $\{2023,2024,\cdots,4043\}$,因此 $x,y,z\in\{45,46,\cdots,63\}$.此时适当的取 $x,y,z$,解出符合要求的 $a,b,c$ 即可,如取 $(x,y,z)=(47,49,48)$,则 $(a,b,c)=(1056,1153,1248)$ 就完成了证明.

备注    因为 $x^2+y^2+z^2$ 是偶数,所以 $x,y,z$ 为三偶数或者二奇一偶,也可以设\[(x,y,z)=(2k-1,2k+1,2k),(2k-2,2k+2,2k),\]则对应\[(a,b,c)=(2k^2-4k,2k^2+1,2k^2+4k),(2k^2-8k,2k^2+4,2k^2+8k),\]然后取 $k$ 的合适的值即可.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复