15ゲームの不可能性の評価         戻る

 6 12  9  2
15  1 14 11
13  8  3  5
 4 10  7  
   左のゲームは、多分誰でも一度はやったことがあるゲーム
  でしょう。

   空きスペースを利用して、次々と数字を移動させ、最後は下
  図のように、きれいに数字を並べるというものである。

   子供のおもちゃとして、TVアニメのキャラクターに並べ替え
  るというものもある。私の手元には、以前に流行った「ダイレ
  ンジャー」のものがある。

   私が子供のころは、数字オンリーであった。適当に数字を
  バラバラにして並べ替えると、うまくいく場合といかない場合
  があることを、皆さんも経験的にご存知かと思う。

   このページでは、なぜうまくいかないのか、うまくいく場合と
  うまくいかない場合を見分けることはできないのか、について
  まとめてみたい。 
 
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  

 このゲームは、1878年アメリカのサム・ロイドが考案したもので、1879年にジョンソン、
ストーロイなどが数学的に分析し、どの場合にできて、どの場合にできないかを解決したと
いう。

 我々の目標を達成するためには、多少、数学的知識の準備が必要である。

 集合G={1,2,3,・・・,n}から集合Gへの1対1の写像σを置換という。

簡単に言えば、置換σとは、1,2,・・・,n をどう並べ替えるかの規則を表すものである。

(例)n=3のとき、置換は全部で、6個ある。(n個の文字の置換は、n!個ある。)

  (1→1,2→2,3→3) (1→1,2→3,3→2) (1→2,2→1,3→3)
  (1→2,2→3,3→1) (1→3,2→1,3→2) (1→3,2→2,3→1)

 上の例で、(1→1,2→2,3→3)のような置換は、恒等置換といわれる。これは、全て
の文字の位置が全く変わらない置換である。ここで、1→1 などのように、変換元と変換先
が同じときは、通常、省略され、(1→1,2→3,3→2)=(2→3,3→2)と書かれる。

 さらに、(2→3,3→2)は(2 3)とも書かれ、このような置換を、互換という。

 これは、2つだけの位置を交換して、その他のものは動かさない置換のことである。

 また、(1→2,2→3,3→1)のような置換は、巡回置換といわれ、(1 2 3)と書かれ
る。この場合、3個の巡回置換という。

 置換σ、τに対して、その積στが、写像の合成σ・τ(k)=σ(τ(k))として定義され
る。

(例) σ=(1→3,2→1,3→2)、τ=(1→3,2→2,3→1)のとき、

        στ=(1→2,2→1,3→3)=(1 2) となる。

置換について、以下の公式が成り立つ。

(1) 巡回置換は、互換の積で表される。

       (1 2 3 ・・・ n)=(1 n)・・・(1 3)(1 2)

(2) 置換σが、a,b,c,・・・,d 個の相異なるものの巡回置換の積で表されるとき、
  置換σは、(a+b+c+・・・+d)−n 個の互換の積で表される。

   但し、nは巡回置換の個数である。

(3) 全て互換は、ある一定の一つの番号を含む互換から作ることができる。

  (例)  (2 3)=(1 2)(1 3)(1 2)

(4) どの置換も、互換の積で表される。その表現は一意ではないが、互換の個数は
  一定である。

   ここで、互換の個数が偶数のとき、偶置換といい、互換の個数が奇数のとき、奇置換
  という。

 ある置換が与えられたとき、それが偶置換か奇置換かを判定することは、我々の目標の
ために大変大切なことなので、少し練習してみよう。

【問 題】 次の置換σ、τは、偶置換・奇置換のいずれであるか、判定せよ。

   σ=(1→2,2→3,3→5,4→1,5→4) τ=(1→3,2→1,3→5,4→4,5→2)

(解) σ=(1 2 3 5 4)=(1 4)(1 5)(1 3)(1 2) なので、偶置換である。
    τ=(1 3 5 2)=(1 2)(1 5)(1 3) なので、奇置換である。

 以上の準備の下、当初の問題について考えてみよう。

 6 12  9  2
15  1 14 11
13  8  3  5
 4 10  7  
  どんなに数字をバラバラに並べ替えても、適当な操作を行う
 と、必ず空きスペースは右下隅に置くことができる。

  従って、全ての15ゲームは、右下隅が空きスペースである
 としてよい。

  数字が順番に並べられたものを、標準形とよぶことにする。

  1回の操作で必ず空きスペースは、右下隅以外に移動する
 から、元の右下隅に戻るためには、あわせて偶数回の操作が
 必要である。

 1回の操作は、互換であり、バラバラな状態から標準形に直すためには、偶数回の操作
即ち、互換が偶数個必要ということになる。

 従って、次のような結論を得ることができる。

    15ゲームは、奇置換のとき、解決不可能である

【問 題】 冒頭の15ゲームについて、解決可能かどうか判定せよ。

(解) 置換σは、次で与えられる。

   σ=(6→1,12→2,9→3,2→4,15→5,1→6,14→7,11→8,13→9,
       8→10,3→11,5→12,4→13,10→14,7→15)

  この置換σを巡回置換の積で表すと、

   σ=(1 6)(12 2 4 13 9 3 11 8 10 14 7 15 5) となる。

  従って、σは、2個、13個の相異なるものの巡回置換の積で表されるから、上記公式
 により、置換σは、(2+13)−2=13個の互換の積で表されることになり、奇置換とな
 る。

 よって、冒頭の15ゲームは、解決不可能である。  (終)

 あまり数が大きいと検証するのが大変なので、ここでは3ゲームについて調べてみる。
3ゲームの場合、起こり得る全ての場合は、次の6通りである。

  (並べ替え可能なもの)

 

これは、
標準形である。
 

σ=(1 3 2)
 =(1 2)(1 3)
で偶置換
 

σ=(1 2 3)
 =(1 3)(1 2)
で偶置換

  (並べ替え不可能なもの)

 

σ=(2 3)
で奇置換
 

σ=(1 2)
で奇置換
 

σ=(1 3)
で奇置換

(参考文献: 淡中忠郎 著  数学の学校(東京図書)
        佐武一郎 著  線形代数学(裳華房)
        富永 晃  著  線形代数(聖文社)
        高木貞治 著  代数学講義(共立出版))

 この話題について、平成21年2月16日付けでHN「でん」さんから、次のような問い合わ
せがあった。

 15ゲームの不可能性の評価について、少々気になった事があります。

 「奇置換の時に不可能」ということに関しては納得できたのですが、それが必ずしも「偶置
換の時は可能」ということにはならないと思います。ですから、その中で出されている問題が
可能か不可能かを云う事は出来ないのではと思いました。


 この問いかけに対して、平成21年2月17日付けで

 まず、全ての15ゲームは、右下が空白の基本形の置換で得られこと。しかも、置換は互
換の積で表せること。互換の個数が奇数のとき、奇置換、互換の個数が偶数のとき、偶置
換と言い、奇置換では、基本形に帰ることはないこと。したがって、基本形に帰ることが出
来る置換は偶置換のみとなること。


を説明させていただきました。

 このことに関連して、平成21年3月1日付けで、at さんから情報をいただいた。

  すべての偶置換は基本形に帰することができる

  (→ 参考 : http://mathworld.wolfram.com/15Puzzle.html

 日本語のHPで、以下に証明があります。
          http://hp.vector.co.jp/authors/VA010128/math/puzzle/P15-3.html

(コメント) at さん、ありがとうございます。証明にもいろいろ歴史がありそうですね!