Question

12．若A_n=$\overline{{a_1}{a_2}…{a_n}}$（a_i=0或1，i=1，2，…n），則稱A_n為0和1的一個(gè)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），它們對應(yīng)位置數(shù)字相同的個(gè)數(shù)減去對應(yīng)位置數(shù)字不同的個(gè)數(shù)，叫做A_n和Rⁱ（A_n）的相關(guā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為最佳排列
（Ⅱ）當(dāng)n=3，寫出所有的n位排列，并求出所有的最佳排列A₃；
（Ⅲ）證明：當(dāng)n=5，不存在最佳排列A₅．

Answer 1

分析 （Ⅰ）根據(jù)R¹（A_n）和Rⁿ（A_n）的定義，結(jié)合已知中A₃=$\overline{110}$，可得答案；
（Ⅱ）列舉出所有的3位排列，根據(jù)最佳排列的定義可得，最佳排列A₃；
（Ⅲ）由 t（A₅，R¹（A₅））=-1，可得|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2個(gè)0，3個(gè)1，而a₅經(jīng)過奇數(shù)次數(shù)碼改變不能回到自身，所以不存在A₅，使得t（A₅，R¹（A₅））=-1．

解答 解：（Ⅰ）當(dāng)A₃=$\overline{110}$，R¹（A₃）=$\overline{011}$，
t（A₃，R¹（A₃））=1-2=-1，
故答案為：$\overline{011}$，-1…（4分）
（Ⅱ）當(dāng)n=3時(shí)，所有的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分）
證明：（Ⅲ）設(shè)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}}$，
因?yàn)?t（A₅，R¹（A₅））=-1，所以|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2個(gè)0，3個(gè)1．
按a₅→a₁→a₂→a₃→a₄→a₅的順序研究數(shù)碼變化，由上述分析可知有2次數(shù)碼不發(fā)生改變，
有3次數(shù)碼發(fā)生了改變．
但是a₅經(jīng)過奇數(shù)次數(shù)碼改變不能回到自身，所以不存在A₅，使得t（A₅，R¹（A₅））=-1，
從而不存在最佳排列A₅． …（12分）

點(diǎn)評 本題主要考查排列、組合以及簡單計(jì)數(shù)原理的應(yīng)用，體現(xiàn)了分類討論的數(shù)學(xué)思想，屬于難題