设 $n$ 是正整数，对每一个满足 $0\leqslant a_i\leqslant n(i=1,2,\cdots,n)$ 的整数数列 $A=\{a_0,a_1,\cdots,a_n\}$，定义变换 $T$：数列 $T(A)=\{0,T(a_1),T(a_2),\cdots,T(a_n)\}$，其中 $T(a_i)$ 为数列 $A$ 中位于 $a_i$ 之前的与 $a_i$ 不相等的项的个数（$i=1,2,\cdots,n$），令 $A_{k+1}=T(A_k)(k=0,1,2,\cdots)$．
【难度】
【出处】
无
【标注】
-
已知数列 $A_0$ 分别为 $\{0,1,2,3\}$ 和 $\{0,0,2,0,1,3\}$，写出对应的数列 $A_1,A_2,A_3$；标注答案$\{0,0,2,1,4,5\},\{0,0,2,3,4,5\},\{0,0,2,3,4,5\}$解析由题意，对于 $\{0,1,2,3\}$，有$$\{0,1,2,3\},\{0,1,2,3\},\{0,1,2,3\},$$对于 $\{0,0,2,0,1,3\}$，有$$\{0,0,2,1,4,5\},\{0,0,2,3,4,5\},\{0,0,2,3,4,5\},$$
-
数列 $B=\{0,b_1,b_2,\cdots,b_n\}$，满足 $b_{i-1}\leqslant b_i$，且 $b_i=i$ 或 $b_i=b_{i-1}(i=1,2,\cdots,n)$，求证：$T(B)=B$；标注答案略解析用数学归纳法．
归纳基础 当 $n=1$ 时，若 $b_1=1$，则$$T(b_1)=1=b_1,$$若 $b_1=b_0=0$，则$$T(b_0)=0=b_0,$$所以命题成立；递推证明 设当 $n=p$ 时，$T(b_n)=b_n$ 成立．
当 $n=p+1$ 时，只需证 $T(b_{p+1})=b_{p+1}$；
若 $b_{p+1}=p+1$，则由于$$b_0\leqslant b_1\leqslant\cdots\leqslant b_p\leqslant p,$$于是$$T(b_{p+1})=p+1=b_{p+1};$$若 $b_{p+1}=b_p$，则$$T(b_{p+1})=T(b_p)=b_p=b_{p+1}.$$所以当 $k=p+1$ 时，$T(b_k)=b_k$ 仍然成立．
综上，$T(B)=B$． -
求证：对任意满足已知条件的数列 $A_0$，当 $k\geqslant n$ 时，$A_k=T(A_k)$．标注答案略解析下面用数学归纳法证明：
① $a_p$ 经过 $p$ 次 $T$ 变换后不再发生改变即 $T^{(p+1)}(a_p)=T^{(p)}(a_p)$；
② 经过 $p$ 次 $T$ 变换后$$T^{(p)}(a_{p+1}),T^{(p)}(a_{p+2}),\cdots,T^{(p)}(a_{n})\geqslant T^{(p)}(a_p),$$归纳假设 当 $p=1,2$ 时，容易证明命题成立．递推证明 假设命题对 $1,2,\cdots,p$ 成立，即
① 若 $1\leqslant i\leqslant p,i\in\mathbb N^*$，则当 $k\geqslant i$ 时，$T^{(k)}(a_i)=T^{(i)}(a_i)$；
②\[\begin{split}T(a_2),T(a_3),\cdots,T(a_n)\geqslant T(a_1),\\ \cdots,\\ T^{(p)}(a_{p+1}),T^{(p)}(a_{p+2}),\cdots,T^{(p)}(a_n)\geqslant T^{(p)}(a_p) \end{split}\]则需要证明命题对 $p+1$ 成立：
先证明 ①．
由归纳假设$$T^{(p)}(a_{p+1})\geqslant T^{(p)}(a_p).$$情形一 若 $T^{(p)}(a_{p+1})=T^{(p)}(a_p)$，则显然有$$T^{(p+2)}(a_{p+1})= T^{(p+1)}(a_{p+1})=T^{(p)}(a_{p}).$$情形二 若 $T^{(p)}(a_{p+1})>T^{(p)}(a_p)$，则$$T^{(p+1)}(a_{p+1})=p+1,$$从而$$T^{(p+2)}(a_{p+1})=p+1=T^{(p+1)}(a_{p+1}).$$再证明 ②．情形一 若 $T^{(p)}(a_{p+1})=T^{(p)}(a_p)$，则
由归纳假设，$$T^{(p)}(a_{P+2}),\cdots,T^{(p)}(a_p)=T^{(p)}(a_{p+1}).$$于是$$T^{(p+1)}(a_{p+2}),T^{(p+1)}(a_{p+3}),\cdots,T^{(p+1)}(a_{n})\geqslant T^{(p+1)}(a_{p+1}).$$情形二 若 $T^{(p)}(a_{p+1})>T^{(p)}(a_{p})$，则$$T^{(p+1)}(a_{p+1})=p+1.$$设$$T^{(p+1)}(a_{p-1})=T^{(p)}(a_{p-1})=T^{(p-1)}(a_{p-1})=m,$$则 $m\leqslant p-1$，于是 $T^{(p)}(a_p)=m$ 或 $p$．
对于 $T^{(p-1)}(a_{p+2}),T^{(p-1)}(a_{p+3}),\cdots,T^{(p-1)}(a_{n})$ 中的某项 $T^{(p-1)}(a_i)(p+2\leqslant i\leqslant n,i\in\mathbb N^*)$，由归纳假设，$$T^{(p-1)(a_i)}\geqslant m,$$而$$T^{(p-1)}(a_p)\ne T^{(p-1)}(a_{p+1})$$（否则 $T^{(p+1)}(a_{p+1})=m$，矛盾），
于是$$T^{(p)}(a_i)\geqslant m+1.$$继而前 $p+2$ 个数中，不小于 $m+1$ 的只可能是 $T_{(p)}(a_{p+1}),T^{(p)}(a_p)$，而$$T^{(p)}(a_{p+1})>T^{(p)}(a_{p})\geqslant m,$$从而$$T^{(p+1)}(a_i)\geqslant p+1.$$综上，$T^{(p+1)}(a_{p+2}),T^{(p+1)}(a_{p+3}),\cdots,T^{(p+1)}(a_{n})\geqslant T^{(p+1)}(a_{p+1})$ 成立．
综合 ①②，原命题得证．
题目
问题1
答案1
解析1
备注1
问题2
答案2
解析2
备注2
问题3
答案3
解析3
备注3
