15パズルで数学しよう! 〜3〜


 

成立条件とその証明 前編(★★★)

 まず、15パズルの現在の盤面を考えて、これを扱いやすい形に書き直すことを考えます(これを数学用語で表現と言います)。

 一般に、15パズルの盤面は、空マスがどの位置にあっても構いません。しかしこれでは扱いにくいので、ここんところをまずうまく書き直したいと思います。それには、空マスを常に同じ位置に置いてやればいいわけです。具体的には、空マスをいつも15パズル完成図の時のように右下に持ってくるように考えます。


図1.5 空白移動の取り決め
 例えば図1.5上 のように、空マスが一番上の左から2番目のマスにあったとします。これを右下へ持っていくのですが、その方法はいくらでもあります。そこで一つの取り決めをします。即ち、まず空マスの下にある数字を順次上に移動させることによって、空マスをその列の一番下に移動させ(図1.5中)、それから右にある数字を順次左に動かして、そうして空マスを盤面の一番右下に持っていくわけです(図1.5下)

 空マスを右下に持っていったら、今度はこの15個の数字を1列に並べることを考えます。と言っても本当に1列に並べ替える必要はなく、転倒数を数えた時と同じように、左上から始まって、その行の一番右まで行って、次の行に移ってまた右に移って、と言う要領で左上から右下までの数字を順序付けて考える、と言うことです。勿論、本当に1列に並べ替えて書き記した方が直感的で分かりやすいですね。

 ここで、一つ二つ言葉を定義します。

 今並べ替えたこの15個の数字の集まりを、その時の15パズルの盤面に対する『状態』または『現状態』と言います。
 例えば図1.1 の盤面に対応する『状態』は、[4,13,8,14,3,12,6,9,5,2,11,1,7,15,10]と書き表されます。
 またその時の転倒数を数えた時、それが奇数だったら、その状態『奇置換』偶数だったらその状態『偶置換』と言います。
 更に、15パズルの完成図に対応する状態(1〜15が、その順番に並んでいる状態ですね)を『基本状態』と呼ぶことにしましょう(注:基本状態転倒数は0、よって基本状態偶置換です)。
 すると、“具体的なパズル完成判定方法!”で述べた、15パズルの大事な性質は、次のように言いかえることが出来ます:

定理1 15パズルは、現状態偶置換なら基本状態にすることが出来る現状態奇置換なら基本状態にすることが出来ない

 そして、これからこれを証明しようと言うわけです。

 でも、まだまだ準備が必要です。まず、もう一つ、大事な考え方を導入しなければなりません。

 先程『偶置換』『奇置換』と言う言葉を導入しましたが、そもそも『置換』というのは、数学用語で「文字の列を並べ替えること」という意味です。
 つまり今考えているのは、“1”〜“15”の、15個の『文字』なのです。そして15パズルというのを、この15個の文字の並べ替えパズルだと考えているわけです。
 ここで『二文字置換』『三文字置換』という言葉を定義します。と言っても、これは簡単です。15個の文字のうちの、どれか二つ(普通は記号で“aとb”のように書きます)を入れ替える「並べ替え」『二文字置換』といいます。また15個のうちの3つの文字(aとbとc)を、その順番に(即ち、aをbに、bをcに、cをaに)置き換える「並べ替え」『三文字置換』と言います。
 同様に『m文字置換』と言うものを定義できます(mが3以上の時は、『m文字巡回置換』という方が実は正しいです、また『二文字置換』は普通は『互換』と言います)。
 今は説明のために「全部で15文字」と言うことにしていますが、勿論何文字でも(一般に n文字 とよく書きます)同じことが言えます。
 例を挙げると、n=3として、[1,3,2]は([1,2,3]の)『二文字置換』(記号 (23) であらわします)、[2,3,1]は([1,2,3]の)『三文字置換』(記号 (123) であらわします)です。

 ではここで、宿題です(笑)
 次の事柄を示してみてください:
二文字置換(互換)奇置換三文字置換偶置換である。」
 ヒントは、二文字置換の場合は具体的に「転倒数」がどう変るかと言うことを計算してみてください。また三文字置換は、実は「2つの二文字置換の合成」だと考えることが出来ます(ちょっと難しいかな(^^;)。でもその事実さえ意味が分かれば、奇置換奇置換偶置換になる、というわけです。

 では続いて、次の補題を考えます:

補題1 現状態偶置換(resp. 奇置換)ならば、そこから何手か進めた15パズルの盤面に対応する状態偶置換(resp. 奇置換)である。

証明:15パズルでは、一手進むごとに空マスの位置が一つずつずれる。今、空マスの位置を座標で(x,y)とあらわすとする。一つの状態に対応する、空白が右下に位置されている盤面においては、即ち空マスの位置は(x,y)=(4,4)となる。特に x+y = 4+4 は偶数である。そしてすぐに分かるように、そこから空マスの位置が一つずれる毎に、x+y は偶数と奇数が交互に現れる。そして巡りめぐって、空マスがまた右下に来た時、今までの話からそれは偶数手目であることが分かる(分かりますよね)。
 ところで、「空マス」を“第16の文字”と見て、空マスの移動を「16個の文字の置換」に見立ててみる。すると、空マスの一回の移動は「空マスと、そこに隣り合っている数字との『二文字置換』である」と言うことが出来る。そして空マスが元の右下の位置に戻った時、今見たように偶数回の移動があったことになるのだから、この時の置換「偶数回の『二文字置換』だと言い表すことが出来る。
 よって、現状態偶置換(resp. 奇置換)ならば、そこから何手か進めた状態は、偶置換(resp. 奇置換)+(偶数回の奇置換)=偶置換(resp. 奇置換) である。  □

 どうですか? 見事でしょう(^^)

 ところで、これは何を意味しているのか、と言うと。実は、[定理1]の二つの主張のうちの、後者。「現状態奇置換なら基本状態にすることが出来ない。」をこれで示してしまったことになるのです。
 こう考えてください。現状態がある奇置換状態だったとしたら、そこから何手か進めた状態は、この補題2から必ず『奇置換』状態にならなければならないのです。ところが先程注意したように、基本状態『偶置換』なのです。マル。

 では、後半は定理1の前者の主張を示してみたいと思います。

To be continued...



Back        Next


ご意見・ご感想は、 感想専用掲示板 または メール でお願いします。

パズル&数学館へ戻る

antimon@opal.famille.ne.jp