设 $n、k$ 为正整数，$T=\{(x, y, z) | x, y, z \in \mathbf{Z}, 1 \leqslant x, y, z \leqslant n\}$ 为空间直角坐标系中 $n^3$ 个整点构成的集合．已知集合 $T$ 中 $(3n^2-3n + 1) + k$ 个点染成红色，满足：若集合 $T$ 中两点 $P、Q$ 均染成红色且 $PQ$ 平行于坐标轴，则线段 $PQ$ 上的所有整点也均染成红色证明：存在至少 $k$ 个互不相同的立方体，它们的边长为 $1$ 且每个顶点均染成红色．
【难度】
【出处】
2017第33届CMO试题
【标注】
【答案】
略
【解析】
为方便起见，引入如下术语．若一个单位立方体的顶点均为红色，则称之为红色立方体；若一个单位正方形的顶点均为红色，且此正方形平行于 $Oxy$ 平面，则 称之为红色正方形；若一条单位线段的顶点 均为红色，且此线段平行于 $x$ 轴，则称之为红色线段．设所有红点构成的集合为 $R$，平面 $z=c上$ 的所有红点构成的集合为 $R_c$，直线 $y=b, z=c$ 上的所有红点构成的集合为 $R_{bc}$．先证明一个引理．
先证明一个引理．
引理：对正整数 $1 \leqslant c \leqslant n$，$R_c$ 中的红色正方形的数目不小于 $\left|R_{c}\right|-(2 n-1)$．
证明：设 $R_c$ 中有 $S(c)$ 个红色正方形，$I$ 条红色线段．从两方面估算 $I$．
一方面，对每个 $1\leqslant b\leqslant n$，若 $R_{bc}$ 非空，可 设其中 $x$ 坐标最小的红点为 $P$，$x$ 坐标最大的 红点为 $Q$．则由题意，知 $R_{bc}$ 恰为线段 $PQ$ 上所 有整点所构成的集合于是，$R_{bc}$ 上红色线段 的数目为 $|R_{bc}| -1$．
故 $\displaystyle I=\sum\limits_{R_{b c} \neq \varnothing}\left(\left|R_{b c}\right|-1\right) \geqslant \sum_{R_{b c} \neq \varnothing}\left|R_{b c}\right|-n=\left|R_{c}\right|-n$．①
另一方面，每条红色线段在 $x$ 轴上的投影为 $x$ 轴上的单位线段，将所有红色线段按照其投影分类．对于 $x$ 轴上的单位线段 $u$，设以 $u$ 为投影的红色线段的数目为 $I_u$．若 $I_u\geqslant 1$，设以 $u$ 为投影的红色线段的 $y$ 坐标的最小值为 $y_0$，最大值为 $y_1$，则 $I_{u} \leqslant y_{1}-y_{0}+1$．
由题意，知对于每个整数 $y \in\left[y_{0}, y_{1}\right]$，$u \times\{y\} \times\{ c\}$ 也均为红色线段．于是，对整数 $y \in\left[y_{0}, y_{1}-1\right], u \times\{y, y+1\} \times\{c\}$ 均为红 色正方形，共 $y_{1}-y_{0}$ 个，$y_{1}-y_{0}\geqslant I_u-1$．
故 $S(c) \geqslant \sum_{I_{u} \geqslant 1}\left(I_{u}-1\right) \geqslant \sum_{I_{u} \geqslant 1} I_{u}-(n-1)=I-(n-1)$．②
结合式 ①、② 得 $S(c) \geqslant I-(n-1)\geqslant\left|R_{c}\right|-n-(n-1)=\left|R_{c}\right|-(2 n-1)$ 引理得证．
设共有 $C$ 个红色立方体，$S$ 个红色正方形．
一方面，由引理知 $\displaystyle S=\sum\limits_{c=1}^{n} S(c) \geqslant \sum_{c=1}^{n}\left(\left|R_{c}\right|-(2 n-1)\right)$ ③
另一方而，每个红色正方形在 $Oxy$ 平面上的投影为 $Oxy$ 平面的单位正方形，将所有 红色芷方形按照其投影分类．对于 $Oxy$ 平面 上的单位正方形 $v$，设以 $v$ 为投影的红色单位 正方形的数目为 $S_v$．若 $S_v\geqslant 1$，设以 $v$ 为投影 的红色正方形的 $z$ 坐标的最小值为 $z_0$，最大值为 $z_1$，则 $S_v\leqslant z_1-z_0+1$．
由题意，知对于每个整数 $z \in\left[z_{0}, z_{1}\right]$，$v \times\{z\}$ 也均为红色正方形于是，对于每个整 数 $z \in\left[z_{0}, z_{1}-1\right], v \times\{z, z+1\}$ 均为红色立方体，共 $z_{1}-z_{0}$ 个，$z_{1}-z_{0} \geqslant S_{v}-1$．
故 $\displaystyle C \geqslant \sum\limits_{s_{v} \geqslant 1}\left(S_{v}-1\right) \geqslant \sum_{s_{v} \geqslant 1} S_{u}-(n-1)^{2}=S-(n-1)^{2}$．④
结合式 ③、④ 即得
$\displaystyle C \geqslant S-(n-1)^{2}\geqslant \sum\limits_{c=1}^{n}\left(\left|R_{c}\right|-(2 n-1)\right)-(n-1)^{2}=\sum_{c=1}^{n}\left|R_{c}\right|-\left(3 n^{2}-3 n+1\right)=k$．
先证明一个引理．
引理：对正整数 $1 \leqslant c \leqslant n$，$R_c$ 中的红色正方形的数目不小于 $\left|R_{c}\right|-(2 n-1)$．
证明：设 $R_c$ 中有 $S(c)$ 个红色正方形，$I$ 条红色线段．从两方面估算 $I$．
一方面，对每个 $1\leqslant b\leqslant n$，若 $R_{bc}$ 非空，可 设其中 $x$ 坐标最小的红点为 $P$，$x$ 坐标最大的 红点为 $Q$．则由题意，知 $R_{bc}$ 恰为线段 $PQ$ 上所 有整点所构成的集合于是，$R_{bc}$ 上红色线段 的数目为 $|R_{bc}| -1$．
故 $\displaystyle I=\sum\limits_{R_{b c} \neq \varnothing}\left(\left|R_{b c}\right|-1\right) \geqslant \sum_{R_{b c} \neq \varnothing}\left|R_{b c}\right|-n=\left|R_{c}\right|-n$．①
另一方面，每条红色线段在 $x$ 轴上的投影为 $x$ 轴上的单位线段，将所有红色线段按照其投影分类．对于 $x$ 轴上的单位线段 $u$，设以 $u$ 为投影的红色线段的数目为 $I_u$．若 $I_u\geqslant 1$，设以 $u$ 为投影的红色线段的 $y$ 坐标的最小值为 $y_0$，最大值为 $y_1$，则 $I_{u} \leqslant y_{1}-y_{0}+1$．
由题意，知对于每个整数 $y \in\left[y_{0}, y_{1}\right]$，$u \times\{y\} \times\{ c\}$ 也均为红色线段．于是，对整数 $y \in\left[y_{0}, y_{1}-1\right], u \times\{y, y+1\} \times\{c\}$ 均为红 色正方形，共 $y_{1}-y_{0}$ 个，$y_{1}-y_{0}\geqslant I_u-1$．
故 $S(c) \geqslant \sum_{I_{u} \geqslant 1}\left(I_{u}-1\right) \geqslant \sum_{I_{u} \geqslant 1} I_{u}-(n-1)=I-(n-1)$．②
结合式 ①、② 得 $S(c) \geqslant I-(n-1)\geqslant\left|R_{c}\right|-n-(n-1)=\left|R_{c}\right|-(2 n-1)$ 引理得证．
设共有 $C$ 个红色立方体，$S$ 个红色正方形．
一方面，由引理知 $\displaystyle S=\sum\limits_{c=1}^{n} S(c) \geqslant \sum_{c=1}^{n}\left(\left|R_{c}\right|-(2 n-1)\right)$ ③
另一方而，每个红色正方形在 $Oxy$ 平面上的投影为 $Oxy$ 平面的单位正方形，将所有 红色芷方形按照其投影分类．对于 $Oxy$ 平面 上的单位正方形 $v$，设以 $v$ 为投影的红色单位 正方形的数目为 $S_v$．若 $S_v\geqslant 1$，设以 $v$ 为投影 的红色正方形的 $z$ 坐标的最小值为 $z_0$，最大值为 $z_1$，则 $S_v\leqslant z_1-z_0+1$．
由题意，知对于每个整数 $z \in\left[z_{0}, z_{1}\right]$，$v \times\{z\}$ 也均为红色正方形于是，对于每个整 数 $z \in\left[z_{0}, z_{1}-1\right], v \times\{z, z+1\}$ 均为红色立方体，共 $z_{1}-z_{0}$ 个，$z_{1}-z_{0} \geqslant S_{v}-1$．
故 $\displaystyle C \geqslant \sum\limits_{s_{v} \geqslant 1}\left(S_{v}-1\right) \geqslant \sum_{s_{v} \geqslant 1} S_{u}-(n-1)^{2}=S-(n-1)^{2}$．④
结合式 ③、④ 即得
$\displaystyle C \geqslant S-(n-1)^{2}\geqslant \sum\limits_{c=1}^{n}\left(\left|R_{c}\right|-(2 n-1)\right)-(n-1)^{2}=\sum_{c=1}^{n}\left|R_{c}\right|-\left(3 n^{2}-3 n+1\right)=k$．
答案
解析
备注
