对于非空数集 $S、T$，定义 $S+T=\left\{s+t | s \in S, t \in T\right\},2 S=\left\{\left.2{s}\right|{s} \in S\right\}$
设 $n $ 为正整数，$A,B$ 均为 $\{1,2, \cdots, n \}$ 的非空子集证明：存在 $A+B$ 的子集 $D$，使得
$D+D \subseteq 2(A+B)$ 且 $|D| \geqslant \dfrac{|A||B|}{2 n}$
其中，$|X|$ 表示有限集 $X$ 的元素个数．
设 $n $ 为正整数，$A,B$ 均为 $\{1,2, \cdots, n \}$ 的非空子集证明：存在 $A+B$ 的子集 $D$，使得
$D+D \subseteq 2(A+B)$ 且 $|D| \geqslant \dfrac{|A||B|}{2 n}$
其中，$|X|$ 表示有限集 $X$ 的元素个数．
【难度】
【出处】
2013第29届CMO试题
【标注】
【答案】
略
【解析】
令 $S_{y}=\{(a, b) | a-b=y, a \in A, b \in B\}$．
由于 $\sum_{y=1-n}^{n-1}\left|S_{y}\right|=|A||B|$，故存在 $y_{0}\left(1-n \leqslant y_{0}\right.$ $\leqslant n-1 )$，使得
$\left|S_{y_{0}}\right| \geqslant \dfrac{|A||B|}{2 n-1}>\dfrac{|A||B|}{2 n}$．
取 $D=\left\{a+b |(a, b) \in S_{y_{0}}\right\}$，则 $|D|=\left|S_{y_{0}}\right|>\dfrac{|A||B|}{2 n}$．
由 $S_{y_0}$ 的定义，知对子集 $D$ 中的每个元素 $d$，存在 $(a, b) \in S_{y_{0}}$，使得 $d=a+b \in A+B$．
因此，$D \subseteq A+B$．
对于 $d_{1}, d_{2} \in D$，设
$d_{1}=a_{1}+b_{1}=2 b_{1}+y_{0}=2 a_{1}-y_{0},d_{2}=a_{2}+b_{2}=2 b_{2}+y_{0}$
其中，$b_{1}, b_{2} \in B, a_{1} \in A$．
则 $d_{1}+d_{2}=2 a_{1}-y_{0}+2 b_{2}+y_{0}=2\left(a_{1}+b_{2}\right) \subseteq 2(A+B)$．
综上，集合 $D$ 满足要求．
由于 $\sum_{y=1-n}^{n-1}\left|S_{y}\right|=|A||B|$，故存在 $y_{0}\left(1-n \leqslant y_{0}\right.$ $\leqslant n-1 )$，使得
$\left|S_{y_{0}}\right| \geqslant \dfrac{|A||B|}{2 n-1}>\dfrac{|A||B|}{2 n}$．
取 $D=\left\{a+b |(a, b) \in S_{y_{0}}\right\}$，则 $|D|=\left|S_{y_{0}}\right|>\dfrac{|A||B|}{2 n}$．
由 $S_{y_0}$ 的定义，知对子集 $D$ 中的每个元素 $d$，存在 $(a, b) \in S_{y_{0}}$，使得 $d=a+b \in A+B$．
因此，$D \subseteq A+B$．
对于 $d_{1}, d_{2} \in D$，设
$d_{1}=a_{1}+b_{1}=2 b_{1}+y_{0}=2 a_{1}-y_{0},d_{2}=a_{2}+b_{2}=2 b_{2}+y_{0}$
其中，$b_{1}, b_{2} \in B, a_{1} \in A$．
则 $d_{1}+d_{2}=2 a_{1}-y_{0}+2 b_{2}+y_{0}=2\left(a_{1}+b_{2}\right) \subseteq 2(A+B)$．
综上，集合 $D$ 满足要求．
答案
解析
备注
