まずは、前置きからお話します。
私が１５パズルの判定方法を初めて知ったのは、高校２年の時だったと思います。
１５パズル自体は小さい頃から知っていて（プラスチック製のものを幼稚園くらいの頃に買ってもらい、それを今でも大事に持っています）、でも、パズルを全部ばらしてから入れ直してやると、完成できる時と、出来ない時−−即ち１４−１５パズルの形になってしまう時−−があるのを、とても不思議に思っていました。
そこで、数学好きだった私は、なんとかしてその法則が見つけられないか、と、何回も何回も繰り返し１５パズルをやって、その初期配置をメモしておいて、完成できたかできなかったかをチェックしていました。
そしてある日、どうやらその法則らしきものをみつけたのです。
そう。自分で見つけたのです！
私は嬉しくなって、同じく数学好きの友人に、見つけたということとその私の見つけた方法を教えました。するとその友人は。
「えー、違うよ。『転倒数』っていうのを数えるんだよ」
えぇ〜！？
最初ははっきり言ってショックでした。自分が見つけた法則を、相手はもう既に知っていた、しかも自分の見つけたものは『違う』と指摘されたのですから。
でも、そんなはずはない。証明なんて出来ないけど、少なくとも今までのパターンの中に例外は一つも無かったのだから。
そこで私はその友人から聞いた『転倒数』という考え方と、自分の見つけた法則との間に、なんらかの相関関係がないかと調べました、そして、見つけたのです！
相関関係アリアリ(笑) その二つは、全く同値な条件だったのです！
つまり私は、その時『本当の答とは本質的に違う、間違ったもの』を見つけたのではなく、『相手が知っていた答と本質的に同じな、別の答え』を見つけたのです！
（注：『同値な条件』という数学用語を使ってしまいましたが、これは簡単に言えば『そのどちらからでも全く同じ結果が出る』ということです。
もうちょっと詳しく言うと、２つの条件が『同値』とは、『一方から他方が導かれ、かつ他方から一方が導かれる』時のことを言います）
さぁ、ここまでが前置きです。
つまりこのセクションでは、その時私が見つけた『同値な条件』を紹介しようというわけです。
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 図1.8 １５パズル（成立する例） |
|---|
９，４，６，８，７，１，...
ここまで来て、また［９］に戻ってしまいます。このように途中で同じ数字が出てきたら、今度はその数字は横に書かないで、その代わり今まで出てきた数字をカッコ（）で括ってください。 そして、今まで書いた数字の中に入っていない数字から、また同じ操作を新しくはじめてください。
また時として、数字とその位置が一致している場合があります（例１の［12］、例３の［１］や［８］など）。この時は、その数字一つだけをカッコ（）で括ってください。
最終的に、そこに書いてある１５個の数字全てが出そろいます。そうしたら終わりです。例１〜４を実際そのように書き並べてみると、次のようになります：
例１：（９，４，６，８，７，１）（３，５，10，14，13，11，15，２）（12）
例２：（３，15，13，14，６，２，１）（11，８，７，５，４）（10，12，９）
例３：（１）（９，５，３，７，６，14，12，２）（10，11，４）（８）（15，13）
例４：（６，13，９，11，15，４，10，12，２，３，８，７，５，14，１）
これを見て何か気付きませんか？
っていきなり言っても、無理でしょうね(笑) では、次の点に注目してください。
今、数字を順に辿っていって、巡回しているいくつかのグループに分けました。それらが、いくつずつの数字のグループに分かれているか、つまり、それぞれのカッコ（）の中にいくつずつ数字が書かれているか、見てみてください：
例１：６＋８＋１
例２：７＋５＋３
例３：１＋８＋３＋１＋２
例４：１５
こんな風になっています（当たり前ですが、この足し算の結果は必ず１５になります）。
ここで一つ、また新しい言葉を定義します。
上のような、カッコ（）で括った数字の列で、数字の個数が偶数のものを偶循環、奇数のものを奇循環、またそれらを総称して循環と呼ぶことにします（注：これは正式な数学用語ではありません）。また各循環の、カッコ（）の中の数字の個数を、その循環の長さと言います（注：こちらは数学用語です）。
では、例１〜４のそれぞれで、偶循環がいくつあるか見てみてください！
例１では２個（長さ６のものと長さ８のもの）と例３でも２個（長さ８のものと長さ２のもの）、例２と例４は０個です。
そう。私の見つけた法則というのは、これなのです：
その時の盤面で、偶循環が偶数個だったらその１５パズルは完成できる、奇数個だったら完成できない。
図1.1 の１５パズルの図でも確かめてください（この例では偶循環は２です）。また上の性質の後半については、１４−１５パズル（図1.2 参照）や、逆１５パズル（図1.3 参照）で確かめてみてください（それぞれ、１と７になっています、即ちどちらも奇数です）。
次回は、この方法がなぜ転倒数を数える方法と『同値』なのか、という証明をしたいと思います。
To be continued...