１５ゲームの不可能性の評価　　　　　　　　　

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

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

　集合Ｇ＝｛１，２，３，・・・，ｎ｝から集合Ｇへの１対１の写像σを置換という。

簡単に言えば、置換σとは、１，２，・・・，ｎ をどう並べ替えるかの規則を表すものである。

(例）ｎ＝３のとき、置換は全部で、６個ある。(n個の文字の置換は、ｎ！個ある。）

　　（１→１，２→２，３→３）　（１→１，２→３，３→２）　（１→２，２→１，３→３）
　　（１→２，２→３，３→１）　（１→３，２→１，３→２）　（１→３，２→２，３→１）

　上の例で、（１→１，２→２，３→３）のような置換は、恒等置換といわれる。これは、全て
の文字の位置が全く変わらない置換である。ここで、１→１ などのように、変換元と変換先
が同じときは、通常、省略され、（１→１，２→３，３→２）＝（２→３，３→２）と書かれる。

　さらに、（２→３，３→２）は（２　３）とも書かれ、このような置換を、互換という。

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

　また、（１→２，２→３，３→１）のような置換は、巡回置換といわれ、（１　２　３）と書かれ
る。この場合、３個の巡回置換という。

　置換σ、τに対して、その積στが、写像の合成σ・τ（ｋ）＝σ（τ（ｋ））として定義され
る。

（例）　σ＝（１→３，２→１，３→２）、τ＝（１→３，２→２，３→１）のとき、

　　　　　　　　στ＝（１→２，２→１，３→３）＝（１　２） となる。

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

（１）　巡回置換は、互換の積で表される。

　　　　　　　（１　２　３　・・・　ｎ）＝（１　ｎ）・・・（１　３）（１　２）

（２）　置換σが、ａ，ｂ，ｃ，・・・，ｄ 個の相異なるものの巡回置換の積で表されるとき、
　　置換σは、（ａ＋ｂ＋ｃ＋・・・＋ｄ）−ｎ 個の互換の積で表される。
　　　但し、ｎは巡回置換の個数である。

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

　　（例）　　（２　３）＝（１　２）（１　３）（１　２）

（４）　どの置換も、互換の積で表される。その表現は一意ではないが、互換の個数は
　　一定である。
　　　ここで、互換の個数が偶数のとき、偶置換といい、互換の個数が奇数のとき、奇置換
　　という。

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

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

　　　σ＝（１→２，２→３，３→５，４→１，５→４）　τ＝（１→３，２→１，３→５，４→４，５→２）

（解）　σ＝（１　２　３　５　４）＝（１　４）（１　５）（１　３）（１　２） なので、偶置換である。
　　　　τ＝（１　３　５　２）＝（１　２）（１　５）（１　３） なので、奇置換である。

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

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

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

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

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

（解）　置換σは、次で与えられる。

　　　σ＝（６→１，１２→２，９→３，２→４，１５→５，１→６，１４→７，１１→８，１３→９，
　　　　　　　８→１０，３→１１，５→１２，４→１３，１０→１４，７→１５）

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

　　　σ＝（１　６）（１２　２　４　１３　９　３　１１　８　１０　１４　７　１５　５）　となる。

　　従って、σは、２個、１３個の相異なるものの巡回置換の積で表されるから、上記公式
　により、置換σは、（２＋１３）−２＝１３個の互換の積で表されることになり、奇置換とな
　る。

　よって、冒頭の１５ゲームは、解決不可能である。　　（終）

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

　　（並べ替え可能なもの）

　　（並べ替え不可能なもの）

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

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

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

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

　この問いかけに対して、平成２１年２月１７日付けで

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

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

　このことに関連して、平成２１年３月１日付けで、ａｔ さんから情報をいただいた。

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

　　（→　参考 ： http://mathworld.wolfram.com/15Puzzle.html ）

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

（コメント）　ａｔ さん、ありがとうございます。証明にもいろいろ歴史がありそうですね！


（追記）　令和３年２月２３日付け

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

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

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

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