2024 年内蒙古预赛

解答

先证下界。给定正整数 $d$，写成 $d=4^{r}q$，其中 $4\nmid q$。若 $q\equiv 1$ 或 $3(\mathrm{mod}4)$，对格点定义

若 $q\equiv 2(\mathrm{mod}4)$，定义

若两个整数格点之差为 $(u,v)$ 且 $u^2+v^2=d$，则 $u,v$ 都被 $2^r$ 整除；约去 $4^r$ 后，第一种情形恰有一个商为奇数，第二种情形两个商均为奇数。因此这两个格点的 ${\chi }_d$ 颜色不同。（若 $d$ 不能表示为两个平方和，则结论显然。）

把 ${\chi }_{d_1}$ 与 ${\chi }_{d_2}$ 合成一个四染色。任一同色类内不会出现平方距离 $d_1$ 或 $d_2$，而四个颜色中至少一个含有

个点，故 $c(n)\ge 1$。

再取 $d_1=1,d_2=2$。把 $2n\times 2n$ 格点阵分成 $n^2$ 个互不相交的 $2\times 2$ 小方格。每个小方格中任意两点的平方距离为 $1$ 或 $2$，所以合法集合在每个小方格中至多取一点，即至多有 $n^2$ 个点。因此 $c(n)\le 1$。

综上，