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 さん、ありがとうございます。証明にもいろいろ歴史がありそうですね!


(追記) 令和3年2月23日付け

 上記では、15ゲームが可能かどうかを判定するのに置換という言葉を用いて考えたが、
手計算で、偶置換か奇置換かを計算するのも大変である。

 あみだくじの理論を用いれば、

 上段「1、2、・・・、15」と下段「1、2、・・・、15」を線で結ぶとき、交点の数に注目しても判
定が可能である。すなわち、

  交点の個数が偶数なら出来て、奇数なら出来ない