Question

若或1，i=1，2，…，n），則稱A_n為0和1的一個n位排列．對于A_n，將排列記為R¹（A_n）；將排列記為R²（A_n）；依此類推，直至Rⁿ（A_n）=A_n．對于排列A_n和Rⁱ（A_n）（i=1，2，…，n-1），它們對應位置數(shù)字相同的個數(shù)減去對應位置數(shù)字不同的個數(shù)，叫做A_n和Rⁱ（A_n）的相關值，記作．例如，則，．若，則稱A_n為最佳排列．
（Ⅰ）寫出所有的最佳排列A₃；
（Ⅱ）證明：不存在最佳排列A₅；
（Ⅲ）若某個A_2k+1（k是正整數(shù)）為最佳排列，求排列A_2k+1中1的個數(shù)．

Answer 1

【答案】分析：（Ⅰ）根據(jù)最佳排列的定義可得，最佳排列A₃為 ，，，，，．
（Ⅱ）由 ，可得|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2個0，3個1，而a₅經(jīng)過奇數(shù)次數(shù)碼改變不能回到自身，所以不存在A₅，使得．
（Ⅲ） A_2k+1與每個Rⁱ（A_2k+1）有k個對應位置數(shù)碼相同，有k+1個對應位置數(shù)碼不同，設a₁，a₂，…，a_2k，a_2k+1中有x個0，y個1，則S=2xy，可得，解得或，從而得出結論．
解答：（Ⅰ）解：最佳排列A₃為 ，，，，，．     …（3分）
（Ⅱ）證明：設，則，
因為 ，所以|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2個0，3個1．
按a₅→a₁→a₂→a₃→a₄→a₅的順序研究數(shù)碼變化，由上述分析可知有2次數(shù)碼不發(fā)生改變，有3次數(shù)碼發(fā)生了改變．
但是a₅經(jīng)過奇數(shù)次數(shù)碼改變不能回到自身，所以不存在A₅，使得，
從而不存在最佳排列A₅． …（7分）
（Ⅲ）解：由或1，i=1，2，…，2k+1），得，，
…，．
因為 ，
所以 A_2k+1與每個Rⁱ（A_2k+1）有k個對應位置數(shù)碼相同，有k+1個對應位置數(shù)碼不同，
因此有|a₁-a_2k+1|+|a₂-a₁|+…+|a_2k-a_2k-1|+|a_2k+1-a_2k|=k+1，|a₁-a_2k|+|a₂-a_2k+1|+…+|a_2k-a_2k-2|+|a_2k+1-a_2k-1|=k+1，
…，|a₁-a₃|+|a₂-a₄|+…+|a_2k-a₁|+|a_2k+1-a₂|=k+1，|a₁-a₂|+|a₂-a₃|+…+|a_2k-a_2k+1|+|a_2k+1-a₁|=k+1．
以上各式求和得，S=（k+1）×2k．   …（10分）
另一方面，S還可以這樣求和：設a₁，a₂，…，a_2k，a_2k+1中有x個0，y個1，則S=2xy．…（11分）
所以解得或，
所以排列A_2k+1中1的個數(shù)是k或k+1．   …（13分）
點評：本題主要考查排列、組合以及簡單計數(shù)原理的應用，體現(xiàn)了分類討論的數(shù)學思想，屬于難題．