Question

（2012•西城区二模）若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），它们对应位置数字相同的个数减去对应位置数字不同的个数，叫做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是正整数）为最佳排列，求排列A_2k+1中1的个数．

Answer 1

分析：（Ⅰ）根据最佳排列的定义可得，最佳排列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₅经过奇数次数码改变不能回到自身，所以不存在A₅，使得t(A5，R1(A5))=-1．
（Ⅲ） A_2k+1与每个Rⁱ（A_2k+1）有k个对应位置数码相同，有k+1个对应位置数码不同，设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₅的顺序研究数码变化，由上述分析可知有2次数码不发生改变，有3次数码发生了改变．
但是a₅经过奇数次数码改变不能回到自身，所以不存在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个对应位置数码相同，有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分）
所以

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

解得

x=k y=k+1

或

x=k+1 y=k.

，
所以排列A_2k+1中1的个数是k或k+1．   …（13分）

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