设 x1,x2,…,xn 是 1,2,…,n 的任一排列，求 ∣x1-1∣+∣x2-2∣+…+∣xn-n∣ 的最大值

luyuanhong

这是网友 ringdove 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

若n为正整数，设x1,x2,.....xn是1,2,....n的任一排列

(如1，2，3的排列有1，2，3；3，2，1；1，3，2；2，3，1；2，1，3；1，3，2共6种），

求∣x1-1∣+∣x2-2∣+.....+∣xn-n∣的最大值。（请给出详细解答过程）

angel_phoenix99

倒序应该最大，证明过程不一定对
n是奇数，最大值(n^2-1)/2
n是偶数，最大值(n-2)^2

大概思路，起始点是完全匹配，最小和值为0

针对第一个数字1，很显然交换到n的位置，能产生2(n-1)，交换到2的位置产生2，按2的等差递增
再处理2，同样交换到n-1的位置会最大，和值2(n-3)

angel_phoenix99

偶数的和值不对

angel_phoenix99

应该最大，证明过程不一定对
n是奇数，最大值(n^2-1)/2
n是偶数，最大值(n)^2/2

大概思路，起始点是完全匹配，最小和值为0

针对第一个数字1，很显然交换到n的位置，能产生2(n-1)，交换到2的位置产生2，按2的等差递增
再处理2，同样交换到n-1的位置会最大，和值2(n-3)

luyuanhong

luyuanhong

问题可以这样来看：

    先让 x1,x2,…,xn 任意取一种排列，如果 x1,x2,…,xn 不是全部逆序的话，

则其中至少有一对 xi,xj 是顺序的。将这一对顺序的  xi,xj  交换位置，变成

逆序，交换后总和只会增大，不会减小。然后再看其中有没有顺序的，如果有，

则再交换一下，将顺序变成逆序，交换后总和又是只会增大，不会减小。……，

就这样，一次又一次地将排列中的顺序变为逆序，最后总是可以将 x1,x2,…,xn

变成全部逆序排列，也就是有 xi=n+1-i ，i=1,2,…,n 。

    因为从任何一种排列出发，都可以通过一次又一次的交换，达到全部逆序排列，

在此过程中，总和只会增大，不会减小，所以，全部逆序排列时的总和，必定大于

等于其他任何一种排列时的总和。也就是说，x1,x2,…,xn 全部逆序排列时取到的

总和，必定是所有各种排列的总和中的最大值。