置換・互換と14-15パズルの不可能性~3パズル&8パズルからの証明
今年に入って、大学レベルの行列、線型代数の数学記事を3本書いた。こ
れはたまたま、引越しパニックによって他の理数系の本が見当たらなくなっ
たという個人的理由が大きいのだが、前からずっと気になってたパズルの
影響もある。
当サイトでは3年半前、有名なパズルに関する論理的考察の記事を書いた。
「15パズル」の攻略法~8パズル、3パズルへの還元
15パズルとは、左のようなもの。
4×4=16マスからなる正方形
の枠の中で、1~15と書かれた
15個のブロックを動かして、目的
の配置(普通は左図)にするもの
だ。知ってる人も多いと思う。数字
の代わりに絵を使って、ジグソー
パズルみたいにした物もある。
この図と次の図(少し下)は、ウィキメディアで公開中、パブリックドメイン(公
的所有物)。
この15パズルを簡単にしたものが、3パズル(2×2=4マスで、3個のブ
ロック)や、8パズル(3×3=9マスで、8個のブロック)だ。以下で登場する。
☆ ☆ ☆
さて、3年半前の記事では、「解けない問題」の存在に触れて、線型代数を
使えば解けないことが数学的に証明できるとだけ書いておいた。その際、
ネットで松井知己氏の小論文、『14-15パズルは何故解けないか?』の
pdfファイル(執筆当時は東大大学院)を見つけたが、その時点では読んで
も何となくしか分からなかったので、パスしたままだったのだ。
先日、置換と互換の記事を書いた後、試しに自分で考えてみたら、あっさり
証明成功。その後、松井氏のファイルや日米のウィキペディアを読み直して
みて、私なりにもっと分かりやすく説明する価値があるなと思ったので、以
下、理論的にも歴史的にも遡って、書いてみよう。
置換と互換の知識は前提とするので、知らない方はまず次の記事の前半
だけでも御覧あれ。高校数学の行列を知らなくても、大体理解できると思う。
置換・互換による行列式の定義~初心者向け
☆ ☆ ☆
ではまず、「解けない問題」の代
表例を見てみよう。左は、標準的
な完成型の14と15の順序だけ
替えたもので、米国のゲーム研
究者サム・ロイドが1880年代以
降に流行らせた(と主張してる)ら
しい(英語版ウィキの説明)。
そもそも15パズル自体、ロイドの発明だと本人は語ってるとの事。詳細は
不明だが、いずれにせよ19世紀後半の米国が、15パズルの発祥の地と
いう話だ。
さて、ロイドは、
上図や左のように
14と15だけ入
れ替えた配置の
15パズルの解決
に、1000ドルの
懸賞金をかけた
ので、人々はます
ます熱狂。やがて、
この配置の15パズルは「14-15パズル」と呼ばれるようになったとの事。
図はネットで公開されてる、ロイドの『Cyclopedia of Puzzles』より。著作
権はもちろん消滅済み。
ところが、これが解決不可能であることは、既に1879年の数学論文で証明
されてたらしい(ジョンソン&ストーリー、無料公開中、英語)。14と15だけ
を入れ替えることは出来ないし、他にも解けない配置は多数あるのだ(おそ
らく全体の半数)。
☆ ☆ ☆
では、3パズルから、不可能性の証明を始めよう。まず、ブロックの配置に名
前を付けるのがポイント。左のような順番に
ブロックの数字を読んで、数字の列(=数列)
との4対1対応を付けるのだ。
この場合、左の4
つの配置はすべて、
数列「123」と呼
ばれることになる。
よって、数列が変わるようなブロックの動かし方は、左側で上下に動かすも
のしかない。上から下に動か
す場合、左のように数列が変
わる(A、B、Cは1~3の数)。
Aが2個のブロックBCを飛び
越えた形だ(数列で右向きに)。
これは要するに、ABCの置換
(並べ替え)であって、下のように、互換(2つだけの入れ替え)2個の積で表
せる。偶数個の互換になるから、元の置換は偶置換。符号(sgn)は+1だ。
ちなみに、カッコ内の上下2行は、上から下への入れ替えを表す。また、互
換も含めて、置換の積(掛け算)は右から考えるので、念のため。Bの場合
だと、まず右側の互換によってAになり、次に左側の互換によってCになる。
結局2つの互換でB → A → Cとなるから、置換の B → C と一致するのだ。
☆ ☆ ☆
元の3パズルに戻ると、左側で下から上にブロックを動かしても同じこと。結
局、ブロックをどう動かしても、偶数個の互換を積み重ねて行くだけだから、
結果的には偶数個の互換。つまり偶置換にしかならない。
ここで、左のような配置変換の問題
を考えてみよう。2と3だけ、標準形
と入れ替えたもので、もし可能だと
するなら、その置換は1個(奇数個)
の互換で表されるはず(下図)。
つまり奇置換になってしまう
(符号は-1)。偶置換が奇置
換になることはないので、ブロッ
ク移動(つまり偶置換)によっ
ては実現不可能なのだ。
☆ ☆ ☆
同様の考え方で、8パズルの不可能性
も証明できる。今回は左のようにブロッ
クの数字を読んで、数列と対応させよう。
この場合、下のような9種類の配置はす
べて数列「12345678」と対応する
(途中の図は省略、3つだけ書いた)。
この時、3パズルの
時と本質的に違うブ
ロックの動かし方は、
左のようなものしか
無い。つまり、Dが
4個のブロックEFG
Hを飛び越えた形だ。
これは要するに、ABCDEFGHの置換であって、下のように、互換4個の
積で表せる。偶数個の互換になるから、元の置換は偶置換。符号(sgn)は+1だ。
☆ ☆ ☆
元の8パズルに戻ると、結局ブロックをどう動かしても、偶数個(2個か4個)
の互換を積み重ねて行くだけだから、結果的には偶数個の互換。つまり偶
置換にしかならない。
ここで、左のような配
置変換の問題を考え
てみよう。7と8だけ、
標準形と入れ替えた
もので、もし可能だと
するなら、その置換
は1個(奇数個)の互
換で表されるはず
(下図)。
つまり奇置換に
なってしまう(符
号は-1)。偶
置換が奇置換に
なることはない
ので、ブロック移動(つまり偶置換)によっては実現不可能なのだ。
☆ ☆ ☆
もはや、14-15パズルの不可能性は
明らかだろう。左のようにブロックの数
字を読んで、数列と対応させる。
3パズル、8パズルの時と本質的に違
うブロックの動かし方は、6個のブロッ
クを飛び越える形のみで、対応する置
換は互換6個の積になる。
数列 ABCDEFGHIJKLMNO
から BCDEFGAHIJKLMNO
への偶置換ということだ。
よって、「15-14」を「14
-15」の順に変えるだけの奇置換にはならない。すなわち、ブロック移動に
よって14-15パズルを標準形にすることは不可能だ。
Q.E.D. (証明終了)
☆ ☆ ☆
全く同様に、24パズル、35パズル、・・・、n²-1パズルの場合の不可能性
も順に示せることになる。単なる2文字の入れ替え、互換に関する理論が、
パズルの世界で意外な証明能力を発揮するのだ。この辺りが、数学という
深遠な学問の醍醐味の1つだろう。
それでは、今日はこの辺で。。☆彡
(計 2849字)
| 固定リンク | 0
「ゲーム」カテゴリの記事
- パズル「絵むすび」23、解き方、考え方(難易度3、ニコリ作、朝日be、22年7月16日)(2022.07.17)
- パズル「推理」、小学生向け6、表の書き方(難易度4、ニコリ作、朝日be、22年7月2日)(2022.07.03)
- 3種類の絵だけ通る迷路パズルの考え方、解き方(難易度4、ニコリ作、朝日新聞be、22年6月25日)(2022.06.26)
- パズル「絵むすび」22、解き方、考え方(難易度4、ニコリ作、朝日be、22年5月21日)(2022.05.21)
- パズル「絵むすび」21、解き方、考え方(難易度2、ニコリ作、朝日be、22年3月19日)(2022.03.19)
「数学」カテゴリの記事
- 昭和レトロの「5玉そろばん」、鉄道員が時間(分)の60進法の計算をする時の玉の動かし方♪(2022.07.23)
- パズル「絵むすび」23、解き方、考え方(難易度3、ニコリ作、朝日be、22年7月16日)(2022.07.17)
- パズル「推理」、小学生向け6、表の書き方(難易度4、ニコリ作、朝日be、22年7月2日)(2022.07.03)
- 3種類の絵だけ通る迷路パズルの考え方、解き方(難易度4、ニコリ作、朝日新聞be、22年6月25日)(2022.06.26)
- パズル「絵むすび」22、解き方、考え方(難易度4、ニコリ作、朝日be、22年5月21日)(2022.05.21)
コメント