組合せ論と離散数学

不変量と単調量

組合せ論的過程の操作の下で不変に保たれる量、または単調に変化する量であり、不可能性や停止性の証明に用いられる。

直観なぜ解けないパズルがあるのか

$8\times 8$ のチェス盤から対角線上にある2つの角のマスを取り除き、 $62$ マスを残す。残りの盤面を $2\times 1$ のドミノ $31$ 枚で敷き詰められるだろうか。手で試すと毎回失敗するが、配置の仕方は何百万通りもある。場合分けの代わりに色に注目しよう。各ドミノは常に黒 $1$ マスと白 $1$ マスを覆うため、 $31$ 枚のドミノは黒 $31$ マスと白 $31$ マスを覆わなければならない。しかしチェス盤の対角の角は同じ色なので、残りは一方の色が $32$ マス、他方が $30$ マスになる!差 $W - B$ はドミノ配置の不変量であり、不可能性を一行で証明する。

不変量としての二部グラフ彩色:各辺(ドミノ)は両側から1頂点ずつを結ぶため、完全マッチングには両側の頂点数が等しいことが必要である。

大学定義:不変量と単調量

定義: 状態系の不変量と単調量

状態空間 $\mathcal{S}$ と許容遷移 $s \to s'$ を持つ組合せ過程を考える。関数 $I: \mathcal{S} \to X$ がすべての有効な遷移 $s \to s'$ に対して $I(s') = I(s)$ を満たすとき不変量という。実数値関数 $M: \mathcal{S} \to \mathbb{R}$ が各遷移で $M(s') < M(s)$ (狭義減少)または $M(s') > M(s)$ (狭義増加)を満たすとき単調量(ポテンシャル関数)という。

I(s_0) = I(s_1) = \cdots = I(s_k) \implies \text{if } I(s_{\mathrm{target}}) \neq I(s_0),\ s_{\mathrm{target}} \text{ is unreachable}

M(s_0) > M(s_1) > M(s_2) > \cdots \ge 0,\quad M(s) \in \mathbb{N} \implies \text{process terminates in } \le M(s_0) \text{ steps}

競技数学・研究で頻出する不変量と単調量の類型
手法	典型的な形	証明できること
偶奇不変量	$S \bmod 2$ または $(-1)^{\text{inversions}}$	目標状態への到達不可能性
合同・代数的不変量	$\sum a_i \bmod m$ または多項式評価	最終配置の一意決定
整数値単調量	$M(s) \in \mathbb{N}$ かつ $M(s') \le M(s) - 1$	$\le M(s_0)$ ステップ以内での停止

大学主要定理:15パズルの偶奇性と単調量停止定理

定理: 15パズルに対するロイド=ジョンソン偶奇不変量

$4\times 4$ のスライド式 $15$ パズルにおいて、 $N(s)$ をタイルの転倒数(行優先順でタイル $i$ がタイル $j$ より前に現れる $i > j$ の組 $(i,j)$ の個数)、 $r(s) \in \{1,2,3,4\}$ を空白マスの行番号(あるいは同値に $d(s)$ を空白マスから右下角までのマンハッタン距離)とする。このとき偶奇性 $(N(s) + r(s)) \bmod 2$ はすべての合法なスライド操作の下で不変である。特に、タイル $14$ と $15$ だけを入れ替えた配置は解けない。

なぜ正しいのか?

横方向のスライドは $15$ 個の数字タイルの行優先順をまったく変えない一方、縦方向のスライドは1つのタイルを行優先順でちょうど $3$ 個の他のタイルを飛び越えさせ(転倒数を $\pm 1$ または $\pm 3$ 、常に奇数だけ変化させ)、同時に空白の行 $r(s)$ を $\pm 1$ 変化させるからである。

証明

ステップ1(横スライド)。 空白が同じ行内で左右にスライドするとき、 $15$ 個の数字タイルの行優先順での並びは一切変わらず、空白も行 $r(s)$ にとどまる。したがって $\Delta N = 0$ かつ $\Delta r = 0$ であり、 $N(s) + r(s)$ は不変である。

ステップ2(縦スライド)。 空白が上下にスライドするとき、空白の元の位置へ移動するタイル $t$ は $15$ 個の数字タイルの行優先列の中でちょうど $3$ つ分位置がずれる。その $3$ 個の各タイルを飛び越えるたびに組 $(t, u)$ の転倒関係が反転し、 $N(s)$ は1タイルあたり $+1$ または $-1$ 変化する。合計の変化量は $\Delta N \in \{-3, -1, +1, +3\}$ で常に奇数である。同時に $\Delta r \in \{-1, +1\}$ も奇数なので、 $\Delta(N + r)$ は偶数となる。

ステップ3(14と15の交換)。 空白を行 $r = 4$ に固定したままタイル $14$ と $15$ を入れ替えると、 $\Delta r = 0$ のまま $N(s)$ が $+1$ ( $0$ から $1$ へ)変化する。よって初期状態( $1 + 4 \equiv 1 \pmod 2$ )と完成状態( $0 + 4 \equiv 0 \pmod 2$ )で $(N + r) \bmod 2$ が異なり、いかなる合法なスライド列でも完成状態に到達できないことが証明される。

定理: 整列単調量による停止定理

ある過程のすべての有効な遷移 $s \to s'$ が整数値関数 $M: \mathcal{S} \to \mathbb{Z}$ を少なくとも $1$ 減少させ(すなわち $M(s') \le M(s) - 1$ )、すべての状態 $s \in \mathcal{S}$ に対して $M(s) \ge 0$ であるとする。このとき任意の初期状態 $s_0$ から出発して、過程は高々 $M(s_0)$ ステップで必ず停止する。

なぜ正しいのか?

高さ $M(s_0)$ 段の階段を、1歩ごとに少なくとも1段ずつ降り、かつ地上階 $0$ より下には行けないとすれば、 $M(s_0)$ 回を超えて降り続けることはできない。

証明

**ステップ1( $k$ ステップ後の評価)。** $s_0 \to s_1 \to s_2 \to \cdots \to s_k$ を任意の有効な $k$ ステップの遷移列とする。 $i = 1, 2, \dots, k$ に対して仮定 $M(s_{i}) \le M(s_{i-1}) - 1$ を適用して辺々加えると、望遠鏡和により $M(s_k) \le M(s_0) - k$ を得る。

**ステップ2( $k$ の上界)。** 到達可能なすべての状態 $s_k \in \mathcal{S}$ について $M(s_k) \ge 0$ なので、2つの不等式を合わせると $0 \le M(s_k) \le M(s_0) - k$ 、すなわち $k \le M(s_0)$ がただちに従う。したがって長さ $k > M(s_0)$ の有効な遷移列は存在せず、過程は高々 $M(s_0)$ ステップで停止する。

発展実世界での応用と具体例

形式検証やソフトウェア工学において、ループ不変量とランキング関数(単調量)は、証明支援系(Lean、Coq、Dafny)が重要アルゴリズムの正当性と無限ループに陥らないことを保証する標準的な手法である。分散合意やチップ発火ネットワークでは、代数的不変量が到達可能な負荷分散状態を決定する。

例: 2数を消してその差を書く操作

黒板に $1, 2, 3, \dots, 2026$ の数が書かれている。毎回2つの数 $a, b$ を消して代わりに $|a - b|$ を書く操作を、1つの数が残るまで繰り返す。最後に残る数は $0$ になり得るか。

解答

$(a + b) - |a - b| = 2\min(a,b)$ は常に偶数なので、 $|a - b| \equiv a + b \pmod 2$ が成り立つ。したがって黒板上の全数の和の偶奇 $S \bmod 2$ は不変量である!

初期状態の総和は $S_0 = \frac{2026 \times 2027}{2} = 1013 \times 2027$ である。 $1013$ も $2027$ も奇数なので $S_0$ は奇数( $S_0 \equiv 1 \pmod 2$ )である。 $2025$ 回の操作の後に残るただ1つの数も $S_0 \equiv 1 \pmod 2$ を満たすため奇数であり、決して $0$ にはならない。

例: 平面上の交差する線分の解消

平面上に一般の位置にある $n$ 個の赤点と $n$ 個の青点が与えられ、それらを $n$ 本の線分で1対1に結ぶ。2本の線分 $A_1B_1$ と $A_2B_2$ が交差するたびに、それらを $A_1B_2$ と $A_2B_1$ に置き換える。この操作は有限回で必ず停止し、交差がなくなることを示せ。

解答

ポテンシャル $L(s) = \sum_{i=1}^n |A_iB_i|$ を $n$ 本の線分のユークリッド長の総和と定める。 $A_1B_1$ と $A_2B_2$ が点 $P$ で交差するとき、 $\triangle A_1 P B_2$ と $\triangle A_2 P B_1$ における三角不等式より $|A_1B_2| + |A_2B_1| < (|A_1P| + |PB_2|) + (|A_2P| + |PB_1|) = |A_1B_1| + |A_2B_2|$ が成り立つ。

よって $L(s)$ は各操作で狭義減少する単調量である!赤 $n$ 点と青 $n$ 点のマッチングは全部で $n!$ 通りしかないため、 $L(s)$ は高々 $n!$ 個の異なる値しかとれず、 $n! - 1$ 回を超えて減少することはできない。したがって操作は高々 $n! - 1$ ステップで停止する。

対角の2角を欠いた $8\times 8$ チェス盤を $2\times 1$ のドミノ $31$ 枚で敷き詰められないのはなぜか。

5つの数 $1, 2, 3, 4, 5$ から始め、毎回任意の2つに $1$ ずつ足す。5つの数をすべて等しくできるか。

非負整数値の単調量 $M(s) \in \mathbb{N}$ が $M(s_0) = 42$ から始まり、各ステップで $M(s') \le M(s) - 3$ を満たす。停止するまでの最大ステップ数はいくつか。

2つの数 $a, b$ を $a + b + ab$ に置き換えるとき、リスト全体で不変に保たれる代数的量はどれか。

参考文献

Arthur Engel (1998). Problem-Solving Strategies · DOI:10.1007/b97682
Jessica Striker (2017). Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance · DOI:10.1090/noti1539