数列(?)の問題が解けません。

質問

この問題が解けません。どなたかアプローチを教えてください。

自然数1,2,3,……nの順列の内の一つ{a1,a2,a3,……an}を考える。
(たとえばn=6なら{5,2,3,6,1,4}など)
この順列に対し、
　　S=1*a1 + 2*a2 + 3*a3 + ...... +n*an
という和を考えたとき、
{a1,a2,a3,……an}が{1,2,3,……n}に一致したときSが最大に、
{a1,a2,a3,……an}が{n,n-1,n-2……1}に一致したときSが最小になることを示せ。

いくら考えても解き方がちっとも浮かんできません。
よろしくお願いします！

回答No.2

kabaokaba

それほど難しいわけではないです．
次のことを証明すればいいのです．

1<=i<j<=n なるiとjに対して，ai>ajとなるaiとajが存在するとき
S' = 1a1+2a2+・・・+iai+・・・+jaj+・・・+nan
S''= 1a1+2a2+・・・+iaj+・・・+jai+・・・+nan
とおけば，S'<S'' である

つまり，大小関係が「ひっくりかえってる」ときに
ひっくりかえってる部分を取り替えると「大きくなる」ということ．
これさえ示せば，もともとの問題を証明したことになります．
どうしてこれで最初の問題の証明に十分なのかは
自分で考えましょう．

回答No.1

koko_u_u

>どなたかアプローチを教えてください。

n = 4 に対する S をすべて求めて補足にどうぞ。