设 $n$ 是给定的正整数，集合 $S=\{1,2,\cdots,n\}$．对非空的有限实数集合 $A$ 和 $B$，求 $|A \otimes S|+|B \otimes S|+|C \otimes S|$ 的最小值，其中，$C=A+B=\{a+b | a \in A, b \in B\}$，$X(\otimes) Y=\{x | x$ 恰好属于 $X$ 和 $Y$ 中的一个 $\}$，$|X|$ 表示有限集合 $X$ 的元素个数．
【难度】
【出处】
2011第26届CMO试题
【标注】
【答案】
略
【解析】
所求的最小值是 $n+1$．
首先，取 $A=B=S$，可知 $|A \otimes S|+|B \otimes S|+|C \otimes S|=n+1$
下面证明：$l=|A \otimes S|+|B \otimes S|+|C \otimes S| \geqslant n+1$
记 $X \setminus Y=\{x | x \in X, x \notin Y\}$．显然，$\begin{aligned} l=&|A\setminus S|+| B\setminus S|+|C\setminus S |+ |S\setminus A|+| S\setminus B|+|S\setminus C | \end{aligned}$．
于是，只要证明：
（1）$|A\setminus S|+| B\setminus S|+|S\setminus C | \geqslant 1$
（2）$|C\setminus S|+| S\setminus A|+|S\setminus B | \geqslant n$
先证（1）．
事实上，若 $|A\setminus S|=| B\setminus S|=0$，则 $A, B \subseteq S$．
故 $1$ 不可能是 $C$ 中元素，即 $|S\setminus C|\geqslant 1$
再证（2）．
若 $A \bigcap S=\varnothing$，则 $|S \backslash A| \geqslant n$，结论成立．
若 $A \bigcap S=\varnothing$，设 $A \bigcap S$ 的元素中最大的一个是 $n-k(0 \leqslant k \leqslant n-1)$，则 $|S\setminus A | \geqslant k$ ①
另一方面，对 $i=k+1, k+2, \cdots, n$，要么 $i \notin B$（此时 $i \in S \backslash B$），要么 $i\in B$（此时 $n-k+i \in C$，即 $n-k+i \in C \backslash S$）
所以，$|C\backslash S|+| S\backslash B| \geqslant n-k$．②
由式 ①、② 即得（2）．
综上可知，$l\geqslant n+1$．
所以最小值是 $n+1$．
首先，取 $A=B=S$，可知 $|A \otimes S|+|B \otimes S|+|C \otimes S|=n+1$
下面证明：$l=|A \otimes S|+|B \otimes S|+|C \otimes S| \geqslant n+1$
记 $X \setminus Y=\{x | x \in X, x \notin Y\}$．显然，$\begin{aligned} l=&|A\setminus S|+| B\setminus S|+|C\setminus S |+ |S\setminus A|+| S\setminus B|+|S\setminus C | \end{aligned}$．
于是，只要证明：
（1）$|A\setminus S|+| B\setminus S|+|S\setminus C | \geqslant 1$
（2）$|C\setminus S|+| S\setminus A|+|S\setminus B | \geqslant n$
先证（1）．
事实上，若 $|A\setminus S|=| B\setminus S|=0$，则 $A, B \subseteq S$．
故 $1$ 不可能是 $C$ 中元素，即 $|S\setminus C|\geqslant 1$
再证（2）．
若 $A \bigcap S=\varnothing$，则 $|S \backslash A| \geqslant n$，结论成立．
若 $A \bigcap S=\varnothing$，设 $A \bigcap S$ 的元素中最大的一个是 $n-k(0 \leqslant k \leqslant n-1)$，则 $|S\setminus A | \geqslant k$ ①
另一方面，对 $i=k+1, k+2, \cdots, n$，要么 $i \notin B$（此时 $i \in S \backslash B$），要么 $i\in B$（此时 $n-k+i \in C$，即 $n-k+i \in C \backslash S$）
所以，$|C\backslash S|+| S\backslash B| \geqslant n-k$．②
由式 ①、② 即得（2）．
综上可知，$l\geqslant n+1$．
所以最小值是 $n+1$．
答案
解析
备注
