给定整数 $n\geqslant 2$．设 $n$ 个非空有限集 $A_{1}, A_{2}, \cdots, A_{n}$ 满足：$\left|A_{i} \Delta A_{j}\right|=|i-j|(i, j \in\{1,2, \cdots, n\})$，规定 $X \Delta Y=\{a | a \in X, a \notin Y\} \cup\{a | a \in Y, a \notin X\}$．
求 $\left|A_{1}\right|+\left|A_{2}\right|+\cdots+\left|A_{n}\right|$ 的最小值．
求 $\left|A_{1}\right|+\left|A_{2}\right|+\cdots+\left|A_{n}\right|$ 的最小值．
【难度】
【出处】
2013第28届CMO试题
【标注】
【答案】
略
【解析】
对整数 $n\geqslant 2$，证明对任意正整数 $k$ 有 $S_{2 k} \geqslant k^{2}+2, S_{2 k+1} \geqslant k(k+1)+2$
先给出两个明显的结论：
（1）对有限集 $X、Y$ 有 $|X|+|Y| \geqslant|X \Delta Y|$．
（2）若非空有限集 $X、Y$ 满足 $|X \Delta Y|=1$ 则 $|X|+|Y| \geqslant 3$．
（事实上，假设不然，则必有 $|X|=|Y|=1$ 于是，$|X \Delta Y|=0$ 或 $2$，矛盾．）
当 $n=2k$ 时，由条件与结论（1）知 $\left|A_{i}\right|+\left|A_{2 k+1-i}\right| \geqslant\left|A_{i} \Delta A_{2 k+1-i}\right|=2 k+1-2 i(i=1,2, \cdots, k-1)$
又 $\left|A_{k} \Delta A_{k+1}\right|=1$ 及结论（2）得
$A_{k}|+| A_{k+1} | \geqslant 3\begin{aligned} \Rightarrow S_{2 k} &=\left|A_{k}\right|+\left|A_{k+1}\right|+\sum_{i=1}^{k-1}\left(\left|A_{i}\right|+\left|A_{2 k+1-i}\right|\right) \geqslant 3+\sum_{i=1}^{k-1}(2 k+1-2 i)=k^{2}+2 \end{aligned}$
同理，当 $n=2k+1$ 时，有 $\left|A_{i}\right|+\left|A_{2 k+2-i}\right| \geqslant\left|A_{i} \Delta A_{2 k+2-i}\right|=2 k+2-2 i(i=1,2, \cdots, k-1)$ 且 $\displaystyle \left|A_{k}\right|+\left|A_{k+1}\right| \geqslant 3,\left|A_{k+2}\right| \geqslant 1\Rightarrow S_{2 k+1}=\left|A_{k}\right|+\left|A_{k+1}\right|+\left|A_{k+2}\right|+
\sum_{i=1}^{k-1}\left(\left|A_{i}\right|+\left|A_{2 k+2-i}\right|\right)\geqslant 4+\sum\limits_{i=1}^{k-1}(2 k+2-2 i)=k(k+1)+2$
另一方面，取集合 $A_{1}, A_{2}, \cdots, A_{2 k+1}$ 如下：
$A_{i}=\{i, i+1, \cdots, k\}(i=1,2, \cdots, k)$
$A_{k+1}=\{k, k+1\}$
$A_{k+j}=\{k+1, k+2, \cdots, k+j-1\}(j=2, \cdots, k+1)$
对这组集合，易验证 $\left|A_{i} \Delta A_{j}\right|=|i-j|$ 对任意的 $i, j \in\{1,2, \cdots, 2 k+1\}$ 成立
此时，经计算得 $S_{2 k+1}=\dfrac{k(k+1)}{2}+2+\dfrac{k(k+1)}{2}=k(k+1)+2$
当取前 $2 $ 个集合时，得 $S_{2 k}=S_{2 k+1}-k=k^{2}+2$
综上，$S_n$ 的最小值为 $\left[\dfrac{n^{2}}{4}\right]+2$ 其中，$[x]$
表示不超过实数 $x$ 的最大整数．
先给出两个明显的结论：
（1）对有限集 $X、Y$ 有 $|X|+|Y| \geqslant|X \Delta Y|$．
（2）若非空有限集 $X、Y$ 满足 $|X \Delta Y|=1$ 则 $|X|+|Y| \geqslant 3$．
（事实上，假设不然，则必有 $|X|=|Y|=1$ 于是，$|X \Delta Y|=0$ 或 $2$，矛盾．）
当 $n=2k$ 时，由条件与结论（1）知 $\left|A_{i}\right|+\left|A_{2 k+1-i}\right| \geqslant\left|A_{i} \Delta A_{2 k+1-i}\right|=2 k+1-2 i(i=1,2, \cdots, k-1)$
又 $\left|A_{k} \Delta A_{k+1}\right|=1$ 及结论（2）得
$A_{k}|+| A_{k+1} | \geqslant 3\begin{aligned} \Rightarrow S_{2 k} &=\left|A_{k}\right|+\left|A_{k+1}\right|+\sum_{i=1}^{k-1}\left(\left|A_{i}\right|+\left|A_{2 k+1-i}\right|\right) \geqslant 3+\sum_{i=1}^{k-1}(2 k+1-2 i)=k^{2}+2 \end{aligned}$
同理，当 $n=2k+1$ 时，有 $\left|A_{i}\right|+\left|A_{2 k+2-i}\right| \geqslant\left|A_{i} \Delta A_{2 k+2-i}\right|=2 k+2-2 i(i=1,2, \cdots, k-1)$ 且 $\displaystyle \left|A_{k}\right|+\left|A_{k+1}\right| \geqslant 3,\left|A_{k+2}\right| \geqslant 1\Rightarrow S_{2 k+1}=\left|A_{k}\right|+\left|A_{k+1}\right|+\left|A_{k+2}\right|+
\sum_{i=1}^{k-1}\left(\left|A_{i}\right|+\left|A_{2 k+2-i}\right|\right)\geqslant 4+\sum\limits_{i=1}^{k-1}(2 k+2-2 i)=k(k+1)+2$
另一方面，取集合 $A_{1}, A_{2}, \cdots, A_{2 k+1}$ 如下：
$A_{i}=\{i, i+1, \cdots, k\}(i=1,2, \cdots, k)$
$A_{k+1}=\{k, k+1\}$
$A_{k+j}=\{k+1, k+2, \cdots, k+j-1\}(j=2, \cdots, k+1)$
对这组集合，易验证 $\left|A_{i} \Delta A_{j}\right|=|i-j|$ 对任意的 $i, j \in\{1,2, \cdots, 2 k+1\}$ 成立
此时，经计算得 $S_{2 k+1}=\dfrac{k(k+1)}{2}+2+\dfrac{k(k+1)}{2}=k(k+1)+2$
当取前 $2 $ 个集合时，得 $S_{2 k}=S_{2 k+1}-k=k^{2}+2$
综上，$S_n$ 的最小值为 $\left[\dfrac{n^{2}}{4}\right]+2$ 其中，$[x]$
表示不超过实数 $x$ 的最大整数．
答案
解析
备注
