>>31
Aセットのk枚目をa(k)
Bセットのk枚目をb(k)と書くと

S = Σ_{k=1 to n} a(k) b(k) = a(1) b(1) + a(2) b(2) + … + a(n) b(n)
の最大値を求める問題

{a(k)-b(k)}^2 ≧0
a(k)^2 + b(k)^2 ≧ 2a(k)b(k)
で、これをk=1 〜 n で足せば

( Σ_{k=1 to n} a(k)^2 ) + ( Σ_{k=1 to n} b(k)^2 ) ≧ 2 S

ここで{ a(k)} も {b(k)} も1〜nまでの自然数の並び替えなので
順序に関係無く
Σ_{k=1 to n} a(k)^2 = Σ_{k=1 to n} b(k)^2 = 1+2^2 + … + n^2
という和に等しい。
つまり
2 ( 1+2^2 + … + n^2) ≧ 2S
1+2^2 + … + n^2 ≧S
となり、
a(1) = b(1) = 1
a(2) = b(2) = 2
…
a(n) = b(n) = n
のとき、等号が成り立つので Sの最大値は1+2^2 + … + n^2になる。

ポイントはa(k)やb(k)の取り方によって不等式の両辺が同時に動く場合は
このような最大値の示し方は、やや難があるけど
この問題の場合は片方が固定できるので最大値を示すのに使える。