いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

15パズル

 15パズルというのがあります。今時はみんなあまりやらないかも知れません。Aの状態からBの状態へ、移動可能なピースを動かして変化させる、というゲームです。

f:id:Inuosann:20190924204339p:plain

Aから、「12」のピースを上の隙間に移動して、「8」を「12」が動いたあとの隙間に移動して、……などとやるわけです。ここで問題です。Aの15パズルは可能でしょうか。つまり、Aの状態からBの状態に変化させることはできるでしょうか。手元に実物があればいろいろいじることができて、難しいかな……とすぐ分かります。しかしそれでは数学的に「不可能」と断言はできません。
 以下で不可能であることを簡単に示してみます。15パズルの局面に対して、転倒数を定義します。Aで、大小順になっていないピースが何組あるでしょうか。ピースは全部で15枚、そこから2枚を取り出す組み合わせの総数は

f:id:Inuosann:20190924204750p:plain

この105通りを全部調べ、大小が逆順になっている組がいくつあるか求めるのです。ちょっと聞くと大変そうですが、そうでもありません。1と他のピースでは逆順なし。2と他のピースでは逆順なし。しかし、最後の8では逆順のものがあります。1~7はいいですが、9と8、10と8、…、15と8が逆順です。すると転倒数は7です。ある状態からピースを1回移動すると、転倒数は変化することもしないこともあります。7を右に移動しても転倒数は変化しません。つまり変化は0。左右に動かしても転倒数は変化しないのです。7でなく12を上に動かすとどうか? この場合、転倒数の変化は奇数です。9,10,11の前に12が来てしまうからです。では例えば下の図で10を上に動かすと?

f:id:Inuosann:20190924205351p:plain

この場合も転倒数の変化は奇数です。7と10との間では+1(転倒数が1増えた)、15と10との間では-1(転倒数が減った)、8と10との間では+1だからです。つまり、ピースを上下に動かすとき、転倒数の変化は奇数なのです(上下の移動では3個の駒を飛び越えることになるので、どんなときでも転倒数の変化は奇数。+1+1+1、+1+1-1、+1-1-1、-1-1-1の4通りしかなく、どれも奇数になる! (注))。
 さて、AからBへの変化では、ピースの上下の移動は偶数回のはずです。すると、AからBまでで転倒数の変化は奇数×偶数=偶数となります。しかし、Aの転倒数は奇数で、Bの転倒数は0、つまり偶数です。従ってAからどうピースを移動してもBには到達できないことが分かりました。

 代数学に置換というものがあります。並べ替えをきちんと考えます。ガロアはこれを利用して「5次以上の代数方程式には解の公式はない」を示したのでした。

(注)10が3個を飛び越えます。そのとき、全部10より小さいか、1個だけが10より小さいか、2個だけが10より小さいか、3個全部が10より小さいか、の4通りです。