- Find the permutation $(a_1,\cdots, a_n)$ of $\{1,\cdots, n\}$ that maximizes the value $\sum_{i=1}^n a_i a_{i+1},$ where $a_{n+1} = a_1.$
- Find the permutation $(a_1,\cdots, a_n)$ of $\{1,\cdots, n\}$ that minimizes the value $\sum_{i=1}^n a_i a_{i+1},$ where $a_{n+1} = a_1.$
Let $S(A) = \sum_{i=1}^n a_i a_{i+1}$ for a permutation $A = (a_1,\cdots, a_n)$ of $\{1,\cdots, n\}$.
To find the two permutations, I think it would be useful to consider the effect of swapping elements $i$ and $j, 1\leq i < j \leq n$ on the result of the sum. Assume $A_{max}$ maximizes $S(A_{max})$. Note that since the function $S$ on permutations is invariant under cyclic shifts, we may assume WLOG that $a_1 = 1$. Then we need to figure out what $a_2$ can be. Note that the difference $A_{max} - A'$, where $A'$ results from switching positions $i$ and $j$ in $A_{max}$ equals $a_{i-1} a_i + a_i a_{i+1} + a_{j-1} a_{j} + a_j a_{j+1} - (a_{i-1} a_j + a_j a_{i+1} + a_{j-1} a_i + a_i a_{j+1})$, where indices are interpreted modulo $n$ (e.g. $a_{-1} = a_n, a_{n+1} = a_1,$ etc.). One could factor the change as $-(a_i - a_j) (a_{j+1} - a_{i-1} - (a_{i+1} - a_{j-1})),$ but I'm not sure how to proceed further.
