2017中国东南数学奥林匹克试题(高一)

• 知识点

  >

  二试组合部分

略

证法一
若一个集合 $X$ 中存在某点 $\left(x_{1}, y_{2}\right)$，为．，其下方，右方分别仍有 $X$ 中的点 $\left(x_{1} , y_{3}\right) ,\left(x_{1}, y_{1}\right) \cdot\left(x_{2} ,y_{2}\right)$，则称 $X$ 为"中心聚点"．本问题等 价于确定 $S$ 中至多能取出多少个 点．使得由这些点组成的集合 $A$ 不是中心点集．
一方面．将 $S$ 中纵坐标为 $1$ 或 $n$ 的点．以及横坐标为 $m$ 的点全部取出，组成集合 $A_0$．显然 $A_0$ 不是中心点集．此时有 $\left|A_{0}\right|=2 m+n-2$．
另一方面，我们证明：若 $A \subseteq S,|A| \geqslant 2 m+n-1$，则 $A$ 必是中心点集．
对 $1\leqslant i\leqslant n$，设 $A$ 中纵坐标为 $i$ 的点有 $k_i$ 个，若 $k_2\geqslant 2$，则将 $A$ 中该行除最右边的点之外的点染成红色．这样至少有 $\left(k_{1}-1\right)+\cdots+\left(k_{n}-1\right)=|A|-n$ 个点染有红色．
对 $1\leqslant j\leqslant m-1$，设 $A$ 中横坐标为 $j$ 的点有 $l_j$ 个，若 $l_j\geqslant 3$，则将 $A$ 中该列除最上、最下两点之外的点染成蓝色，再将 $A$ 中横坐标为 $m$ 的点全部染成 蓝色．这样至少有 $\left(l_{1}-2\right)+\cdots+\left(l_{m-1}-2\right)+l_{m}=|A|-2 m+2$ 个点染有蓝色．
注意到 $(|A|-n)+(|A|-2 m+2)=(|A|-2 m-n+1)+|A|+1>|A|$，，必一个点既被染了红色，也被染了蓝色，且这个点的横坐标不是 $ m$（横坐标为 $m$ 的点不可能染有红色）．由染色的依据可知，该点的上方、下方、右方均有 $A$ 中的其他点，从而 $A$ 为中心点集．
综上所述，$A$ 的元素个数的最大值为 $2m+n-2$．
证法二
将 $S$ 视为一般的 $n$ 行 $m$ 列点阵 $S_{n,m}$，并对任意正整数 $m\geqslant 1, n\geqslant 2$ 考虑本问题，以确定 $S_{n,m}$ 中至多能取出多少个点，使得由这些点组成的 集合 $A$ 不是中心点集（"中心点集＂的定义参见解法一）．
一方面，使 $|A|=2 m+n-2$ 的例子是存在的（参见证法一）
另一方面，我们证明：若 $A$ 是 $S_{n,m}$ 的子集，且 $| A |\geqslant 2m + n -1$，则 $A$ 必是中心点集（在 $m=1$ 或 $n=2$ 时，$\left|S_{n, m}\right|=m m<2 m+n-1$，结论自动视为成立）．
对 $n+m$ 进行归纳．当 $m=1$ 或 $ n=2$ 时，结论已成立．对 $m\geqslant 2,n\geqslant 3$
的情如况．假如 $n+m - 1$ 的情形均已得到证明，我们考虑 $n+m$ 的情形．
如果 $S_{n,m}$ 中存在一行至多只有 $A$ 中的 $1$ 个点，那么去掉这一行，考虑剩
下的点阵 $S_{n-1,m}$．由于 $\left|A \cap S_{n-1, m}\right| \geqslant|A|-1 \geqslant 2 m+(n-1)-1$，根据归纳假设，$A \cap S_{n-1, m}$ 为中心点集，从而 $A$ 为中心点集．
如果 $S_{n,m}$ 中每一行至少有 $A$ 中的 $2$ 个点，考虑 $S_{n,m}$ 的最左边一列．若这列存在 $A$ 中的 $3$ 个点，则从上到下依次取出其中 $3$ 个为 $u、v、w$，由于 $v$ 所在行必还有一点 $t\in A$，且在 $v$ 右方，故 $A$ 已为中心点集；若这列至多只有 $A$ 中的 $2$ 个点，去掉这一列，考虑剩下的点阵 $S_{n,m-1}$．由于 $\left|A \cap S_{n, m-1}\right| \geqslant|A|-2 \geqslant2(m-1)+n-1$，根据归纳假设知，$A \cap S_{n, m-1}$ 为中心点集，从而 $A$ 为中心点集．
由数学归纳法知，结论成立．
综上所述，$A$ 的元素个数的最大值为 $2m+n-2$．