查看数据源：590adb2c6cddca0008610f4c
对于数列 $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$；（写出一个即可）；
    标注
    • 方法
      >
      思考方式
      >
      信息迁移
    答案
    $A_1:3,1,2$ 或 $A_1:2,1,3$
    解析
    $A_1:3,1,2$ 或 $A_1:2,1,3$；
  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$；（写出一组即可）；
    标注
    • 方法
      >
      思考方式
      >
      信息迁移
    答案
    $A_3:5,6,7,2,3,4,9,8,1$；$A_4:5,6,7,8,1,2,3,4,9$
    解析
    $A_3:5,6,7,2,3,4,9,8,1$；$A_4:5,6,7,8,1,2,3,4,9$．
  3. 如果数列 $A_0$ 为等差数列：$2015,2014,\cdots,1$，$A_n$ 为等差数列：$1,2,\cdots,2015$，求 $n$ 的最小值．
    标注
    • 题型
      >
      组合数学
      >
      组合极值
    • 方法
      >
      思考方式
      >
      构造半不变量
    答案
    $1008$
    解析
    $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$．
题目 问题1 答案1 解析1 备注1 问题2 答案2 解析2 备注2 问题3 答案3 解析3 备注3
0.150380s