Question

（2013•石景山區二模）已知集合S_n={（x₁，x₂，…，x_n）|x₁，x₂，…，x_n是正整數1，2，3，…，n的一個排列}（n≥2），函數g(x)=

1， x＞0 -1，  x＜0.

對于（a₁，a₂，…a_n）∈S_n，定義：b_i=g（a_i-a₁）+g（a_i-a₂）+…+g（a_i-a_i-1），i∈{2，3，…，n}，b₁=0，稱b_i為a_i的滿意指數．排列b₁，b₂，…，b_n為排列a₁，a₂，…，a_n的生成列；排列a₁，a₂，…，a_n為排列b₁，b₂，…，b_n的母列．
（Ⅰ）當n=6時，寫出排列3，5，1，4，6，2的生成列及排列0，-1，2，-3，4，3的母列；
（Ⅱ）證明：若a₁，a₂，…，a_n和a′₁，a′₂，…，a′_n為S_n中兩個不同排列，則它們的生成列也不同；
（Ⅲ）對于S_n中的排列a₁，a₂，…，a_n，定義變換τ：將排列a₁，a₂，…，a_n從左至右第一個滿意指數為負數的項調至首項，其它各項順序不變，得到一個新的排列．證明：一定可以經過有限次變換τ將排列a₁，a₂，…，a_n變換為各項滿意指數均為非負數的排列．

Answer 1

分析：（Ⅰ）由b_i=g（a_i-a₁）+g（a_i-a₂）+…+g（a_i-a_i-1），g（x）=

1， x＞0 -1，  x＜0

及“生成列”與“母列”的定義可求得當n=6時排列3，5，1，4，6，2的生成列及排列0，-1，2，-3，4，3的母列；
（Ⅱ）設a₁，a₂，…，a_n的生成列是b₁，b₂，…，b_n；a′₁，a′₂，…，a′_n的生成列是與b′₁，b′₂，…，b′_n，從右往左數，設排列a₁，a₂，…，a_n與a′₁，a′₂，…，a′_n第一個不同的項為a_k與a′_k，由滿意指數的定義可知a_i的滿意指數，從而可證得且a_k≠a′_k，于是可得排列a₁，a₂，…，a_n和a′₁，a′₂，…，a′_n的生成列也不同．
（Ⅲ）設排列a₁，a₂，…，a_n的生成列為b₁，b₂，…，b_n，且a_k為a₁，a₂，…，a_n中從左至右第一個滿意指數為負數的項，⇒b₁≥0，b₂≥0，…，b_k-1≥0，b_k≤-1，經過一次變換τ后，整個排列的各項滿意指數之和將至少增加2，利用a_i的滿意指數b_i≤i-1，可知整個排列的各項滿意指數之和不超過1+2+3+…+（n-1）=

n(n-1)

2

，從而可使結論得證．

解答：（Ⅰ）解：當n=6時，排列3，5，1，4，6，2的生成列為0，1，-2，1，4，-3；
排列0，-1，2，-3，4，3的母列為3，2，4，1，6，5．
（Ⅱ）證明：設a₁，a₂，…，a_n的生成列是b₁，b₂，…，b_n；a′₁，a′₂，…，a′_n的生成列是與b′₁，b′₂，…，b′_n，
從右往左數，設排列a₁，a₂，…，a_n與a′₁，a′₂，…，a′_n第一個不同的項為a_k與a′_k，即：a_n=a′_n，a_n-1=a′_n-1，…，a_k+1=a′_k+1，a_k≠a′_k．
顯然 b_n=b′_n，b_n-1=b′_n-1，…，b_k+1=b′_k+1，下面證明：b_k≠b′_k．
由滿意指數的定義知，a_i的滿意指數為排列a₁，a₂，…，a_n中前i-1項中比a_i小的項的個數減去比a_i大的項的個數．
由于排列a₁，a₂，…，a_n的前k項各不相同，設這k項中有l項比a_k小，則有k-l-1項比a_k大，從而b_k=l-（k-l-1）=2l-k+1．
同理，設排列a′₁，a′₂，…，a′_n中有l′項比a′_k小，則有k-l′-1項比a′_k大，從而b′_k=2l′-k+1．
因為 a₁，a₂，…，a_k與a′₁，a′₂，…，a′_k是k個不同數的兩個不同排列，且a_k≠a′_k，
所以 l≠l′，從而 b_k≠b′_k．
所以排列a₁，a₂，…，a_n和a′₁，a′₂，…，a′_n的生成列也不同．
（Ⅲ）證明：設排列a₁，a₂，…，a_n的生成列為b₁，b₂，…，b_n，且a_k為a₁，a₂，…，a_n中從左至右第一個滿意指數為負數的項，所以 b₁≥0，b₂≥0，…，b_k-1≥0，b_k≤-1．
進行一次變換τ后，排列a₁，a₂，…，a_n變換為a_k，a₁，a₂，…a_k-1，a_k+1，…，a_n，設該排列的生成列為b′₁，b′₂，…，b′_n．
所以 （b′₁，b′₂，…，b′_n）-（b₁+b₂+…+b_n）=[g（a₁-a_k）+g（a₂-a_k）+…+g（a_k-1-a_k）]-[g（a_k-a₁）+g（a_k-a₂）+…+g（a_k-a_k-1）]=-2[g（a_k-a₁）+g（a_k-a₂）+…+g（a_k-a_k-1）]=-2b_k≥2．
因此，經過一次變換τ后，整個排列的各項滿意指數之和將至少增加2．
因為a_i的滿意指數b_i≤i-1，其中i=1，2，3，…，n，
所以，整個排列的各項滿意指數之和不超過1+2+3+…+（n-1）=

n(n-1)

2

，
即整個排列的各項滿意指數之和為有限數，
所以經過有限次變換τ后，一定會使各項的滿意指數均為非負數．

點評：本題等差數列與等比數列的綜合，理解題意及“生成列”、“母列”、“滿意指數”及運算法則是關鍵，也是難點，屬于難題．