Argentine National Olympiad 2016

The desired minimum is $33\cdot 34=1122$. More generally, for $n=3k+1$ instead of $100$ the answer is $S_{\min }=2(1+\cdots +k)=k(k+1)$. For clarity we state separately a fact used later in a proof of the lower bound $S(\alpha )\ge 2(1+\cdots +k)$ for each permutation $\alpha$ of $1,2,...,3k+1$.

Claim. If $2k$ distinct natural numbers are divided into $k$ pairs $u_j,v_j$ with $u_j<v_j$, $j=1,\dots ,k$, then $v_1+\cdots +v_k\ge 2(1+\cdots +k)$.

The justification is by induction on $k$, with obvious base case $k=1$.

For the inductive step $k-1\to k$ choose the labeling so that $v_k:={\max }_{j=1}^k{v}_j$. Ignore $u_k$ and $v_k$ for the time being, and apply the inductive hypothesis to the remaining $2k-2$ numbers. This gives $v_1+\cdots +v_{k-1}\ge 2(1+\cdots +(k-1))$. So it is enough to prove $v_k\ge 2k$ in order to complete the inductive step. We have $v_k>v_j$ for all $j=1,\dots ,k-1$ by $v_k={\max }_{j=1}^k{v}_j$. In addition observe that $v_k>u_j$ for all $j=1,\dots ,k$. This holds for $j=k$ by hypothesis. Suppose that $v_k<u_j$ for some $j=1,\dots ,k-1$. Then $u_j<v_j$ implies $v_k<v_j$, which contradicts the maximum choice of $v_k$. In summary there are $2k-1$ distinct natural numbers smaller than $v_k$, namely $u_1,\dots ,u_k,v_1,\dots ,v_{k-1}$. Hence $v_k\ge 2k$, completing the induction.

Now let $\alpha =(a_1,a_2,...,a_{3k+1})$ be any permutation of $1,2,...,3k+1$. Divide $a_1,a_2,...,a_{3k}$ into $k$ triples $T_j=\{a_{3j-2},a_{3j-1},a_{3j}\},j=1,\dots ,k$. Let $u_j$ and $v_j$ be respectively the smaller number and the middle number in $T_j$. The $2k$ numbers $u_j,v_j,j=1,\dots ,k$, are distinct. Then the claim above gives $v_1+\cdots +v_k\ge 2(1+\cdots +k)$. Since $v_1,\dots ,v_k$ are marked numbers (in general there are more of them), the sum $S(\alpha )$ of all marked number in $\alpha$ also satisfies $S(\alpha )\ge 2(1+\cdots +k)$.

The equality $S(\alpha )=2(1+\cdots +k)$ is attained for the following permutation of $1,2,...,3k+1$: $3k+1,1,2,2k+1,4,3,2k+2,6,5,2k+3,...,2k-2,2k-3,3k-1,2k,2k-1,3k$.

The marked numbers are precisely $2,4,...,2k$, hence $S(\alpha )=2(1+\cdots +k)$. This completes the proof of $S_{\min }=2(1+\cdots +k)=k(k+1)$.