2026 年浙江预赛

解答

(1) 反设不存在题目所说的 $4$ 格同色。对第 $j$ 列和颜色 $c$，记该列中颜色为 $c$ 的格数为 $a_{j,c}$。于是

把同一列中同色的两个格子所对应的无序行对计数。由组合数的凸性，或把相差至少 $2$ 的 两个数作一次均衡化可使组合数之和减小，得到

对全部 $n$ 列求和，所计对象总数 $T$ 满足

另一方面，固定一个无序行对和一种颜色。若它在两列中都被计数，这两行与这两列交叉处的 四格便全为该颜色，与反设矛盾。因此每个“行对、颜色”至多对应一列，从而

然而由 $n=p(p+1)$，

这与 (2)、(3) 矛盾。因此必有两行两列交叉处的四格同色。

(2) 以有限域 ${\mathbb{F}}_p$ 中的有序对 $(x,y)$ 标记各行，以有序对 $(u,v)$ 标记各列，恰各有 $p^2$ 个。把颜色也用 ${\mathbb{F}}_p$ 的元素编号，并规定行 $(x,y)$ 与 列 $(u,v)$ 交叉处的颜色为

下面证明这种染色不存在单色矩形。若不然，设两个不同行的标记为 $(x_1,y_1),(x_2,y_2)$，两个不同列的标记为 $(u_1,v_1),(u_2,v_2)$，且四个交叉格同色。 对每一行分别比较两列的颜色，由 (4) 得

两式相减，得到

若 $u_1=u_2$，则上面的任一等式给出 $v_1=v_2$，这与两列不同矛盾。 若 $u_1\ne u_2$，因 ${\mathbb{F}}_p$ 是域，由 (5) 得 $x_1=x_2$；再比较任一列中两行的颜色， 便得 $y_1=y_2$，这与两行不同矛盾。

故 (4) 给出了所需染色，结论成立。