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），它們對應位置數字相同的個數減去對應位置數字不同的個數，叫做A_n和Rⁱ（A_n）的相關值，記作．例如，則，．若，則稱A_n為最佳排列．
（Ⅰ）寫出所有的最佳排列A₃；
（Ⅱ）證明：不存在最佳排列A₅；
（Ⅲ）若某個A_2k+1（k是正整數）為最佳排列，求排列A_2k+1中1的個數．

Answer 1

（Ⅰ）解：最佳排列A₃為 ，，，，，． …（3分）
（Ⅱ）證明：設，則，
因為 ，所以|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2個0，3個1．
按a₅→a₁→a₂→a₃→a₄→a₅的順序研究數碼變化，由上述分析可知有2次數碼不發生改變，有3次數碼發生了改變．
但是a₅經過奇數次數碼改變不能回到自身，所以不存在A₅，使得，
從而不存在最佳排列A₅． …（7分）
（Ⅲ）解：由或1，i=1，2，…，2k+1），得，，
…，．
因為 ，
所以 A_2k+1與每個Rⁱ（A_2k+1）有k個對應位置數碼相同，有k+1個對應位置數碼不同，
因此有|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的個數是k或k+1． …（13分）
分析：（Ⅰ）根據最佳排列的定義可得，最佳排列A₃為 ，，，，，．
（Ⅱ）由 ，可得|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2個0，3個1，而a₅經過奇數次數碼改變不能回到自身，所以不存在A₅，使得．
（Ⅲ） A_2k+1與每個Rⁱ（A_2k+1）有k個對應位置數碼相同，有k+1個對應位置數碼不同，設a₁，a₂，…，a_2k，a_2k+1中有x個0，y個1，則S=2xy，可得，解得或，從而得出結論．
點評：本題主要考查排列、組合以及簡單計數原理的應用，體現了分類討論的數學思想，屬于難題．