Question

（2012•西城區(qū)二模）若An=

.

a1a2…an

 (ai=0或1，i=1，2，…，n），則稱A_n為0和1的一個n位排列．對于A_n，將排列

.

ana1a2…an-1

記為R¹（A_n）；將排列

.

an-1ana1…an-2

記為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）的相關值，記作t(An，Ri(An))．例如A3=

.

110

，則R1(A3)=

.

011

，t(A3，R1(A3))=-1．若t(An，Ri(An))=-1 (i=1，2，…，n-1)，則稱A_n為最佳排列．
（Ⅰ）寫出所有的最佳排列A₃；
（Ⅱ）證明：不存在最佳排列A₅；
（Ⅲ）若某個A_2k+1（k是正整數(shù)）為最佳排列，求排列A_2k+1中1的個數(shù)．

Answer 1

分析：（Ⅰ）根據(jù)最佳排列的定義可得，最佳排列A₃為

.

110

，

.

101

，

.

100

，

.

011

，

.

010

，

.

001

．
（Ⅱ）由 t(A5，R1(A5))=-1，可得|a₁-a₅|，|a₂-a₁|，|a₃-a₂|，|a₄-a₃|，|a₅-a₄|之中有2個0，3個1，而a₅經(jīng)過奇數(shù)次數(shù)碼改變不能回到自身，所以不存在A₅，使得t(A5，R1(A5))=-1．
（Ⅲ） 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，可得

x+y=2k+1 2xy=2k(k+1).

，解得

x=k y=k+1

或

x=k+1 y=k.

，從而得出結論．

解答：（Ⅰ）解：最佳排列A₃為

.

110

，

.

101

，

.

100

，

.

011

，

.

010

，

.

001

．     …（3分）
（Ⅱ）證明：設A5=

.

a1a2a3a4a5

，則R1(A5)=

.

a5a1a2a3a4

，
因為 t(A5，R1(A5))=-1，所以|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₅，使得t(A5，R1(A5))=-1，
從而不存在最佳排列A₅． …（7分）
（Ⅲ）解：由A2k+1=

.

a1a2…a2k+1

 (ai=0或1，i=1，2，…，2k+1），得R1(A2k+1)=

.

a2k+1a1a2…a2k

，R2(A2k+1)=

.

a2ka2k+1a1a2…a2k-1

，
…R2k-1(A2k+1)=

.

a3a4…a2k+1a1a2

，R2k(A2k+1)=

.

a2a3…a2k+1a1

．
因為 t(A2k+1，Ri(A2k+1))=-1 (i=1，2，…，2k)，
所以 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分）
所以

x+y=2k+1 2xy=2k(k+1).

解得

x=k y=k+1

或

x=k+1 y=k.

，
所以排列A_2k+1中1的個數(shù)是k或k+1．   …（13分）

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