[Back to the Problem Page]
[問題ページへ戻る]
ヒント
- 置換群の定理を使うと、空白の位置を元に戻すことにすれば、
自己同型群は A15 (15文字の上の交代群)であることが分かる。
それゆえ、この変形はできるはずである。
- 計算機を使えば、A15 の2つの生成元を色々と演算させることにより、
解が見つかるはずである。
(芳沢 光雄)
問題ページの Java アプレットでは、手数が膨大になってしまいます(数百程度)。
お手軽な perl スクリプトを作ってみましたので、
必要ならこちらで遊んで見てください：
15.pl
15.pl を実行後、プロンプトに対し、
「A」「a」「B」「b」「C」「c」などのコマンドを入力します。
それらの機能は実際に実行すればわかります。
これらを組み合わせたコマンドもいくつかあります。
スクリプトを見てください。終了は「x」です。
さらなる余計なお世話(^^;:
誰もがperlを使える環境にある訳でもないですので、もう少し解説します。
パズルの操作を表現する一番単純な方法は、空白の移動を記述することです。
最終的な配置になるまでに、空白は元の位置(原点とよぶことにします)に
何度か戻ることでしょう。
その際、一度原点を出てから次に原点にもどるまでの部分に着目します。
もし、途中で、ひとコマ進んですぐに後戻りするような動きがあればそれらは
キャンセルしてしまいますので、なかったものと思うことができます。
そうすると、本質的にそのような動きは
- 「A」上半分の長方形を時計回りに１周する。
- 「a」その逆。
- 「B」下半分の長方形を時計回りに１周する。
- 「b」その逆。
- 「C」外側の長方形を時計回りに１周する。
- 「c」その逆。
の６つになります。もちろんコマ自身は逆方向に動きます。
例えば、初期状態で「A」の操作を行うと下図のようになります：
[ 2][ 3][ 4][ 5] [ 3][ 4][ 5][ 6]
[ 1] [ 6] [ 2] [ 7]
[ 9][ 8][ 7] => [ 1][ 9][ 8]
[10] [15] [10] [15]
[11][12][13][14] [11][12][13][14]
そして、これらの間には
C=BA, c=ab, C13=1, ....
などの関係があります。
ただし、「積」は、一番左の操作から順番に行うものとします
(つまり普通の写像の合成と逆の書き方)。また 1 は何もしない操作を表します。
これらの操作を使って、まず、となりあう２つのコマ
(たとえば[1]と[2])を入れ換える操作を工夫してみて下さい。
もちろんその副作用として、他のコマが動いてしまうのですが、
次に同様な方法で[2]と[3]を入れ換える操作を行うことで、
他のコマの動きをもとに戻すことができるようならばいいわけです。
その他の方法もいろいろためすと、さらに短い手順のものも見つかります。
管理人自身は上の６つの操作を20回行って並べ替える方法を見つけました。
もっと短いものがあれば教えて下さい。
[webmaster@ math.josai.ac.jpにメールを下さい。]
(管理人)