置換・互換と１４－１５パズルの不可能性～３パズル＆８パズルからの証明

今年に入って、大学レベルの行列、線型代数の数学記事を３本書いた。こ

れはたまたま、引越しパニックによって他の理数系の本が見当たらなくなっ

たという個人的理由が大きいのだが、前からずっと気になってたパズルの

影響もある。

当サイトでは３年半前、有名なパズルに関する論理的考察の記事を書いた。

　　　「１５パズル」の攻略法～８パズル、３パズルへの還元

　　１５パズルとは、左のようなもの。

　　４×４＝１６マスからなる正方形

　　の枠の中で、１～１５と書かれた

　　１５個のブロックを動かして、目的

　　の配置（普通は左図）にするもの

　　だ。知ってる人も多いと思う。数字

　　の代わりに絵を使って、ジグソー

パズルみたいにした物もある。

この図と次の図（少し下）は、ウィキメディアで公開中、パブリックドメイン（公

的所有物）。

この１５パズルを簡単にしたものが、３パズル（２×２＝４マスで、３個のブ

ロック）や、８パズル（３×３＝９マスで、８個のブロック）だ。以下で登場する。

　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

さて、３年半前の記事では、「解けない問題」の存在に触れて、線型代数を

使えば解けないことが数学的に証明できるとだけ書いておいた。その際、

ネットで松井知己氏の小論文、『１４－１５パズルは何故解けないか？』の

ｐｄｆファイル（執筆当時は東大大学院）を見つけたが、その時点では読んで

も何となくしか分からなかったので、パスしたままだったのだ。　　　

先日、置換と互換の記事を書いた後、試しに自分で考えてみたら、あっさり

証明成功。その後、松井氏のファイルや日米のウィキペディアを読み直して

みて、私なりにもっと分かりやすく説明する価値があるなと思ったので、以

下、理論的にも歴史的にも遡って、書いてみよう。

置換と互換の知識は前提とするので、知らない方はまず次の記事の前半

だけでも御覧あれ。高校数学の行列を知らなくても、大体理解できると思う。

　　　　置換・互換による行列式の定義～初心者向け

　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

　　ではまず、「解けない問題」の代

　　表例を見てみよう。左は、標準的

　　な完成型の１４と１５の順序だけ

　　替えたもので、米国のゲーム研

　　究者サム・ロイドが１８８０年代以

　　降に流行らせた（と主張してる）ら

　　しい（英語版ウィキの説明）。

そもそも１５パズル自体、ロイドの発明だと本人は語ってるとの事。詳細は

不明だが、いずれにせよ１９世紀後半の米国が、１５パズルの発祥の地と

いう話だ。

　　さて、ロイドは、

　　上図や左のように

　　１４と１５だけ入

　　れ替えた配置の

　　１５パズルの解決

　　に、１０００ドルの

　　懸賞金をかけた

　　ので、人々はます

　　ます熱狂。やがて、

この配置の１５パズルは「１４－１５パズル」と呼ばれるようになったとの事。

図はネットで公開されてる、ロイドの『Ｃｙｃｌｏｐｅｄｉａ　ｏｆ　Ｐｕｚｚｌｅｓ』より。著作

権はもちろん消滅済み。

ところが、これが解決不可能であることは、既に１８７９年の数学論文で証明

されてたらしい（ジョンソン＆ストーリー、無料公開中、英語）。１４と１５だけ

を入れ替えることは出来ないし、他にも解けない配置は多数あるのだ（おそ

らく全体の半数）。

　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆　

では、３パズルから、不可能性の証明を始めよう。まず、ブロックの配置に名

　　前を付けるのがポイント。左のような順番に

　　ブロックの数字を読んで、数字の列（＝数列）

　　との４対１対応を付けるのだ。

　　この場合、左の４

　　つの配置はすべて、

　　数列「１２３」と呼

　　ばれることになる。　　　　

よって、数列が変わるようなブロックの動かし方は、左側で上下に動かすも

　　のしかない。上から下に動か

　　す場合、左のように数列が変

　　わる（Ａ、Ｂ、Ｃは１～３の数）。

　　Ａが２個のブロックＢＣを飛び

　　越えた形だ（数列で右向きに）。

　　これは要するに、ＡＢＣの置換

（並べ替え）であって、下のように、互換（２つだけの入れ替え）２個の積で表

せる。偶数個の互換になるから、元の置換は偶置換。符号（ｓｇｎ）は＋１だ。

ちなみに、カッコ内の上下２行は、上から下への入れ替えを表す。また、互

換も含めて、置換の積（掛け算）は右から考えるので、念のため。Ｂの場合

だと、まず右側の互換によってＡになり、次に左側の互換によってＣになる。

結局２つの互換でＢ → Ａ → Ｃとなるから、置換の Ｂ → Ｃ と一致するのだ。

　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

元の３パズルに戻ると、左側で下から上にブロックを動かしても同じこと。結

局、ブロックをどう動かしても、偶数個の互換を積み重ねて行くだけだから、

結果的には偶数個の互換。つまり偶置換にしかならない。

　　ここで、左のような配置変換の問題

　　を考えてみよう。２と３だけ、標準形

　　と入れ替えたもので、もし可能だと

　　するなら、その置換は１個（奇数個）

　　の互換で表されるはず（下図）。

　　つまり奇置換になってしまう

　　（符号は－１）。偶置換が奇置

　　換になることはないので、ブロッ

　　ク移動（つまり偶置換）によっ

　　ては実現不可能なのだ。

　　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

　　同様の考え方で、８パズルの不可能性

　　も証明できる。今回は左のようにブロッ

　　クの数字を読んで、数列と対応させよう。

　　この場合、下のような９種類の配置はす

　　べて数列「１２３４５６７８」と対応する

　　（途中の図は省略、３つだけ書いた）。

　　この時、３パズルの

　　時と本質的に違うブ

　　ロックの動かし方は、

　　左のようなものしか

　　無い。つまり、Ｄが

　　４個のブロックＥＦＧ

　　Ｈを飛び越えた形だ。

これは要するに、ＡＢＣＤＥＦＧＨの置換であって、下のように、互換４個の

積で表せる。偶数個の互換になるから、元の置換は偶置換。符号（ｓｇｎ）は＋１だ。

　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

元の８パズルに戻ると、結局ブロックをどう動かしても、偶数個（２個か４個）

の互換を積み重ねて行くだけだから、結果的には偶数個の互換。つまり偶

置換にしかならない。

　　ここで、左のような配

　　置変換の問題を考え

　　てみよう。７と８だけ、

　　標準形と入れ替えた

　　もので、もし可能だと

　　するなら、その置換

　　は１個（奇数個）の互

　　換で表されるはず

　　（下図）。　　　　

　　つまり奇置換に

　　なってしまう（符

　　号は－１）。偶

　　置換が奇置換に

　　なることはない

ので、ブロック移動（つまり偶置換）によっては実現不可能なのだ。

　　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

　　もはや、１４－１５パズルの不可能性は

　　明らかだろう。左のようにブロックの数

　　字を読んで、数列と対応させる。

　　３パズル、８パズルの時と本質的に違

　　うブロックの動かし方は、６個のブロッ

　　クを飛び越える形のみで、対応する置

　　換は互換６個の積になる。

　　数列　ＡＢＣＤＥＦＧＨＩＪＫＬＭＮＯ

　　から　ＢＣＤＥＦＧＡＨＩＪＫＬＭＮＯ

　　への偶置換ということだ。

　　よって、「１５－１４」を「１４

－１５」の順に変えるだけの奇置換にはならない。すなわち、ブロック移動に

よって１４－１５パズルを標準形にすることは不可能だ。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ｑ．Ｅ．Ｄ．　（証明終了）

　　　　　　　　　☆　　　　　　　　　　☆　　　　　　　　　　☆

全く同様に、２４パズル、３５パズル、・・・、ｎ²－１パズルの場合の不可能性

も順に示せることになる。単なる２文字の入れ替え、互換に関する理論が、

パズルの世界で意外な証明能力を発揮するのだ。この辺りが、数学という

深遠な学問の醍醐味の１つだろう。

それでは、今日はこの辺で。。☆彡

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（計　２８４９字）