Question

12．若A_n=$\overline{{a_1}{a_2}…{a_n}}$（a_i=0或1，i=1，2，…n），则称A_n为0和1的一个n位排列，对于A_n，将排列$\overline{{a_n}{a_1}{a_2}…{a_{n-1}}}$记为R¹（A_n）；将排列$\overline{{a_{n-1}}{a_n}{a_1}{a_2}…{a_{n-2}}}$记为R²（A_n）；依此类推，直至Rⁿ（A_n）=A_n．对于排列A_n和Rⁱ（A_n）（i=1，2，…n-1），它们对应位置数字相同的个数减去对应位置数字不同的个数，叫做A_n和Rⁱ（A_n）的相关值，记作t（A_n，Rⁱ（A_n）），
（Ⅰ）例如A₃=$\overline{110}$，则R¹（A₃）=$\overline{011}$，t（A₃，R¹（A₃））=-1；
若t（A_n，Rⁱ（A_n））=-1（i=1，2，…n-1），则称A_n为最佳排列
（Ⅱ）当n=3，写出所有的n位排列，并求出所有的最佳排列A₃；
（Ⅲ）证明：当n=5，不存在最佳排列A₅．

Answer 1

分析 （Ⅰ）根据R¹（A_n）和Rⁿ（A_n）的定义，结合已知中A₃=$\overline{110}$，可得答案；
（Ⅱ）列举出所有的3位排列，根据最佳排列的定义可得，最佳排列A₃；
（Ⅲ）由 t（A₅，R¹（A₅））=-1，可得|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2个0，3个1，而a₅经过奇数次数码改变不能回到自身，所以不存在A₅，使得t（A₅，R¹（A₅））=-1．

解答 解：（Ⅰ）当A₃=$\overline{110}$，R¹（A₃）=$\overline{011}$，
t（A₃，R¹（A₃））=1-2=-1，
故答案为：$\overline{011}$，-1…（4分）
（Ⅱ）当n=3时，所有的3位排列有：
$\overline{000}$，$\overrightarrow{001}$，$\overrightarrow{010}$，$\overrightarrow{100}$，$\overrightarrow{011}$，$\overrightarrow{101}$，$\overrightarrow{110}$，$\overrightarrow{111}$
最佳排列A₃为 $\overrightarrow{001}$，$\overrightarrow{010}$，$\overrightarrow{100}$，$\overrightarrow{011}$，$\overrightarrow{101}$，$\overrightarrow{110}$ …（8分）
证明：（Ⅲ）设A₅=$\overline{{a}_{1}{a}_{2}{a}_{3}{a}_{4}{a}_{5}}$，则R¹（A₅）=$\overline{{{a}_{5}a}_{1}{a}_{2}{a}_{3}{a}_{4}}$，
因为 t（A₅，R¹（A₅））=-1，所以|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2个0，3个1．
按a₅→a₁→a₂→a₃→a₄→a₅的顺序研究数码变化，由上述分析可知有2次数码不发生改变，
有3次数码发生了改变．
但是a₅经过奇数次数码改变不能回到自身，所以不存在A₅，使得t（A₅，R¹（A₅））=-1，
从而不存在最佳排列A₅． …（12分）

点评 本题主要考查排列、组合以及简单计数原理的应用，体现了分类讨论的数学思想，属于难题