给定整数 $m\geqslant 3,n\geqslant 3$．设集合 $S=\{(a, b) | a \in\{1,2, \cdots, m\}$，$b \in\{1,2, \cdots, n\}, A$ 为 $S$ 的子集．若不存在正整数 $x_{1}, x_{2}, x_{3}, y_{1}, y_{2},y_3$ 使得（$x_{1}<x_{2}<x_{3}, y_{1}<y_{2}<y_{3}$ 且 $\left(x_{1}, y_{2}\right),\left(x_{2}, y_{1}\right),\left(x_{2}, y_{2}\right)\left(x_{2}, y_{3}\right),\left(x_{3}, y_{2}\right) \in A$，求集合 $A$ 的元素个数的最大值．
【难度】
【出处】
2017中国东南数学奥林匹克试题(高二)
【标注】
【答案】
略
【解析】
若一个集合 $X$ 中存在某点 $(x_2,y_2)$，其上、下、左、右四个方向分别仍有 $X$ 中的点 $\left(x_{2}, y_{3}\right),\left(x_{2}, y_{1}\right),\left(x_{1}, y_{2}\right),\left(x_{3}, y_{2}\right)$，则称 $X$ 为"中心点集"．本问题等价于确定 $S$ 中至多能取出多少个点，使得由这些点组成的集合 $A$ 不是中心点集．
一方面将 $S$ 中横坐标为 $1$ 或 $m$ 的点，以及纵坐标为 $1$ 或 $n$ 的点全部取出组成集合 $A_0$，显然 $A_0$ 不是中心点集，此时有 $\left|A_{0}\right|=2 m+2 n-4$．
另一方面，我们证明：若 $A \subseteq S,|A| \geqslant 2 m+2 n-3$，则 $A$ 必是中心点集．
对 $1\leqslant i\leqslant n$，设 $A$ 中纵坐标为 $i$ 的有 $k_i$ 个，若 $k_i\geqslant 3$，则将 $A$ 中该行除最左，最右两点之外的点染上红色．这样至少有 $\left(k_{1}-2\right)+\cdots+\left(k_{n}-2\right)=|A|-2 n$ 个点染有红色．
对 $2\leqslant j\leqslant m-1$，设 $A$ 中横坐标为 $j$ 的点有 $l_j$ 个，若 $l_j\geqslant 3$，则将 $A$ 中该 列除最上、最下两点之外的点染上蓝色；再将 $A$ 中横坐标为 $1$ 或 $m$ 的点全部染 上蓝色．这样至少有 $l_{1}+\left(l_{2}-2\right)+\dots+\left(l_{n-1}-2\right)+l_{m}=|A|-2 m+4$ 个点染有蓝色．
注意到 $\begin{aligned} &(|A|-2 n)+(|A|-2 m+4) =(|A|-2 n-2 m+3)+|A|+1>|A| \end{aligned}$，必一个点既被染了红色，也被染了蓝色，且这个点的横坐标不是 $1$ 或 $m$（横坐标为 $1$ 或 $m$ 的点不可能染有红色）．由染色的依据可知，该点的上、下、左、右 四个方向均有 $A$ 中的其他点，从而A为中心点集．
综上所述，$A$ 的元素个数的最大值为 $2m+2n-4$．
一方面将 $S$ 中横坐标为 $1$ 或 $m$ 的点，以及纵坐标为 $1$ 或 $n$ 的点全部取出组成集合 $A_0$，显然 $A_0$ 不是中心点集，此时有 $\left|A_{0}\right|=2 m+2 n-4$．
另一方面，我们证明：若 $A \subseteq S,|A| \geqslant 2 m+2 n-3$，则 $A$ 必是中心点集．
对 $1\leqslant i\leqslant n$，设 $A$ 中纵坐标为 $i$ 的有 $k_i$ 个，若 $k_i\geqslant 3$，则将 $A$ 中该行除最左，最右两点之外的点染上红色．这样至少有 $\left(k_{1}-2\right)+\cdots+\left(k_{n}-2\right)=|A|-2 n$ 个点染有红色．
对 $2\leqslant j\leqslant m-1$，设 $A$ 中横坐标为 $j$ 的点有 $l_j$ 个，若 $l_j\geqslant 3$，则将 $A$ 中该 列除最上、最下两点之外的点染上蓝色；再将 $A$ 中横坐标为 $1$ 或 $m$ 的点全部染 上蓝色．这样至少有 $l_{1}+\left(l_{2}-2\right)+\dots+\left(l_{n-1}-2\right)+l_{m}=|A|-2 m+4$ 个点染有蓝色．
注意到 $\begin{aligned} &(|A|-2 n)+(|A|-2 m+4) =(|A|-2 n-2 m+3)+|A|+1>|A| \end{aligned}$，必一个点既被染了红色，也被染了蓝色，且这个点的横坐标不是 $1$ 或 $m$（横坐标为 $1$ 或 $m$ 的点不可能染有红色）．由染色的依据可知，该点的上、下、左、右 四个方向均有 $A$ 中的其他点，从而A为中心点集．
综上所述，$A$ 的元素个数的最大值为 $2m+2n-4$．
答案
解析
备注
