, 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 + \dots + 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 + \dots + 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 + \dots + v_k \ge 2(1 + \dots + 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 + \dots + v_{k-1} \ge 2(1 + \dots + (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 + \dots + v_k \ge 2(1 + \dots + 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 + \dots + k)$.

The equality $S(\alpha) = 2(1 + \dots + 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 + \dots + k)$. This completes the proof of $S_{\min} = 2(1 + \dots + k) = k(k+1)$.