, 2022

a) Place the elements of $p$ along the real axis. Then $S_p$ equals the length of the "walk", starting from $a_1$, then reaching $a_2$, then reaching $a_3$ and so on until we end at $a_{12}$. In such a walk, the segments:

$1$-$2$ and $11$-$12$ appear at most twice (before and after $1$; before and after $12$);

$2$-$3$ and $10$-$11$ appear at most $4$ times (before and after $1$, $2$, $11$, and $12$);

$3$-$4$ and $9$-$10$ appear at most $6$ times (before and after $1$, $2$, $3$, $10$, $11$, and $12$);

$4$-$5$ and $8$-$9$ appear at most $8$ times (before and after $1$, $2$, $3$, $4$, $9$, $10$, $11$, and $12$);

$5$-$6$ and $7$-$8$ appear at most $10$ times (before and after $1$, $2$, $3$, $4$, $5$, $8$, $9$, $10$, $11$, $12$);

$6$-$7$ may appear in all $11$ paths $a_i-a_{i+1}$.

Therefore, $S_p \le 2(2+4+6+8+10)+11 = 2 \cdot 30+11 = 71$. Furthermore $S_p = 71$ iff all the inequalities above become equalities. This is possible only if $\{a_1, a_{12}\} = \{6, 7\}$ (2 cases). For the case $a_1 = 6$, $(a_2, a_4, \dots, a_{10})$ must be a permutation of $\{8, 9, \dots, 12\}$ ($5!$ cases) and $(a_3, a_5, \dots, a_{11})$ must be a permutation of $\{1, 2, \dots, 5\}$ ($5!$ cases), while in the case $a_1 = 7$ it is vice versa. Therefore, the total number of permutations with $S_p = 71$ is $2 \cdot 5! \cdot 5! = 28800$.

b) In order for $p$ to be an optimistic permutation, the number $1$ should be at one of the end positions. Then, the number $2$ should be at one of the end positions of the remaining $p$-sub-permutation of $\{2, 3, \dots, 12\}$, $3$ should be at one of the end positions of the remaining $p$-sub-permutation of $\{3, \dots, 12\}$ and so on. It is easy to check that all such permutations are indeed optimistic. Therefore, their number is $2^{11} = 2048$.

c) Let $p$ be an optimistic permutation and $k \in \{1, 2, \dots, 12\}$ be the position of $12$ in it (i.e., $a_k = 12$). Then, it is trivial to check that $a_i > a_{i-1}$, for all $i = 2, \dots, k$, while $a_j > a_{j+1}$, for all $j = k, \dots, 11$. Thus, $S_p = 12 - a_1 + 12 - a_{12} \le 2 \cdot 12 - 1 - 2 = 21$. Equality is achieved iff $\{a_1, a_{12}\} = \{1, 2\}$. According to b), the total number of such permutations is $2^{11}/2 = 2^{10} = 1024$.