004. Multiplying Adjacent Elements in a Permutation

Given a permutation $(a_1, a_2, \cdots, a_n)$ of $\{ 1, 2, \cdots, n \}$, maximize $a_1 a_2 + a_2 a_3 + \cdots + a_{n-1} a_n + a_n a_1$.

---

Let $M_n = \max (a_1 a_2 + a_2 a_3 + \cdots + a_{n-1} a_n + a_n a_1)$. Note that $M_n$ of a permutation is always the same as the ones of its cyclic permutations. Observe the amount of change updating $\{ 1, 2, \cdots, n - 1 \}$ to $\{ 1, 2, \cdots, n \}$. When $n$ is inserted between $a_k$ and $a_{k + 1}$, the amount of change is $$\begin{aligned} n a_k + n a_{k + 1} - a_k a_{k + 1} &= n a_k + n a_{k + 1} - a_k a_{k + 1} + n^2 - n^2 \\ &= n^2 - \{ n^2 - n (a_k + a_{k + 1}) + a_k a_{k + 1} \} \\ &= n^2 - (n - a_k) (n - a_{k + 1}) \\ &\leq n^2 - \{n - (n - 1)\} \{n - (n - 2)\} = n^2 - 2 \end{aligned}$$

where $1 \leq k \leq n - 1$. Although $k + 1$ must be $1$ when $k = n - 1$, the above inequality is always valid since the permutation can be cyclic keeping $M_{n - 1}$. So, the maximum amount of change is $n^2 - 2$, which means $M_n - M_{n - 1} = n^2 - 2$. Also, this only happens when $n$ is inserted between $n - 1$ and $n - 2$ in a situation where $n - 1$ and $n - 2$ are adjacent. From $M_2 = a_1 a_2 + a_2 a_1 = 4$, $$\begin{aligned} M_3 &= M_2 + 3^2 - 2 \\ M_4 &= M_3 + 4^2 - 2 \\ &\qquad \vdots \\ M_n &= M_{n - 1} + n^2 - 2 \\\\ \implies M_n &= M_2 + (3^2 - 2) + (4^2 - 2) + \cdots + (n^2 - 2) \\ &= 4 + (1^2 + 2^2 + \cdots + n^2) - (1^2 + 2^2) - 2(n - 2) \\ &= (1^2 + 2^2 + \cdots + n^2) -2n + 3 \\ &= \frac{n(n + 1)(2n + 1)}{6} - 2n + 3 \qquad (n \geq 2) \end{aligned}$$

Enumerating $M_n$ starting from $n = 3$, $$\begin{aligned} M_3 &\Longleftarrow 1, 3, 2 \\ M_4 &\Longleftarrow 1, 3, 4, 2 \\ M_5 &\Longleftarrow 1, 3, 5, 4, 2 \\ &\qquad \vdots \\ M_n &= \begin{cases} 1, 3, \cdots, n - 3, n - 1, n, n - 2, \cdots, 4, 2 \qquad (n \text{ is even}) \\\\ 1, 3, \cdots, n - 2, n, n - 1, n - 3, \cdots, 4, 2 \qquad (n \text{ is odd}) \end{cases} \end{aligned}$$