ソートする系の貪欲証明 part.1

Minimum(Maximum) Scalar Product

与えられた $2$ つの実ベクトル $A=(A_1,\ A_2,\ \dots,\ A_n),\ B=(B_1,\ B_2,\ \dots,\ B_n)$ に対して適当な $\sigma_a,\ \sigma_b$ を選び、 $(A\sigma_a)\cdot (B\sigma_b)=A_{\sigma_a(1)}B_{\sigma_b(1)}+A_{\sigma_a(2)}B_{\sigma_b(2)}+\cdots+A_{\sigma_a(n)}B_{\sigma_b(n)}$ を最小・最大化する問題。解法は、最小の場合は $A,\ B$ をそれぞれ昇順、降順に、最大の場合は $A,\ B$ をそれぞれ昇順にソートするだけである。蟻本に証明が載っているが、ちょっとだけ飛躍を感じたので補足になればと思う。

最初に最大化問題を考える。
簡単のため $A,\ B$ をそれぞれ昇順にソートしておく(すなわち、 $A_1\le A_2\le\dots\le A_n,\ B_1\le B_2\le\dots\le B_n$ となるよう並び替える)。
また、 $\sigma_a$ は恒等置換とする。

まず、以下の補題はすぐにわかるだろう。
補題 I
$x\le X,\ y\le Y$ のとき、 $Xy+xY\le XY+xy$
【証明】
$(XY+xy)-(Xy+xY)=(X-x)(Y-y)\ge 0$

さて、 $i\lt j$ かつ $(B\sigma_b\sigma_1\sigma_2\cdots\sigma_{k-1})_i\gt (B\sigma_b\sigma_1\sigma_2\cdots\sigma_{k-1})_j$ となる $i,\ j$ が存在する間、 $k$ 回目には $B\sigma_b\sigma_1\sigma_2\cdots\sigma_{k-1}$ に $i$ と $j$ の交換 $\sigma_k$ を掛けて、 $m$ 回の交換の後 $i\lt j$ かつ $B_{\sigma_b(i)}>B_{\sigma_b(j)}$ となる $i,\ j$ が存在しなくなったとする。
このとき、 $B\sigma_b\sigma_1\sigma_2\cdots\sigma_m=B$ が満たされている (すなわち、 $B\sigma_b\sigma_1\sigma_2\cdots\sigma_m$ は昇順にソートされている)。
ここで、補題 Iより、 $(A\sigma_a)\cdot(B\sigma_b)\le(A\sigma_a)\cdot(B\sigma_b\sigma_1)\le (A\sigma_a)\cdot(B\sigma_b\sigma_1\sigma_2)\le\cdots\le(A\sigma_a)\cdot(B\sigma_b\sigma_1\sigma_2\cdots\sigma_m)=A\cdot B$ であるから、任意の $\sigma_b$ に対して $(A\sigma_a)\cdot(B\sigma_b)\le A\cdot B$ が言え、すなわち $A\sigma_a,\ B\sigma_b$ が昇順のとき $(A\sigma_a)\cdot (B\sigma_b)$ が最大になることが言える。