由满意指数的定义知，ai的满意指数为排列a1,a2, ,an中前i 1项中比ai小的项的个数减去比ai大的项的个数．
由于排列a1,a2, ,an的前k项各不相同，设这k项中有l项比ak小，则有k l 1项比ak大，从而
bk l (k l 1) 2l k 1．
同理，设排列a1
,a2 , ,an 中有l 项比ak 小，则有k l 1项比ak 大，从而bk 2l k 1． 因为 a1,a2, ,ak与a1
,a2 , ,ak 是k个不同数的两个不同排列，且ak ak ， 所以 l l ， 从而 bk b k
． 所以排列a1,a2, ,an和a1
,a2 , ,an 的生成列也不同． 8分 （Ⅲ）证明：设排列a1,a2, ,an的生成列为b1,b2, ,bn，且ak为a1,a2, ,an中从左至右第一个满意指数为负数的项，所以 b1 0,b2 0, ,bk 1 0,bk 1． 9分 进行一次变换 后，排列a1,a2, ,an变换为ak,a1,a2, ak 1,ak 1, ,an，设该排列的生成列为
b1 ,b 2
, ,bn ． 所以 (b1
b2 bn ) (b1 b2 bn) [g(a1 ak) g(a2 ak) g(ak 1 ak)] [g(ak a1) g(ak a2) g(ak ak 1)] 2[g(ak a1) g(ka 2a) gk(a k1
a ) ]2bk 2． 11分 因此，经过一次变换 后，整个排列的各项满意指数之和将至少增加2． 因为ai的满意指数bi i 1，其中i 1,2,3, ,n，
所以，整个排列的各项满意指数之和不超过1 2 3 (n 1) (n 1)n
2
，
即整个排列的各项满意指数之和为有限数，
所以经过有限次变换 后，一定会使各项的满意指数均为非负数． 13分