两列数,由大到小分别为a1,a2,a3,……an以及b1,b2,b3,……bn的顺序和≥乱序和≥倒序和,怎样证明

Question

两列数,由大到小分别为a1,a2,a3,……an以及b1,b2,b3,……bn的顺序和≥乱序和≥倒序和,怎样证明

Answer 1

证明：设a1≤a2≤……an,b1≤b2……bn,c1,c2,……,cn是b1,b2,……bn的任意排列,因为b1,b2,……bn的全排列只有n!个,所以 S=a1c1+a2c2+……+ancn ① 的不同的值也只有有限个.其中必有最大值和最小值 考虑①式,若c1≠b1,则有某ck=b1（k>1),c1>ck.将①中c1,ck对换,得S’=a1ck+...+akc1+...+ancn.②-①得S'-s=a1ck+akc1-a1c1-akck=(ak-a1)(c1-ck)≥0这说明将①中的第一项调换为a1b1后,和式不减小. 若c1=b1,则转而考察c2,并进行类似讨论. 类似的,可以证明.将①中的第一项转化为a1b1,第二项换为a2b2后,和式不减小. 如此下去,经有限步调整.可知一切和数中,最大和数所对应的情况只能是数组｛ci｝由小到大排序的情况,最大和数是顺序和. 即S≤S2同样可证,最小和数是反序和,即 S1≤S.因此 S1≤S≤S2.