6 隣接積和が最小となる並び

次は $S_3$, $S_2$ の最小値の方を考える。 こちらは、最大の場合より少し複雑である。 まずは、補題 1 に対応する補題を紹介する。

補題 3.

$a_1\leq a_2\leq\cdots\leq a_k$ の並べかえを $A$ とする。

1. $x\leq y\leq a_1$ のとき、 $A$ の左端が $a_k$ でない場合は、 左端が $a_k$ である並びかえ $A'=[a_k \cdots]$ で、

   $$S_3([x A y])\geq S_3([x A' y])$$

   
   となるものが存在する。
2. $x\leq a_1\leq a_k\leq y$ のとき、 $A$ の右端が $a_1$ でない場合は、 右端が $a_1$ である並びかえ $A'=[\cdots a_1]$ で、

   $$S_3([x A y])\geq S_3([x A' y])$$

   
   となるものが存在する。
3. $x\leq a_1\leq a_k\leq y$ のとき、 $A$ の左端が $a_k$ でない場合は、 左端が $a_k$ である並びかえ $A'=[a_k \cdots]$ で、

   $$S_3([x A y])\geq S_3([x A' y])$$

   
   となるものが存在する。
4. $a_k\leq x\leq y$ のとき、 $A$ の右端が $a_1$ でない場合は、 右端が $a_1$ である並びかえ $A'=[\cdots a_1]$ で、

   $$S_3([x A y])\geq S_3([x A' y])$$

   
   となるものが存在する。

証明

まずは 1. から示す。 この場合は、 $[A y]=[B a_k C]$ とし、 $B$ の左端を $p$, $C$ の左端を $q$ とし、 $A$ の $[B a_k]$ を反転させたものを $A'$ とすると、 $[A' y] = [a_k \bar{B} C]$ で、 $p$ は $a_1,\ldots,a_{k-1}$ のいずれか、 $q$ は $a_1,\ldots,a_{k-1},y$ のいずれかで、

$$[x A y]=[x p \cdots a_k q \cdots y], \hspace{1zw} [x A' y]=[x a_k \cdots p q \cdots y]$$

であり、よって

$$S_3([x A y])-S_3([x A' y]) = xp +a_kq - xa_k-pq = (x-q)(p-a_k)$$

となるが、仮定より $q\geq y\geq x$, $p\leq a_{k-1}\leq a_k$ より $(x-q)(p-a_k)\geq 0$、よって $S_3([x A y])\geq S_3([x A' y])$ となる。

次は 2. この場合は、 $[x A]=[B a_1 C]$ とし、 $B$ の右端を $p$, $C$ の右端を $q$ とし、 $A$ の $[a_1 C]$ を反転させたものを $A'$ とすると、 $[x A'] = [B \bar{C} a_1]$ で、 $p$ は $a_2,\ldots,a_k,x$ のいずれか、 $q$ は $a_2,\ldots,a_k$ のいずれかで、

$$[x A y]=[x \cdots p a_1 \cdots q y], \hspace{1zw} [x A' y]=[x \cdots p q \cdots a_1 y]$$

であり、よって

$$S_3([x A y])-S_3([x A' y]) = pa_1 + qy - pq-a_1y = (p-y)(a_1-q)$$

となるが、仮定より $p\leq a_k\leq y$, $q\geq a_2\geq a_1$ より $(p-y)(a_1-q)\geq 0$、よって $S_3([x A y])\geq S_3([x A' y])$ となる。

次は 3. この場合は、1. と同じに $B$, $C$, $A'$, $p$, $q$ を 取ると、

$$S_3([x A y])-S_3([x A' y]) = (x-q)(p-a_k)$$

だが、仮定より $q\geq a_1\geq x$, $p\leq a_{k-1}\leq a_k$ より $(x-q)(p-a_k)\geq 0$、よって $S_3([x A y])\geq S_3([x A' y])$ となる。

最後は 4. この場合は、2. と同じに $B$, $C$, $A'$, $p$, $q$ を 取ると、

$$S_3([x A y])-S_3([x A' y]) = (p-y)(a_1-q)$$

だが、仮定より $p\leq x\leq y$, $q\geq a_2\geq a_1$ より $(p-y)(a_1-q)\geq 0$、よって $S_3([x A y])\geq S_3([x A' y])$ となる。

この補題 3 に従い、最大値の場合と同様に $A$ の並びを ジグザグに決めていけば最小値を与える並びを得ることができる。

まずは $S_3$ から考える。 最大値の場合と同様に $S_3(A)=S_3([0 A 0])$ を考えると、 補題 3 の 1. により $S_3$ を最小にするには $A$ の左端には $a_n$ を置くとよいことがわかる。

すると $A=[a_n A']$ になるので、次は

$$S_3(A) = S_3([a_n A']) = S_3([a_n A' 0]) = S_3([0 \bar{A'} a_n])$$

を考える。 これは、補題 3 の 3. の形なので、 $S_3$ を最小にするには $\bar{A'}$ の左端、 すなわち $A'$ の右端には $a_{n-1}$ を置くとよいことがわかる。

なお、これは補題 3 の 2. の形でもあるので、 $\bar{A'}$ の右端、 すなわち $A'$ の左端 ($A$ でいえば左から 2 番目) に $a_1$ を 先に置いてもよいが、とりあえず端からジグザグ順に埋めることとし、 ここでは $a_{n-1}$ を先に $A'$ の右端に埋めることにする。

これで $A=[a_n A'' a_{n-1}]$ となるが、 これは、補題 3 の 4. を反転させた形なので、 $S_3$ を最小にするには、$A''$ の左端は $a_1$ と決まる。 そしてさらに $A=[a_n a_1 A''' a_{n-1}]$ に対しては 補題 3 の 2. により、 $A'''$ の右端が $a_2$ と決まる。

これらの手順を繰り返すことで、$S_3(A)$ を最小にする並べかえ $A$ は、

$$A = [a_n a_1 a_{n-2} a_3 \cdots a_4 a_{n-3} a_2 a_{n-1}]$$ (15)

であり、これは $a_n,a_{n-1},a_1,a_2,a_{n-2},a_{n-3},a_3,a_4,\ldots$ を 左端、右端、左から 2 番目、右から 2 番目、...のような 順番に並べていったものとなる。

なお、上でも触れたように補題 3 の 2. と 3. の適用順を変えれば、 左端 2 つを先に $a_n, a_1$ と決定し、次は右端 2 つを $a_2, a_{n-1}$ と 決定する、という形の「2 つずつのジグザグ順」に並べていくことも 可能である。 なお、いずれにせよ 4 回で 1 セット、 といった並べ方になっていることに注意する。

最後に $S_2$ の最小値を考える。

これは、最大の場合と同様、(14) のようにして $S_2$ を $S_3$ に帰着させて考えるのであるが、 しかし最大の場合とは違い、 $S_3$ の最小値を与える並び (15) は、 $S_2$ の最小値を与えない。

$S_2$ は巡回的なので、左端は任意の $a_j$ に固定できるので、 左端を $a_1$ とする。

この場合、(14) をそのまま使えば、 上の $S_3$ の最小の場合 $[0 A 0]$ から始めたのとほぼ同じ状態と 見ることができる。よって、この場合の $S_3([a_1 \bar{A'} a_1])$ を 最小にする並びは

$$[a_1 \bar{A'} a_1] = [a_1 \bar{A}] = [a_1 a_n a_2 a_{n-2} a_4\cdots a_5 a_{n-3} a_3 a_{n-1} a_1]$$

であることがわかる。 埋める順番は、両端を除けば $a_n$ が先、つまり左から先である。 この左端の $a_1$ を除いて反転すれば $A$ の並びが得られる:

$$A = [a_1 a_{n-1} a_3 a_{n-3} a_5\cdots a_4 a_{n-2} a_2 a_n]$$ (16)

上では $a_1$ を仮定して $a_n$ から埋めていったので、 並べ方の順番は、左端の $a_1$ が最初で、次は右端の $a_n$、 次は左の $a_{n-1}$、というジグザグ順に埋めることになる。

なお、今は $A$ の左端を $a_1$ と固定して考えたが、 次にこれを $a_n$ に固定して考えてみる。 この場合、

$$S_2(A) = S_2([a_n A']) = S_3([a_n A' a_n])$$

なので、(15) の両端が既に並んでいると 見ればよい。よってこの値を最小にするのは、

$$[a_n A] = [a_n A' a_n] = [a_n a_1 a_{n-1} a_3 \cdots a_4 a_{n-2} a_2 a_n]$$

であり、よって $S_2$ の最小を与える $A$ はこれの右端の $a_n$ を除いた

$$A = [a_n a_1 a_{n-1} a_3 \cdots a_4 a_{n-2} a_2]$$

であることがわかる。しかし、これは最初が $a_n$、次がその隣の $a_1$、 その次が右端の $a_2$ のようになってしまい、 先頭がジグザグ順にはなっていない。 よって、左端の $a_n$ を右端に巡回的に移動させた

$$A = [a_1 a_{n-1} a_3 \cdots a_4 a_{n-2} a_2 a_n]$$ (17)

を $S_2$ の最小を与えるものと見ることができ、 これでジグザグ順の並べかえが得られることになる。

これは、並びだけ見れば (16) と同じもののようであり、 $S_2$ の同じ最小値を与えることは 一見明らかなように見える。

しかし、注意しなければいけないのは、その並びを決定する順番の違いであり、 (16) の方は左端の $a_1$ が最初で 次が右端の $a_n$、という順であるが、 (17) の方は右端の $a_n$ が最初で 次が左端の $a_1$、という順になっていて、 並びは同じようであるが順番は逆になっている。 ということは、この 2 種類の並べ方の最後の方で並び方がずれてしまわないか、 違ってしまわないか、をちゃんと確認する必要がある。

手順は 4 つで 1 セットなので、$n$ が 4 で割りきれる場合、4 で割って余りが 1, 2, 3 のそれぞれの場合、の 4 通りで調べればよい。 簡単のため $n=4,5,6,7$ で考えてみる。 これで同じであれば、これ以上 $n$ を増やしても 4 つのセットが 追加されるだけなので同じである。

まず $n=4$ の場合、(16) に従って 左端から並べる。置く順番は、左端から

$$a_1, a_4 (=a_n), a_3(=a_{n-1}), a_2$$

の順なので、結果として

$$[a_1 a_3 a_2 a_4]$$

という列になる。一方、(17) の方は、 置くのは

$$a_4(=a_n), a_1, a_2, a_3(=a_{n-1})$$

の順なので、

$$[a_1 a_3 a_2 a_4]$$

となり確かに同じものになっていて、ずれは起きないことがわかる。

$n=5$ の場合は、 (16) の方は

$$a_1, a_5(=a_n), a_4(=a_{n-1}), a_2, a_3$$

の順、(17) の方は

$$a_5(=a_n), a_1, a_2, a_4(=a_{n-1}), a_3(=a_{n-2})$$

の順で、いずれも $[a_1 a_4 a_3 a_2 a_5]$ とやはり同じものになる。

$n=6$ の場合は、 (16) の方は

$$a_1, a_6(=a_n), a_5(=a_{n-1}), a_2, a_3, a_4(=a_{n-2})$$

の順、(17) の方は

$$a_6(=a_n), a_1, a_2, a_5(=a_{n-1}), a_4(=a_{n-2}), a_3$$

の順で、いずれも $[a_1 a_5 a_3 a_4 a_2 a_6]$ となり、 $n=7$ の場合は、 (16) の方は

$$a_1, a_7(=a_n), a_6(=a_{n-1}), a_2, a_3, a_5(=a_{n-2}), a_4(=a_{n-3})$$

の順、(17) の方は

$$a_7(=a_n), a_1, a_2, a_6(=a_{n-1}), a_5(=a_{n-2}), a_3, a_4$$

の順でいずれも $[a_1 a_6 a_3 a_4 a_5 a_2 a_7]$ となる。

結局、$S_2$ の方は、最小を与える並びは (16) で、並べかたは右から先でも左から先でもよいが、 端からジグザグ順に並べていったもの、であることがわかる。

定理 4.

$S_3(A)$ は、 (15) の並びのときに最小となり、 $S_2(A)$ は、 (16) の並びのときに最小となる。 並べ方はいずれも左端からジグザグ順に並べていく。

$S_2$ と $S_3$ の最小値は、異なる並びで最小を与えることになっている。 これは、最大値の方が、なるべく大きいもの同士を かけるようにしているのに対し、 最小解は逆に大きいものには小さいものをかけるようにして 大きくならないようにしていることに由来する。

$S_3$ の場合は両端に一番大きいもの ($a_n$ と $a_{n-1}$) を置くことで、 それらにはそれぞれ一番小さいもの ($a_1$ と $a_2$) をひとつかけた 積 1 つだけを作るようにしているのに対し、 巡回型の $S_2$ の場合は両端に $a_n$ と $a_{n-1}$ を置いてしまうと、 それらの積が入ってしまうので小さくならず、よって (16) では 巡回的に大きいものと小さいものが順番に並ぶようになっている。 そのため $S_2$ と $S_3$ の最小を与える並び方が違っているわけである。