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\}, \quad i = 1, 2, \dots, k; \quad A_{k+1} = \{k, k+1\};$$
$$A_{k+j} = \{k+1, k+2, \dots, k+j-1\}, \quad 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, \quad 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, \quad i=1, 2, \dots, k-1.$$
Since $|A_k \Delta A_{k+1}| = 1$, we have
$$(|A_k| + |A_{k+1}|) + |A_{k+2}| \geq 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}|)$$
$$\geq 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 \geq 2$, the minimum value of $S_n$ is $\left\lfloor \frac{n^2}{4} \right\rfloor + 2$.