每日一题[123]论证与构造

今天的题目是2015年北京市海淀区高三二模理科数学压轴题：

对于数列$A:a_1,a_2,\cdots,a_n$，经过变换$T$：交换$A$中某相邻两段的位置（数列$A$中的一项或连续的几项称为一段），得到数列$T(A)$．例如，数列$A$：

$$a_1,\cdots,a_i,\underbrace{a_{i+1},\cdots,a_{i+p}}_M,\underbrace{a_{i+p+1},\cdots,a_{i+p+q}}_N,a_{i+p+q+1},\cdots,a_n$$ 经交换$M$、$N$两段位置，变换为数列$T(A)$： $$a_1,\cdots,a_i,\underbrace{a_{i+p+1},\cdots,a_{i+p+q}}_N,\underbrace{a_{i+1},\cdots,a_{i+p}}_M,a_{i+p+q+1},\cdots,a_n,$$ 其中$p\geqslant 1$，$q\geqslant 1$．设$A_0$是有穷数列，令$A_{k+1}=T\left(A_k\right)$（$k=0,1,2,\cdots$）．

（1）如果数列$A_0$为$3,2,1$，且$A_2$为$1,2,3$，写出数列$A_1$；（写出一个即可）；

（2）如果数列

$$\begin{split}A_0:9,8,7,6,5,4,3,2,1,\\A_1:5,4,9,8,7,6,3,2,1,\\A_2:5,6,3,4,9,8,7,2,1,\\A_5:1,2,3,4,5,6,7,8,9.\end{split}$$ 写出数列$A_3$，$A_4$；（写出一组即可）；

（3）如果数列$A_0$为等差数列：$2015,2014,\cdots,1$，$A_n$为等差数列：$1,2,\cdots,2015$，求$n$的最小值．

---

直接给出第3小题的解答．

$n$的最小值为$1008$．

先给出$n=1008$的例子．\

$$\begin{split}A_0&:\underbrace{2015,2014,\cdots,1010,1009},\underbrace{1008,1007},1006,1005,\cdots,2,1\\A_1&:1008,\underbrace{1007,2015,2014,\cdots,1011,1010},\underbrace{1009,1006},1005,1004,\cdots,2,1\\A_2&:1008,1009,\underbrace{1006,1007,2015,2014,\cdots},\underbrace{1010,1005},1004,\cdots,2,1\\A_3&:1008,1009,1010,\underbrace{1005,1006,1007,2015,2014,\cdots},\underbrace{1011,1004},1003,\cdots,2,1\\\cdots\\A_{1006}&:1008,\cdots,2013,\underbrace{2,3,\cdots,1007,2015},\underbrace{2014,1};\\A_{1007}&:\underbrace{1008,\cdots,2014},\underbrace{1,\cdots,1007},2015\\A_{1008}&:1,\cdots,1007,1008,\cdots,2014,2015\end{split}$$ 注意两个逐步变长的片段，一个从$1008$逐步增长为$1008,1009,\cdots,2014$，另外一个从$1007$逐步变长为$1,2,\cdots,1007$．

接下来给出$n\geqslant 1008$的证明．

数列$A_0:2015,2014,\cdots,1$中相邻的数有$2014$对，分别为

$$(2015,2014),(2014,2013),\cdots,(2,1),$$ 在两个相邻的数构成的数对中，定义前面的数比后面的数大的数对为“逆序”，前面的数比后面的数小的数对为“顺序”，如数列$A_0$中有$2014$个逆序，而$A_n$中有$2014$个顺序．

下面证明“$T$变换”有以下两个特点：

①对所有数对均为逆序（或所有数对均为顺序）的数列，必然转化$1$个逆序（或顺序）为顺序（或逆序）；

②对其他既包含顺序又包含逆序的数列，至多转化$2$个顺序到逆序（或逆序到顺序）．

假设“T变换”前后的数列分别为

$$\begin{split}a,\cdots,b,\underbrace{c,\cdots,d},\underbrace{e\cdots,f},g\cdots,h\\a,\cdots,b,\underbrace{e,\cdots,f},\underbrace{c\cdots,d},g\cdots,h\end{split}$$ 注意到 $$(b-c)+(d-e)+(f-g)=(b-e)+(f-c)+(d-g)$$ 于是前后顺序（或逆序）数的差必然小于$3$；特别的，若 $$b>c>d>e>f>g,$$ 则“$T$变换”后只有$(f,c)$变为顺序．因此命题①②均得证．
于是对于包含$2015$个数的数列$A_0$，至少需要$1008$次“$T$变换”才能将所有逆序全部转化为顺序．

综上所述，$n$的最小值为$1008$．