不変量

不変量とは、許された操作を行っても変化しない量のことです。パズルをスライドさせたり、盤面からマスを切り取ったり、ケーニヒスベルクに橋を追加したりしてみてください。このページでは、反転数の偶奇、黒マスと白マスの差、奇数本の橋がかかっている陸地の数など、常にその不変量を示します。もし出発点と目標点でその量が異なれば、どのような手順を踏んでも目標には到達できないことになります。

計算例 — 不変量

反転数	1
不変量：反転数 mod 2	奇数
完成までの手数	到達不可能
空白の隣のタイルをクリックして移動	12345687

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — 不変量

不変量とは、許された操作を行っても変化しない量のことです。出発点と目標点でこの値が異なる場合、どのような手順を試みても目標には到達できません。そしてそれを知るために探索を行う必要は一切ありません。

各記号の意味

I: 不変量：ここでは反転数の偶奇、黒マスと白マスの差、または橋の数が奇数である陸地の数
d(v): 陸地vの次数：そこに繋がっている橋の数

公式の導き方

なぜスライドで偶奇が保たれるのか。 空白を無視して、8枚のタイルを行ごとに読んでください。横方向のスライドでは、この読み取る順番はまったく変わりません。縦方向のスライドでは、一つのタイルが順列の中で3つ分移動し、古いマスと新しいマスの間にある二つのタイルを飛び越えます。飛び越えられた二つのペアはそれぞれ反転が増減するため、全体の反転数は−2、0、+2のいずれかで変化し、奇数変化することは決してありません。完成状態の反転数は0なので、奇数である配置には到達不可能です。逆に偶数である配置のすべてに到達可能だという事実を示すほうが難問ですが、8パズルの場合はこのページの探索結果がそれを直接示しています。
なぜドミノで差が保たれるのか。 チェスボードではどのマスの隣も違う色です。そのため、隣り合う二つのマスを覆うドミノは必ず黒と白を一つずつ覆います。したがって、ドミノを配置しても、覆われていない黒マスと白マスの数の差は決して変わりません。敷き詰めが完了すると覆われていないマスはゼロとなり、その差も0になります。ゆえに、開始時点でも差が0であること、すなわち両方の色が同じ数だけあることが必要なのです。
なぜ奇数の陸地は最大二つなのか。 経路をたどってみましょう。陸地を通過するたびに一本の橋で到着し、別の橋で出発します。出発点では出発するためだけに使われ、終着点では到着するためだけに使われますが、それ以外では陸地にある橋は必ずペアで使われます。もし経路が出発点で終わるなら、すべての陸地の橋は偶数本になります。そうでないなら、まさに出発点と終着点だけが奇数本になります。橋がすべてを繋いでいればこの逆も成り立ち、このページでは、経路をいくつかのループとして構築し、それらを繋ぎ合わせることで全体の経路を見つけ出しています。

3 × 3のスライディングパズルの配置の半分には決して到達できません。そして、すべてを調べなくても、それがどちらの半分なのかを見分けることができます。 🖖

7と8の入れ替えを押して解いてみてください。タイルの並びを行ごとに読み、逆順になっているペアを数えます。ここでは1組、8が7の前に来ています。横方向のスライドではこの数は変わらず、縦方向のスライドでは一つのタイルが他の二つを飛び越えるため、変化量は0または2です。つまり反転数は永遠に奇数のままですが、完成状態の反転数は0なのです。このページでは完成状態からの全配置も探索しました。全362,880通りのうち、到達できるのは181,440通り。これは反転数が偶数の配置と完全に一致しており、最も遠い二つの配置には31手を要します。1880年に15パズルがアメリカを席巻し、1890年代にはサム・ロイドが14と15の入れ替えを元に戻すことに$1,000の懸賞金をかけました。しかし、これは決して誰にも受け取ることのできない賞金でした。

チェスボードの対角の二つの隅を切り落とすとドミノで敷き詰められない 🖖

対角の隅を押してください。盤面全体を32個のドミノで覆う方法は12,988,816通り存在します。しかし、対角の二つの隅を切り落とすと、もはや敷き詰めることはできません。どちらの隅も同じ色であるため、一方の色が30マス、もう一方が32マス残りますが、すべてのドミノは必ず各色を一つずつ覆うからです。代わりに一つの辺の両端にある二つの隅を切り落としてみましょう。この場合は各色が一つずつ減るため、2,436,304通りの敷き詰め方が残ります。次に隔離された隅を押してください。30マスと30マスで完全にバランスが取れていますが、やはり敷き詰めは不可能です。隅のマスに隣接するマスが一つも残っていないからです。色の数を使えば盤面が不可能であることは証明できますが、可能であることの証明には決してなりません。

ケーニヒスベルクの経路は暗算できる数え上げで不可能とわかる 🖖

ケーニヒスベルクを押してください。島には5本、他の三つの陸地にはそれぞれ3本の橋がかかっています。すべての橋を一度だけ渡る経路では、通過する陸地に到着して出発するため、そこにある橋をペアで使います。余る可能性があるのは、経路の出発点と終着点だけです。つまり、橋が奇数本ある陸地は最大でも二つしか許されませんが、ここでは四つすべてが奇数となっています。オイラーは1735年の論文でこの問題を解決しました。B–Cの横にある+で両岸の間に橋を一本追加してみましょう。奇数の陸地は二つだけ残り、ページはAからDへの経路を見つけ出します。四つの陸地の橋の数を合計すると常に橋の総数の2倍になります。そのため、奇数の陸地は必ずペアで現れるのです。

全プロセスの詳細解説

サム・ロイドの$1,000を獲得できた人はいたのか？ 4 ステップ
4 × 4の盤面で14と15だけを入れ替え、空白は隅に残します。 サム・ロイドはこれを完成状態に戻せた人に$1,000を支払うと申し出ました。はたして可能だったのでしょうか？

この問題をツールで開く
1. このページの3 × 3の盤面では、不変量は反転数の偶奇でした。
  
  $3 wide: a vertical slide passes 2 tiles \Rightarrow Δ I \in {- 2, 0, + 2}$
2. 幅が4の盤面では、縦方向のスライドで一つのタイルが他の三つを飛び越えるため、反転数は奇数変化し、空白の行も変わります。
  
  $4 wide: a vertical slide passes 3 tiles \Rightarrow Δ I \in {- 3, - 1, + 1, + 3}, Δ row = \pm 1$
3. どのスライドでも両方の偶奇が反転するか、どちらも反転しないかのいずれかです。したがって、それらのmod 2での和は決して変わりません。
  
  $I + row of the blank (mod 2) never changes$
4. 空白がどちらも4行目にある状態で、二つの配置を比較してみましょう。
  
  $solved: 0 + 4 = 4 (even), 14 \leftrightarrow 15 : 1 + 4 = 5 (odd)$
解答

誰にも獲得できませんでした。その入れ替えは不変量の反対側に位置しているからです。16!通りの配置のちょうど半分である10,461,394,944,000通りだけが、完成状態から到達可能です。7と8の入れ替えを押して、同じ罠の3 × 3バージョンを試してみてください。

$unreachable; \frac{16 !}{2} = 10, 461, 394, 944, 000 arrangements can be reached$

学習の道すじ

証明の手法

参考文献 (3)

The parity argument for the 15-puzzle, the history (made in upstate New York in the 1870s, a craze in early 1880, analysed in the American Journal of Mathematics that year) and Sam Loyd's later $1,000 prize for a swap that cannot be done: K. Conrad, "The 15-Puzzle (and Rubik's Cube)", expository notes, University of Connecticut.
Euler's paper on the seven bridges of Königsberg, which reduced the walk to the number of bridges at each land mass: L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii academiae scientiarum Petropolitanae 8, 128–140 (written 1735, published 1741); Eneström number E53, The Euler Archive.
The number of domino tilings of square boards, with 12,988,816 for the 8 × 8 chessboard: OEIS Foundation, "A004003: Number of domino tilings (or dimer coverings) of a 2n X 2n square", The On-Line Encyclopedia of Integer Sequences.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。