2012第27届CMO试题

• 知识点

  >

  二试组合部分

略

设 $a<b<c$．令 $x=a+b, y=a+c, z=b+c$
则 $x<y<z, x+y>z$，且 $x+y+z$ 为偶数 ①
反之，若存在 $x, y, z \in A$ 满足性质 ①，
则取 $a=\dfrac{x+y-z}{2}, b=\dfrac{x+z-y}{2}, c=\dfrac{y+z-x}{2}$，有 $a, b, c \in \mathbf{Z}, 1 \leqslant a<b<c \leqslant 2012$，且 $x=a+b, y=a+c, z=b+c$．
于是，题述条件等价于对任意的 $k$ 元子集 $A$，均有 $x, y, z \in A$，满足性质 ①．
若 $A=\{1,2,3,5,7, \cdots, 2011\}$，则 $|A|=1007$，且集合 $A$ 中不含有满足性质 ① 的三个元素．因此，$k\geqslant 1008$．
下面证明：任意一个 $1 008$ 元子集均含有三个元素满足性质 ①．
接下来证明一个更一般的结论：
对任意整数 $n(n\geqslant 4)$，集合 $\{1,2, \cdots, 2 n\}$ 的任意一个 $n+2$ 元子集均含有三个元素满足性质 ①．
对 $n$ 进行归纳．
当 $n=4$ 时，设集合 $A$ 是 $\{1,2, \cdots, 8\}$ 的一个六元子集．则 $A \bigcap\{3,4, \cdots, 8\}$ 至少有 $4$ 个元素．
若 $A \bigcap\{3,4, \cdots, 8\}$ 中含有三个偶数，则 $4、6、8\in A$ 且满足性质 ①；
若 $A \bigcap\{3,4, \cdots, 8\}$，中恰含有两个偶数，则它还应含有至少两个奇数，取这两个奇数，则 $4、6、8$ 中至少有两个偶数与这两个奇数可以形成一个满足性质 ① 的三元数组，由于至少有两个偶数，故存在三个数满足性质 ①；
若 $A \bigcap\{3,4, \cdots, 8\}$ 中恰含有一个偶数，则它含有全部三个奇数，此偶数与 $5、7$ 即构成满足性质 ① 的三元数组．
因此，当 $n=4$ 时，结论成立．
假设结论对 $n(n\geqslant 4)$ 成立，考虑 $n+1$ 的情形．