每日一题[1634]逐步调整

设 $\delta=\{a_1,a_2,\cdots,a_n\}$ 为 $\{1,2,\cdots,n\}$ 的一个排列，记 $\displaystyle F(\delta)=\sum \limits_{i=1}^{n}a_ia_{i+1}$，$a_{n+1}=a_1$，求 $\min \limits_{\delta}F(\delta)$．

答案    $T_n=\begin{cases} \dfrac 16n^3+\dfrac 12n^2+\dfrac 56n-1,&2\mid n,\\ \dfrac 16n^3+\dfrac 12n^2+\dfrac 56n-\dfrac 12,&2\nmid n.\end{cases}$

解析    问题等价于圆周上放置 $n$ 个数形成排列 $\delta$，使得相邻数的乘积之和 $F(\delta)$ 最小． 首先，$1$ 必然与 $n$ 相邻，否则设 $\delta$ 中 $x$ 与 $n$ 相邻且 $x\ne 1$，将从 $x$ 到 $1$ 的数反向排列形成 $\delta'$，则 $F(\delta')<F(\delta)$． 接下来，$2$ 必然与 $n$ 相邻，否则设 $\delta$ 中 $x$ 与 $n$ 相邻且 $x\ne 1,2$，将从 $x$ 到 $2$ 的数反向排列形成 $\delta'$，则 $F(\delta')<F(\delta)$． 再接下来，$n-1$ 必然与 $1$ 相邻，否则设 $\delta$ 中 $x$ 与 $1$ 相邻且 $x\ne n,n-1$，将从 $x$ 到 $n-1$ 的数反向排列形成 $\delta'$，则 $F(\delta')<F(\delta)$． 依次操作，直到得到排列（以 $n=8,9$ 为例）：

这样就得到了使得 $F(\delta)$ 最小的排列 $\delta$，称之为最佳排列． 下面计算 $F(\delta)$ 的最小值，记为 $T_n$． 事实上，在 $n$ 个数的最佳排列基础上，将所有数都加 $1$，再在 $2,n+1$ 之间添加 $n+2,1$，然后即可得到 $n+2$ 个数的最佳排列，因此

$$T_{n+2}=\sum_{i=1}^n(a_i+1)(a_{i+1}+1)+(2n+5)=T_n+n^2+4n+5,$$ 设 $$T_{n+2}+A(n+2)^3+B(n+2)^2+C(n+2)=T_n+An^3+Bn^2+Cn,$$ 则 $$\begin{cases} 6A=-1,\\ 12A+4B=-4,\\ 8A+4B+2C=-5,\end{cases}\iff \begin{cases} A=-\dfrac 16,\\ B=-\dfrac 12,\\ C=-\dfrac 56,\end{cases}$$ 又 $T_1=1$，$T_2=4$，于是 $$T_n=\begin{cases} \dfrac 16n^3+\dfrac 12n^2+\dfrac 56n-1,&2\mid n,\\ \dfrac 16n^3+\dfrac 12n^2+\dfrac 56n-\dfrac 12,&2\nmid n.\end{cases}$$