１５パズルで数学しよう！ 〜４〜

成立条件とその証明 後編（★★★）

　さて、後半です。後半は、『三文字置換』が大活躍します。

　まずは、次の補題から入ります：

補題２　１５パズルでは、任意の三文字置換が可能である。

　証明に入る前に、一つ注意しておきたいと思いますが、ここでは、ある場所にある数字を、他のどの場所に移動させることも可能である、という事実を証明なしに使います。でもそれは、１５パズルをもう何回もトライしてきたみなさんなら、経験則で理解できるでしょう(^^)

ａ ｂ 　 　 ｃ □ 　 　 　 ↑ ← ４手 −→ 　 　 　 　 　 ｂ ｃ 　 　 ａ ↓ 　 　 　 → □
図1.6 三文字置換の図(１)

証明：例えば、今行いたい三文字置換を(ａｂｃ)とする（即ち、今ａのあるところにｂを、ｂのところにｃを、ｃのところにａを持ってきたいとする）。
　まずこのａ，ｂ，ｃが、図1.6 のように２×２の部分ブロックの左上・右上・左下に位置していたとした時は、先程決めた、空マスの右下への移動の取り決めの、全く逆の手順によって、そのブロックの右下に空マスを持ってくることが出来る。するとそのブロックの中では、４手で三文字置換が簡単に実行できる。あとは先ほどの取り決めの通りに空白を右下に戻せば、入れ替わっているのはその三文字だけになっている。

ｂ 　 ａ 　 　 　 　 　 　 　 ｃ 　 □ −→ ａ ｂ 　 　 ｃ □ 　 　 　 ↑ 　 　 　 ↑ ← ← ４手 −→ ｂ ｃ 　 　 ａ ↓ 　 　 　 ↓ 　 　 　 → → □ −→ 　 　 　 ｃ 　 ｂ 　 　 　 　 　 　 　 ａ 　 □
図1.7 三文字置換の図(２)

　次に図1.7 のようにａ，ｂ，ｃがすべてばらばらの位置にあった時。この時、例えばａを然るべき手順によって一番左上のマスに移動させることが出来る。同様にして、ｂ，ｃをａの一つ右、ａの一つ下に移動させることも可能である。注意としては、それぞれその移動の方法を覚えておくことである。
　そしてその移動が済んだら、先程と同じようにその２×２ブロックの右下に空白を持ってくることで、その三文字に対して置換を行い、それが済んだら、先程覚えておいた、ａ，ｂ，ｃを移動した手順のまったく逆の手順を踏むことによって、ｃのあった場所にａを、ｂのあった場所にｃを、ａのあった場所にｂを戻す。すると、ａ，ｂ，ｃのみが入れ替わり、他は元の位置に戻る、即ち三文字置換（ａｂｃ）が完成する。　　□

　これは、論より証拠、実際にお手元の１５パズルで実践してみることをお勧めします。

　続いて、ここでまた新しい言葉を定義します。と言っても、これはそんなに難しくありません。
　前に、『転倒数』と言うものを考えました。これは、現状態の数字が基本状態とどれだけ入れ替わっているかと言うことで、特に０ならばそれは基本状態と同じです。ですから言ってみれば、これは『基本状態からどれだけ離れた状態か』を示す尺度の一つになっています。
　ところが、そういう尺度なら、もっと直感的なものがありますね。そうです、それが今から定義する「不一致数」です。即ち：

定義　現状態において、基本状態と位置が合致していないような数字の個数を『不一致数』と呼ぶ。

　例を挙げると、図1.1 の１５パズルは不一致数は１４（［11］のみ一致している）、１４−１５パズルは不一致数２、逆１５パズルは不一致数１４（最下段の［15］［14］［13］は一つずつ左にずれて、結果［14］だけは一致していることに注意！）です。勿論、転倒数と同じく、基本状態の不一致数は０です。
　また注意として、不一致数はパリティとは何の関係もありません。

　そして、これが一番のキーとなる命題です：

命題１　現状態が基本状態でない状態（偶置換）とする。この時、その状態に三文字置換を施した状態で、不一致数が１以上少なくなるものがある。

証明：実際に、そのような三文字置換を見つければいい。なお先ほどの補題により、どんな三文字置換も１５パズルで出来ることが保証されていることに注意。
　その状態において基本状態と位置が合致していないある数字をまず見つける。次にその場所に本来あるべき数字がどこにあるか探す。２つを見つけたら、更にもう一つ勝手な数字（これも数字と基本状態の位置が合致していないもの）を見つけ出し（注１）、この３つの数字の、この順番の三文字置換を考える。この時、合致していなかったその２番目の数字が基本状態と同じ位置に移動して合致することになり、他は合致するかまたは依然合致しないかのどちらかとなる。つまりこれは、不一致数が１以上少なくなる三文字置換である。　　□

※注１：この時３つめの数字が選び出せることは、現状態が偶置換であるということから保証される。逆にそのような３つめの数字が選び出せない状態であるとすると、基本状態と合致していない数字は、最初に選んだものと２つめに選んだものの２つだけだということになる、即ちこれは基本状態に対する『二文字置換』の状態になっており、よって奇置換である。

　ちょっと難しいかもしれません。これも、実際にお手元の１５パズルで実践されることをオススメします。

さーて、いよいよオーラス（死語）。定理１の証明です！

定理１の証明：まず後者の主張は、前半（補題１）で示した通りなので割愛する。
　前者の主張。今、現状態がある勝手な偶置換の状態だとする。すると命題１より、その状態から不一致数が１以上少ない状態に三文字置換で移行できる。三文字置換は偶置換なので、得られた新しい状態ももちろん偶置換である。
　この操作を繰り返していくことにより、不一致数はどんどん少なくなる。そして高々１５回の操作で、いつかはそれが０になるはずである。即ち、基本状態になるのである。　　□ 　

　一つだけ注記しておくと、ここで「高々」という数学特有の言い回しを使っています。これは「多くても、最高でも」という意味です。
　とにもかくにも、こうして見事、定理１の証明が出来ました！
　この定理と、今までの話を使って、いくつかの系が導き出せます。それを紹介しましょう。

系１　１４−１５パズルは完成できない１５パズルである。

証明：１４−１５パズルの状態は、基本状態に対して［14］，［15］の『二文字置換』になっている、よって奇置換である。　　□

系２　逆１５パズルは完成できない１５パズルである。

証明：逆１５パズルの初期の盤面は空マスが左下にある。これを「取り決め」に従って空マスの位置を右下に持っていくと、逆１５パズルの初期状態は、［４，３，２，１，８，７，６，５，12，11，10，９，15，14，13］となる。これは基本状態に対して、［１］，［４］、 ［２］，［３］、……、［13］，［15］の、７個の『二文字置換』として表される。よって奇数個の奇置換なので、奇置換である。　　□

系３　ある状態が完成できる１５パズルの状態だったら、その盤面を左右逆にした盤面に対する状態は完成できない１５パズルの状態である。

注：これは、『パズル成立判定の考え方』のセクションで触れた予想 『完成できない１５パズルの初期配置が見つかったら、その左右対称にしたものは完成できる！』 と全く同じ物です。

証明：現状態が完成できる１５パズルの状態ならば、偶置換である。
　ところで、系２と同じ理由により、盤面を左右逆にするということは、その状態に対して奇数回の奇置換を施すことになる（実際、ある７個の『二文字置換』を施すことになる）。よってその状態は奇置換になり、完成できない１５パズルの状態になる。　　□

　最後に、この「１５パズル」というのは、いくらでも一般化できます。
　例えば３×３のマスに８個の数字の入っている『８パズル』、同様、『２４パズル』、『３５パズル』、『９９パズル』、ｅｔｃ．　もちろんその性質から、正方形だけでなく長方形にもすることができます。つまり一般に、『ｎパズル』というものが定義できます。
　この時、定理１をそのまま一般化した、次の定理が成立します：

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

　これに関連した系も、いくつかはそのまま使えます。ただしこの場合、系２及び系３は、ｎの値（正確には、ｎを与える正方形乃至長方形の横幅）によっては成り立たないことがあります。例えば『２４パズル（サイズ５×５）』では成立しません（なぜでしょう？　考えてみてください）。

To be continued...