カエルの交換３
前ページで得られた公式
Ａｎ＋Ｂｎ＋Ａｎ＝（１＋２＋・・・＋ｎ）×２＋ｎ＝ｎ２＋２ｎ
は本当に最小値でしょうか。
実は、最近の杜陵サークル（2001.2月）で、岩手の小山中学校の佐藤宏行さん
がこのカエルパズルについて面白い話をしましたので、それを紹介したい
と思います。
|
１ |
２ |
……… |
ｎ |
ｎ |
……… |
２ |
１ |
|
|
●１ |
●２ |
……… |
●ｎ |
×ｎ |
……… |
×２ |
×１ |
図において、●ｎは、×１の場所に、●ｎ−１は×２の場所に、・・・、●１は
×ｎの場所に移動するとすれば（これが最も経済的移動とする）移動の総量は、
ｎ（個）×２（●と×）×（ｎ＋１）（移動の距離）＝２ｎ（ｎ＋１）＝２ｎ２＋２ｎ
ところが、●ｎは×１の場所に行くためには、×１〜×ｎのｎ個を飛び越えなければ
なりません。ということは、先ほどの式からｎ回分移動が減ることになります。
これが各●×に対してあるので、ｎ×２ｎ＝２ｎ２だけ減じられるのですが、飛び越える
ことによって、飛び越えられほうも「飛び越えた」ことになりますから、減ずる量は、
２ｎ２の半分ｎ２で良いことになります。以上から、最小手数は、
２ｎ２＋２ｎ−ｎ２＝ｎ２＋２ｎ となります。
以上が佐藤さんによる考え方です。これは、具体的な手順を示していませんが、移動
手順の限界値を示しています。
つまり 手順≧ｎ２＋２ｎ であるわけです。で、前ページのような手順が存在した
わけですから、前ページの戦略は最適な方法であることがいえたわけです。