1990第5届CMO试题

• 知识点

  >

  二试组合部分

略

首先在 $f(A \cup B)=f(A)+f(B)-1990$ 中，令 $A=B=\varnothing$，可得到 $f(\varnothing)=1990$．设 $D=A_{1} \cup A_{2} \cup A_{3} \cdots \cup A_{k}$，$ A_{i}$ 有两个元素 $(i=1,2, \cdots,k)$，易知 $\begin{aligned} F(D)=& f\left(A_{1}\right)+f\left(A_{2}\right)+\cdots+f\left(A_{k}\right)-(k-1) \times 1990>1990 \Rightarrow f\left(A_{1}\right)+f\left(A_{2}\right)+\cdots+f\left(A_{k}\right)>1990 k \end{aligned}$ 必存在一个 $i$，使得 $f(A_i)>1990$．于是，$A_i$ 的任何非空偶子集 $S$，都有 $f(S)>1990$，在所有满足条件（2）的子集中（显然，这样的子集存在），找出一个元素个数最多的，不妨设为 $P_{1}$，$P_{1}$ 的补集设为 $Q_{1}$．
在 $Q_{1}$ 中，若任何 $Q_{1}$ 的二元子集对应的 $f$ 值都小于或等于 $1990$，那么就容易证明 $Q$ 满足条件（3），这样 $P_{1},Q_{1}$ 就满足条件（1），（2），（3），因此，不妨设 $Q_{1}$ 的一个二元子集 $\{x,y\}$ 满足 $f(\{x, y\})>1990$．
若对 $P_{1}$ 中的每一个元素 $a$，$f(\{x, a\})>1990$ 的话，很显然，$P_{1} \bigcup\{x\}$ 也满足条件（2），并且 $P_{1} \bigcup\{x\}$ 比 $P_1$ 的元素个数多．
因此 $P_1$ 中存在一个 $a$，$f(\{x, a\}) \leqslant 1990$，同理也存在一个 $b$，$f(\{y, b\}) \leqslant 1990$．若 $a\ne b$，就有 $f(\{x, y, a, b\})=f(\{x, y\})+f(\{a, b\})-1990>1990$ 与 $f(\{x, y, a, b\})=f(\{x, a\})+f(\{y, b\})-1990 \leqslant 1990$ 矛盾，因此 $a=b$，即 $f( | x, a\} ) \leqslant 1990, f( | y, a\} ) \leqslant 1990$，并且对于 $P_1$ 中的其他任意元素 $c$，有 $f( | x, c\} )>1990, f(\{y, c\})>1990$，此时，容易验证：$P_{1} / a \cup\{x, y\}$ 亦满足条件（2），并且元素个数比 $P_1$ 多．这就得出了矛盾，因此结论成立．