China Mathematical Olympiad

For each positive integer $k$, we prove that the minimum value of $S_{2k}$ is $k^2+2$; the minimum value of $S_{2k+1}$ is $k(k+1)+2$. Firstly, define the sets $A_1,A_2,\dots ,A_{2k},A_{2k+1}$ as follows: $$A_i=\{i,i+1,\dots ,k\},i=1,2,\dots ,k;A_{k+1}=\{k,k+1\};$$ $$A_{k+j}=\{k+1,k+2,\dots ,k+j-1\},j=2,3,\dots ,k+1.$$

For this family of sets, it is easy to verify that $|A_i\Delta A_j|=j-i=|i-j|$ holds in the following cases: (1) $1\le i<j\le k$; (2) $1\le i<j=k+1$; (3) $1\le i<k+1<j\le 2k+1$; (4) $k+1=i<j\le 2k+1$; (5) $k+2\le i<j\le 2k+1$. Moreover, the case of $i=j$ is trivial, and the case of $i>j$ can be reduced to the case of $i<j$. Thus for all $i,j\in \{1,2,\dots ,2k+1\}$, we have verified that $$|A_i\Delta A_j|=j-i=|i-j|.$$ For the above $(2k+1)$ sets, we can easily calculate that $$S_{2k+1}=\frac{k(k+1)}{2}+2+\frac{k(k+1)}{2}=k(k+1)+2;$$ if we choose the first $2k$ sets, we get that $$S_{2k}=S_{2k+1}-k=k^2+2.$$

Secondly, we show that $S_{2k}\ge k^2+2$ and $S_{2k+1}\ge k(k+1)+2$. Note the following facts: Fact 1: for any two finite sets $X,Y$, we have $$|X|+|Y|\ge |X\Delta Y|.$$ Fact 2: for any two nonempty finite sets $X,Y$, if $|X\Delta Y|=1$, then $|X|+|Y|\ge 3$. When $n=2k$, it follows from Fact 1 that $$|A_i|+|A_{2k+1-i}|\ge |A_i\Delta A_{2k+1-i}|=2k+1-2i,i=1,2,\dots ,k-1.$$ By $|A_k\Delta A_{k+1}|=1$ and Fact 2, we have $|A_k|+|A_{k+1}|\ge 3$. So $$S_{2k}=|A_k|+|A_{k+1}|+\sum _{i=1}^{k-1}(|A_i|+|A_{2k+1-i}|)\ge 3+\sum _{i=1}^{k-1}(2k+1-2i)=k^2+2.$$ Similarly, when $n=2k+1$, we get that $$|A_i|+|A_{2k+2-i}|\ge |A_i\Delta A_{2k+2-i}|=2k+2-2i,i=1,2,\dots ,k-1.$$ Since $|A_k\Delta A_{k+1}|=1$, we have $$(|A_k|+|A_{k+1}|)+|A_{k+2}|\ge 3+1=4,$$ SO $$S_{2k+1}=|A_k|+|A_{k+1}|+|A_{k+2}|+\sum _{i=1}^{k-1}(|A_i|+|A_{2k+2-i}|)$$ $$\ge 4+\sum _{i=1}^{k-1}(2k+2-2i)=k(k+1)+2.$$ In conclusion, the minimum value of $S_{2k}$ is $k^2+2$, the minimum value of $S_{2k+1}$ is $k(k+1)+2$. Equivalently, for any $n\ge 2$, the minimum value of $S_n$ is $\lfloor \frac{n^2}{4}\rfloor +2$.