对于每项均是正整数的数列
A:
a1,
a2,
⋯,
an,定义变换
T1 将数列
A 变换成数列
T1(A):
n,
a1−1,
a2−1,
⋯,
an−1. 对于每项均是非负整数的数列
B:
b1,
b2,
⋯,
bm,定义变换
T2 将数列
B 各项从大到小排列,然后去掉所有为零的项,得到数列
T2(B);又定义
S(B)=2(b1+2b2+⋯+mbm)+b12+b22+⋯+bm2. 设
A0 是每项均为正整数的有穷数列,令
Ak+1=T2(T1(Ak))(
k=0,
1,
2,
⋯).
(1) 如果数列
A0 为
5,
3,
2,写出数列
A1,
A2;
(2) 对于每项均是正整数的有穷数列
A,证明
S(T1(A))=S(A);
(3) 证明:对于任意给定的每项均为正整数的有穷数列
A0,存在正整数
K,当
k⩾K 时,
S(Ak+1)=S(Ak).
\begin{solution}
\begin{enumerate}
\item
T1(A0)=(3,4,2,1),按从大到小排列并去掉零项后,
A1=(4,3,2,1). 再有
T1(A1)=(4,3,2,1,0),所以
A2=(4,3,2,1).
\item 设
A=(a1,a2,…,an),则
T1(A)=(n,a1−1,a2−1,…,an−1). 直接展开
S 得
S(T1(A))=2[n+∑i=1n(i+1)(ai−1)]+n2+∑i=1n(ai−1)2.
展开后,
ai 的一次项为
2(i+1)ai−2ai=2iai,平方项为
∑i=1nai2,常数项为
2n−2∑i=1n(i+1)+n2+n.
又
∑i=1n(i+1)=2n(n+3),所以该常数项等于
2n−n(n+3)+n2+n=0. 因此
S(T1(A))=2∑i=1niai+∑i=1nai2=S(A).
\item 对任意非负整数数列
B=(b1,…,bm),交换相邻的逆序项
bi<bi+1 后,平方和不变,而加权和的变化为
ibi+(i+1)bi+1−(ibi+1+(i+1)bi)=bi+1−bi>0
这里左边是交换前的加权和,右边是交换后的加权和,所以每次交换都会使
S 严格减小;将所有逆序项交换后,数列按从大到小排列,故排序不会增加
S. 排序后所有零项位于末尾,去掉零项也不改变
S,从而
S(T2(B))⩽S(B). 结合第(2)问,对
Ak 有
S(Ak+1)=S(T2(T1(Ak)))⩽S(T1(Ak))=S(Ak)
由于每个
Ak 都是非负整数项数列去掉零项后得到的正整数项数列,故
S(Ak) 是非负整数. 单调不增的非负整数列不可能无限次严格下降,因此从某个正整数
K 起不再下降,即对所有
k⩾K,都有
S(Ak+1)=S(Ak).
\end{enumerate}
\end{solution}