カエルの交換２

　＜答え＞できましたか。最小手数は15手のようです。

では、ｎ匹とｎ匹のカエルではどうなるでしょう。一般項はどのようにすれば

求められるのでしょう。

　上の、3匹のカエルの場合の表を見てわかるとおり、パターンは上下対称になっている

ことに気づきますね。つまり、無駄の無い動きであれば、上から下に向かって見た変形

と、下から上に向かって見た変形が同じものになっているはずです。これを「入れ替えの

自己双対性」と呼ぶことにしましょう。つまり、上の表の２と１４、３と１３などは互いに双対

（反転して●と×を入れ替えると同じものになる）というわけです。

　このような、対称性に着目すれば、次のような戦略でカエルを移動することができます。

まず、上表の６のような、●×が交互の状態を作る（下図参照）。

これができるまでの手数を　Ａ_３とします。

次に、この図の双対パターン

を作る。（上表では９のパターン）

６から９への手順を　Ｂ_３とする。

こうなれば、後は、６ができるまでの逆順のパターンを辿ればいいわけですから

解が得られます。すると、解までの手数は、　Ａ_３手ですね。

ということで、全体の手順は、Ａ_３＋B_３＋Ａ_３　となります。

因みに、Ａ_３＝１＋２＋３＝６、Ｂ_３＝３　ということがすぐわかります。

そこで、ｎ匹のカエルの場合に一般化することができます。

ｎ匹の場合の手数は

　Ａ_ｎ＋Ｂ_ｎ＋Ａ_ｎ＝（１＋２＋・・・＋ｎ）×２＋ｎ＝ｎ^２＋２ｎ

これが一般式になります。　　

　　　＜続く＞　＜戻る＞　＜面白数学らんど＞