每日一题[3326]数值污染

设正整数 $n\geqslant 3$，集合 $\left\{a_1,a_2,\cdots,a_n\right\}=\{1,2,\cdots,n\}$，已知有穷数列 $A_0: ~a_1,a_2,\cdots,a_n$ 经过 一次 $M$ 变换后得到数列 $$A_1:~\displaystyle\max\left\{a_1,a_2\right\},\max\left\{a_2,a_3\right\},\cdots,\max\left\{a_{n-1},a_n\right\},\max\left\{a_n,a_1\right\},$$ 其中 $\displaystyle\max\{a,b\}$ 表示 $a,b$ 中的最大者．记数列 $A$ 的所有项之和为 $S(A)$．

1、若 $A_0: ~1,3,2,4$，求 $S\left(A_1\right)$；

2、当 $n=5$ 时，求 $S\left(A_1\right)$ 的最大值；

3、若 $A_1$ 经过一次 $M$ 变换后得到数列 $A_2$，求 $S\left(A_2\right)$ 的最大值．

解析

1、根据题意，$A_1:3,3,4,4$，$S(A_1)=14$．

2、根据题意，$A_1$ 中 $4$ 的个数不超过 $2$，且 $5$ 的个数也不超过 $2$，因此 $$S(A_1)\leqslant 4\cdot 2+5\cdot 2+3,$$ 等号当 $A_0:1,5,2,3,4$ 时可以取得，因此所求最大值为 $21$．

3、根据题意，$A_1$ 中任何一个数至多出现 $2$ 次，且若某个数出现 $2$ 次，则必然相邻，于是 $A_2$ 中任何一个数至多出现 $3$ 次，且若某个数出现不小于 $2$ 次，则必然相邻．因此 $S(A_2)$ 的最大值不超过 $$\underbrace{n,n,n}_{\text{第}~1~\text{组}},\underbrace{n-1,n-1,n-1}_{\text{第}~2~\text{组}},\cdots,\underbrace{n+1-k,n+1-k,n+1-k}_{\text{第}~k~\text{组}},\underbrace{n-k,n-k,n-k}_{\text{第}~k+1~\text{组},\text{取}~r~\text{个}}\cdots\underbrace{1,1,1},$$ 的前 $n$ 项和 $T_n$． 设 $n=3k+r$（$k\in\mathbb N^{\ast}$，$r\in\{0,1,2\}$），则 $$\begin{split} T_n&=3\sum_{i=1}^k(n+1-i)+r(n-k)\\ &=\dfrac 32k(5k+1)+5kr+r^2\\ &=\begin{cases}\dfrac{5 n^2+3 n}6,& n\equiv 0\pmod 3,\\\dfrac{5 n^2+3 n-2}6,& n\equiv 1,2\pmod 3.\end{cases}\end{split}$$ 下面构造具体的例子说明等号能够取到，在之前的数列中每一组的后两个数依次替换为 $1,2,3,\cdots$，直至取够 $n$ 个数为止： $$\underbrace{n,1,2}_{\text{第}~1~\text{组}},\underbrace{n-1,3,4}_{\text{第}~2~\text{组}},\cdots,\underbrace{n+1-k,2k-1,2k}_{\text{第}~k~\text{组}},\cdots.$$