« やはり急用がまた来襲・・&マラソン瀬古復帰、小保方さん反撃か | トップページ | 全記事一覧(06年7~9月) »

置換・互換と14-15パズルの不可能性~3パズル&8パズルからの証明

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

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

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

影響もある。

    

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

   

   「15パズル」の攻略法~8パズル、3パズルへの還元

   

140403b

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

  4×4=16マスからなる正方形

  の枠の中で、1~15と書かれた

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

  の配置(普通は左図)にするもの

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

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

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

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

的所有物)。

      

この15パズルを簡単にしたものが、3パズル(2×2=4マスで、3個のブ

ロック)や、8パズル(3×3=9マスで、8個のブロック)だ。以下で登場する。

     

    

         ☆          ☆          ☆

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

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

ネットで松井知己氏の小論文、『14-15パズルは何故解けないか?』の

pdfファイル(執筆当時は東大大学院)を見つけたが、その時点では読んで

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

     

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

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

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

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

   

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

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

     

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

    

     

          ☆          ☆          ☆

140403a_2

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

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

  な完成型の14と15の順序だけ

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

  究者サム・ロイドが1880年代以

  降に流行らせた(と主張してる)ら

  しい(英語版ウィキの説明)。

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

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

いう話だ。

   

140403c

  さて、ロイドは、

  上図や左のように

  14と15だけ入

  れ替えた配置の

  15パズルの解決

  に、1000ドルの

  懸賞金をかけた

  ので、人々はます

  ます熱狂。やがて、

この配置の15パズルは「14-15パズル」と呼ばれるようになったとの事。

図はネットで公開されてる、ロイドの『Cyclopedia of Puzzles』より。著作

権はもちろん消滅済み。

      

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

されてたらしい(ジョンソン&ストーリー、無料公開中、英語)。14と15だけ

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

らく全体の半数)。

     

    

          ☆          ☆          ☆ 

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

140403e

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

  ブロックの数字を読んで、数字の列(=数列)

  との4対1対応を付けるのだ。

      

     

140403q

  この場合、左の4

  つの配置はすべて、

  数列「123」と呼

  ばれることになる。    

        

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

140403g

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

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

  わる(A、B、Cは1~3の数)。

  Aが2個のブロックBCを飛び

  越えた形だ(数列で右向きに)。

       

  これは要するに、ABCの置換

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

せる。偶数個の互換になるから、元の置換は偶置換。符号(sgn)は+1だ。

           

140403h

    

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

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

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

結局2つの互換でB → A → Cとなるから、置換の B → C と一致するのだ。

       

   

         ☆          ☆          ☆

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

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

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

    

140403p_2

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

  を考えてみよう。2と3だけ、標準形

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

  するなら、その置換は1個(奇数個)

  の互換で表されるはず(下図)。

   

     

140403r

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

  (符号は-1)。偶置換が奇置

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

  ク移動(つまり偶置換)によっ

  ては実現不可能なのだ。

          

    

           ☆          ☆          ☆

140403i

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

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

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

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

  べて数列「12345678」と対応する

  (途中の図は省略、3つだけ書いた)。

   

140403j_2

      

140403k

  この時、3パズルの

  時と本質的に違うブ

  ロックの動かし方は、

  左のようなものしか

  無い。つまり、Dが

  4個のブロックEFG

  Hを飛び越えた形だ。

   

   

これは要するに、ABCDEFGHの置換であって、下のように、互換4個の

で表せる。偶数個の互換になるから、元の置換は偶置換。符号(sgn)は+1だ。

   

140403l

   

    

          ☆          ☆          ☆

元の8パズルに戻ると、結局ブロックをどう動かしても、偶数個(2個か4個)

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

置換にしかならない。

   

140403m_2

  ここで、のような配

  置変換の問題を考え

  てみよう。7と8だけ、

  標準形と入れ替えた

  もので、もし可能だと

  するなら、その置換

  は1個(奇数個)の互

  換で表されるはず

  (下図)。    

      

    

140403n_2

  つまり奇置換

  なってしまう(符

  号は-1)。偶

  置換が奇置換に

  なることはない

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

   

   

          ☆          ☆          ☆

140403o

  もはや、14-15パズルの不可能性は

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

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

   

  3パズル、8パズルの時と本質的に違

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

140403s

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

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

    

  数列 ABCDEFGHIJKLMNO

  から BCDEFGAHIJKLMNO

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

  よって、「15-14」を「14

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

よって14-15パズルを標準形にすることは不可能だ。

                                 Q.E.D. (証明終了)

      

   

         ☆          ☆          ☆

全く同様に、24パズル35パズル、・・・、n²-1パズルの場合の不可能性

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

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

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

    

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

             

                                    (計 2849字)

|

« やはり急用がまた来襲・・&マラソン瀬古復帰、小保方さん反撃か | トップページ | 全記事一覧(06年7~9月) »

ゲーム」カテゴリの記事

数学」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



« やはり急用がまた来襲・・&マラソン瀬古復帰、小保方さん反撃か | トップページ | 全記事一覧(06年7~9月) »