不変量と単調量

縦に 3 片・横に 4 片並んだ、合わせて 12 片の板チョコを、1 片ずつばらばらにしたい。1 回の操作では、手元にある 1 つのかたまりを選び、溝に沿ったまっすぐな 1 本の線で 2 つに割る（2 つのかたまりを重ねて一度に割ることはしない）。
図 1 は、上から 1 行ずつ切り離し、切り離した行を 1 片ずつに分ける割り方である。1 行目を切り離すのに 1 回、その行を 4 片に分けるのに 3 回、2 行目を切り離すのに 1 回、分けるのに 3 回、最後に残った 3 行目を分けるのに 3 回かかるので、合計は
$$ 1+3+1+3+3=11 $$
回である。図 2 は、いつもいちばん大きいかたまりを選び、長い方の辺をなるべく半分に分ける線で割る、まったく違う割り方である。数えるとこれも 11 回になる。
11 回になる理由は、割る順番ではなく、かたまりの個数にある。最初はかたまりが 1 個で、1 回割るたびに、1 個のかたまりが 2 個になるので、かたまりの個数はちょうど $1$ だけ増える。最後はかたまりが 12 個なので、何回割ったかを $k$ とすると
$$ 1+k=12,\qquad k=11 $$
である。どう割っても 11 回で、10 回で済む割り方も 12 回かかる割り方もない。

黒板に $1,2,3,4$ の 4 つの数が書いてある。1 回の操作では、2 つの数 $a,b$ を選んで消し、代わりに $\lvert a-b\rvert$ を 1 つ書く。数は 1 回ごとに 1 つ減るので、3 回の操作で 1 つだけ残る。
たとえば $1,2$ を消して $1$ を書くと $1,3,4$、次に $3,4$ を消して $1$ を書くと $1,1$、最後に $1,1$ を消して $0$ を書くと $0$ が残る。別の順に、$1,4$ を消して $3$ を書くと $2,3,3$、$3,3$ を消して $0$ を書くと $2,0$、最後に $2$ が残る。
残る数は順番によって変わるが、いつも偶数である。理由は、黒板の数の和の偶奇にある。$a+b$ と $\lvert a-b\rvert$ の差は、$a\ge b$ なら $(a+b)-(a-b)=2b$、$a< b$ なら $(a+b)-(b-a)=2a$ で、どちらも偶数である。したがって 1 回の操作で和は偶数だけ変わり、和の偶奇は変わらない。最初の和は $1+2+3+4=10$ で偶数なので、最後に残る 1 つの数も偶数である。

1. ex-inv-board の操作で、黒板の数の和を $2$ で割った余りは不変量である。和そのものは不変量ではない。$\{1,2,3,4\}$ の和は $10$、$\{1,3,4\}$ の和は $8$ である。
2. 同じ操作で、黒板にある数の個数は 1 回ごとにちょうど $1$ 減るので、単調量である。$\{1,2,3,4\}$ では $4$、$\{1,3,4\}$ では $3$、$\{1,1\}$ では $2$、$\{0\}$ では $1$ である。
3. ex-inv-choco で、状態を「かたまりの集まりと、それまでに割った回数 $k$ の組」とすると、「かたまりの個数 $-\,k$」は不変量である。1 回割るとかたまりの個数も $k$ も $1$ 増えるので、差は変わらない。最初の値は $1-0=1$ である。

赤・緑・青の 3 色の生き物が合わせて 15 匹いて、赤が $4$ 匹、緑が $5$ 匹、青が $6$ 匹である。1 回の操作では、違う色の 2 匹が出会い、2 匹とも残りの 1 色に変わる。たとえば赤と緑が出会うと、2 匹とも青になる。全部を同じ色にできるか。
赤・緑・青の数を $(r,g,b)$ で表す。3 種類の出会い方で、数は次のように変わる。
$$ (r,g,b)\to(r-1,\,g-1,\,b+2),\qquad (r,g,b)\to(r+2,\,g-1,\,b-1),\qquad (r,g,b)\to(r-1,\,g+2,\,b-1) $$
差 $r-g$ はそれぞれ $0$、$+3$、$-3$ だけ変わる。どれも $3$ の倍数なので、$r-g$ を $3$ で割った余りは不変量である（合同式の計算規則）。同じ理由で $g-b$、$b-r$ を $3$ で割った余りも不変量である。
最初は $r-g=-1$、$g-b=-1$、$b-r=2$ で、$3$ で割った余りはどれも $2$ である（$-1=3\cdot(-1)+2$ なので、$-1$ を $3$ で割った余りは $2$）。一方、全部が同じ色の状態は $(15,0,0)$、$(0,15,0)$、$(0,0,15)$ の 3 つで、どれも 2 つの数が $0$ なので、差のどれかが $0$ になり、その差を $3$ で割った余りは $0$ である。たとえば $(15,0,0)$ では $g-b=0$ である。thm-inv-invariant により、全部を同じ色にすることはできない。図 3 は、この様子を赤と緑の数の平面で見たものである。
同じ 3 色で、最初が $(4,5,7)$ の 16 匹なら、$r-g$ と $b-r$ を $3$ で割った余りは $2$ と $0$ で、余り $0$ の差がある。この場合は全部を同じ色にできる。最初に緑と青を出会わせて $(4,5,7)\to(6,4,6)$ とし、その後は赤と青を出会わせることを続ける（赤と青が $1$ 匹ずつ減り、緑が $2$ 匹増える）と
$$ (6,4,6)\to(5,6,5)\to(4,8,4)\to(3,10,3)\to(2,12,2)\to(1,14,1)\to(0,16,0) $$
となり、全部が緑になる。「行ける」ことは、このように操作の列を実際に示して確かめる。

$3,1,4,2$ と並んだ 4 枚のカードがある。1 回の操作では、隣り合う 2 枚で左の数の方が大きいものを 1 組選び、その 2 枚を入れかえる。そのような組がなくなったら止まる。
図 4 の手順 1 は、$3,1$ を入れかえて $1,3,4,2$、$4,2$ を入れかえて $1,3,2,4$、$3,2$ を入れかえて $1,2,3,4$ と進み、3 回で止まる。手順 2 は、先に $4,2$ を入れかえて $3,1,2,4$、次に $3,1$ を入れかえて $1,3,2,4$、最後に $3,2$ を入れかえて $1,2,3,4$ で、これも 3 回である。
ここで、並びの中で「左にある数の方が大きい 2 枚の組」の個数を数える。これを 転倒数 という。$3,1,4,2$ では、組 $(3,1)$、$(3,2)$、$(4,2)$ の 3 組なので転倒数は $3$ である。図 4 のどちらの手順でも、転倒数は 1 回ごとに $3,2,1,0$ と $1$ ずつ減っている。

ex-inv-sort の操作を、異なる $n$ 個の数の並び $p_1,p_2,\dots,p_n$ で考える。転倒数を $T$ とする。隣り合う $p_i>p_{i+1}$ を入れかえたとき、どの 2 つの数の組で左右の順が変わるかを調べる。
(1) 入れかえた 2 つの数 $p_i,p_{i+1}$ の組は、大きい方が左にある状態から右にある状態に変わる。この組は転倒数に数えられなくなる。
(2) それ以外の 2 つの数の組で、どちらの数も $i$ 番目・$i+1$ 番目にないものは、どちらの位置も変わらない。
(3) 一方の数が $i$ 番目か $i+1$ 番目にあり、もう一方が $k$ 番目（$k< i$ または $k>i+1$）にある組では、前者の位置は $i$ と $i+1$ の間で動くだけである。$k< i$ なら入れかえの前も後も $k$ 番目の数が左にあり、$k>i+1$ なら前も後も右にある。左右の順は変わらない。
よって転倒数はちょうど $1$ だけ減る。転倒数は $0$ 以上の整数なので単調量であり、thm-inv-terminate により、どの順に入れかえても $T$ 回以内に止まる。止まった並びでは、隣り合うどの 2 つも左が小さいので、$p_1< p_2<\cdots< p_n$ と小さい順に並んでいる。その転倒数は $0$ である。1 回ごとにちょうど $1$ 減って $T$ から $0$ になるので、止まるまでの回数はどの順でもちょうど $T$ 回である。$4,3,2,1$ なら転倒数は $6$ で、どう入れかえても 6 回かかる。

2 行 3 列の表
$$ \begin{array}{|r|r|r|}\hline 1&-3&2\\\hline -2&1&-4\\\hline\end{array} $$
がある。1 回の操作では、和が負である行か列を 1 つ選び、その行（列）の数の符号をすべて変える。行の和は $0,-5$、列の和は $-1,-2,-2$ で、表の数全体の和は $-5$ である。
和が $s<0$ の行の符号を変えると、その行の和は $-s$ になり、全体の和は $-s-s=-2s>0$ だけ増える。列でも同じである。したがって全体の和は、操作のたびに必ず増える単調量である。一方、表の各数は最初の数か、その符号を変えた数なので、表は $2^6=64$ 通りしかない。cor-inv-finite により、どの順に選んでも 63 回以内に止まる。止まった表では、どの行の和もどの列の和も $0$ 以上である。
実際に進めてみる。2 行目の符号を変えると、2 行目は $2,-1,4$ になり全体の和は $5$、列の和は $3,-4,6$ になる。次に 2 列目の符号を変えると
$$ \begin{array}{|r|r|r|}\hline 1&3&2\\\hline 2&1&4\\\hline\end{array} $$
となり、全体の和は $13$ で止まる。

ex-inv-board の $1,2,3,4$ では、和の偶奇から最後の数は偶数である。$6$ も偶数だが、$6$ は最後に残らない。
理由は別の量にある。$a,b\ge0$ のとき $\lvert a-b\rvert\le\max(a,b)$ なので、黒板の数の最大値は操作で増えない。最初の最大値は $4$ なので、$6$ は現れない。すべての順を調べると、最後に残る数は $0,2,4$ の 3 通りである。不変量は「行けない」ことを示すだけで、値が等しいことは「行ける」ことを意味しない。

状態を整数全体とし、操作を $n\to n-1$ とする。$f(n)=n$ は操作のたびにちょうど $1$ 減るが、$0$ 以上という条件を満たさない。$0\to-1\to-2\to\cdots$ と操作はいつまでも続き、止まった状態に着かない。prf-inv-terminate の段 3 で $0\le f(s_k)$ を使ったところが成り立たない。

状態を $0$ 以上の整数 $k$ とし、操作を $k\to k+1$ とする。$f(k)=2^{-k}$ は正の値で、$2^{-(k+1)}<2^{-k}$ なので操作のたびに必ず減る。しかし操作はいつまでも続く。値が整数でないので、prf-inv-terminate の段 1 の「$1$ 以上減る」が成り立たず、減り方が $\dfrac12,\dfrac14,\dfrac18,\dots$ と小さくなっていく。図 5 の右がこの様子である。状態が無限個あるので、cor-inv-finite も使えない。

状態を $0$ 以上の整数 2 つの並び $(x,y)$ とし、操作を $(x,y)\to(y,x)$ とする。和 $f=x+y$ は $0$ 以上の整数で増えることはないが、操作で変わらないので「必ず減る」を満たさない。$(1,2)\to(2,1)\to(1,2)\to\cdots$ と操作は続き、止まらない。「減るか変わらない」量だけでは、同じ状態を回り続けることを防げない。