每日一题[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}\]

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论