Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

a) We show that the permutation $\sigma$ of the first $n$ positive integers, defined by $\sigma(i) = (i+1)/2$ for each positive odd $i \le n$, and $\sigma(i) = n - i/2 + 1$ for each positive even $i \le n$, satisfies the required condition.
More precisely, we show that the $\lfloor(n+1)^2/4\rfloor$ sums of the form $\sum_{i=k}^{\ell} \sigma(i)$, where $1 \le k \le \ell \le n$ and $k \equiv \ell \pmod 2$, are pairwise distinct, so $|S(\sigma)| \ge \lfloor(n+1)^2/4\rfloor$.
Let $1 \le k \le \ell \le n$ and $k \equiv \ell \pmod 2$, and notice that $\sigma(i) + \sigma(i+1) = n+1$ for every positive odd $i \le n$, so
$$\sum_{i=k}^{\ell} \sigma(i) = \begin{cases} (\ell-k)(n+1)/2 + \sigma(\ell) & \text{if } k \text{ is odd,} \\ \sigma(k) + (\ell-k)(n+1)/2 & \text{if } k \text{ is even.} \end{cases}$$
Since the absolute value of an integer of the form $\sigma(i) - \sigma(j)$ is less than $n$, the above formula shows that the assignment $(k, \ell) \mapsto \sum_{i=k}^{\ell} \sigma(i)$ is indeed injective on the pairs in question.

b) Let $\sigma$ be a permutation of the first $n$ positive integers, and split $S(\sigma)$ into $S_m(\sigma) = S(\sigma) \cap [mn + 1, mn + n]$, where $m$ runs through the integers; of course, $S_m(\sigma)$ is empty if $m$ is negative or $m > (n-1)/2$, and $|S_0(\sigma)| \ge n$.
Leaving aside the trivial cases $n=1$ and $n=2$, we assume $n \ge 3$ and prove that
$$|S_m(\sigma)| + |S_{m-1}(\sigma)| > \sqrt{2n}, \quad (*)$$
for every non-negative integer $m \le (n+1)/4$. The conclusion then follows by summing over this range:
$$|S(\sigma)| \ge \frac{1}{2} \sum_{m=0}^{\lfloor(n+1)/4\rfloor} (|S_m(\sigma)| + |S_{m-1}(\sigma)|) > \frac{1}{2} \left\lfloor \frac{n+5}{4} \right\rfloor \sqrt{2n} > \frac{n\sqrt{n}}{4\sqrt{2}}.$$
To prove (*), fix a non-negative integer $m \le (n+1)/4$. We will show that the Minkowski difference $S_m(\sigma) - (S_m(\sigma) \cup S_{m-1}(\sigma))$ contains every positive integer less than or equal to $n$; alternatively, but equivalently, that it contains every $\sigma(k)$. Then so does $(S_m(\sigma) \cup S_{m-1}(\sigma)) - (S_m(\sigma) \cup S_{m-1}(\sigma))$, so $|S_m(\sigma)| + |S_{m-1}(\sigma)| = |S_m(\sigma) \cup S_{m-1}(\sigma)| > \sqrt{2n}$, for if $X$ is a finite set of numbers such that $\{1, 2, \dots, n\} \subseteq X - X$, then $|X| \cdot (|X| - 1) + 1 \ge |X - X| \ge 2n + 1$, so $|X| \ge (1 + \sqrt{8n+1})/2 > \sqrt{2n}$.
Finally, we show that every $\sigma(k)$ is a member of $S_m(\sigma) - (S_m(\sigma) \cup S_{m-1}(\sigma))$. To this end, fix a positive integer $k \le n$, and notice that at least one of the sums $\sum_{i=1}^k \sigma(i)$, $\sum_{i=k}^n \sigma(i)$ exceeds $n(n+1)/4 \ge mn$. Let $\sum_{i=k}^n \sigma(i) > mn$ — the other case is easily dealt with dually —, and consider the smallest integer $\ell \ge k$ such that $\sum_{i=k}^{\ell} \sigma(i) > mn$. With reference to this minimality, it is readily checked that the sums $\sum_{i=k}^{\ell} \sigma(i)$ and $\sum_{i=k+1}^{\ell} \sigma(i)$ belong to $S_m(\sigma)$ and $S_m(\sigma) \cup S_{m-1}(\sigma)$, respectively, so $\sigma(k)$ is indeed a member of $S_m(\sigma) - (S_m(\sigma) \cup S_{m-1}(\sigma))$.