子蜘蛛の蟻ハンティング練習(解答)

　子蜘蛛が1匹だけでは，たとえ蟻と同じ速さで走れても，決して蟻を捕まえることができないのは明らかである。これは子蜘蛛が2匹の場合でも同じことで，蟻はなるべく頂点にいるようにして，子蜘蛛のうちの1匹が危険なほど近づいたら2方向ある逃げ道から，原則もう1匹の子蜘蛛から遠ざかる方向を選んで逃げさえすれば，（蟻が子蜘蛛よりほんの少しでもスピードで勝っていれば）捕まることはなさそうだ。

　だが，ハンターが3匹になると，ことは微妙になる。蟻が頂点にいたとしても，その頂点に隣接する3つの頂点すべてを3匹の子蜘蛛にそれぞれ占有されてしまうと万事休すだ。子蜘蛛たちは，そこからゆっくりと蟻に近づいていっても，逃げ道の3方向をすべてふさいでいるので，やがて蟻を捕獲することができる。

　だが蟻の側から戦略を考えると，子蜘蛛たちがそのような包囲網を作ろうとしたとき，それが完成する前に蟻がスピード差を生かして別の頂点に移動できればよい。そうなるとその試みは破綻する。

　実は，この賭け引きは（子蜘蛛が蟻の1/3以上のスピードを出せれば）子蜘蛛のほうに勝ち目があるのだが，その戦略は，単に3匹で逃げ道をふさぐというものよりはもう少し複雑になる。下図をご覧いただきたい。

　子蜘蛛のうち1匹は辺AEを占拠し，そこに蟻が入り込まないようにガードする。これは難しくないだろう。例えば，この子蜘蛛は点Aから辺AEに入り，点Eに向かって進んでいけば，辺AE上に蟻がいたとしても，やがて点Eから逃げ出さなければならなくなる。

　ここで（辺AEを使わない限り）点Aと点Eを結ぶルートの道のりはどれもAEの3倍以上であることに注意されたい。従って，その後にまた蟻が点Aや点Eに到達しようとしても，子蜘蛛は蟻の1/3の速さで動けるのだから，蟻の動きに応じて自分の位置を調整し，蟻が点Aや点Eに到達した場合には少なくとも同時に自分もそこに到達できるように辺AE上を動くことができる。よって辺AEをガードされると蟻は二度と点Aと点Eを通ることができなくなる。

　同様に，もう1匹の子蜘蛛が辺CGを占拠しガードする。そこからも追い出された蟻は，もう二度と点Cと点Gを通れなくなるのがミソだ。

　これで罠の設置は完了である。残った1匹の子蜘蛛はゆっくりでいいから，蟻を単純に追っていけばよい。蟻は辺AEと辺CGには入り込めないから，上図で点線で描いた辺上を逃げるしかないが， これらは点A，点E，点C，点Gを含むループしか持たないので， やがてそのどれかを通過するハメになり，待ち構えていた（あるいは同時にそこに到達した） 子蜘蛛に捕獲される。

　これで，うまくやればこの勝負は子蜘蛛たちの勝ちになることがおわかりいただけたと思うが，もっと早く蟻を捕まえる戦略はあるだろうか？　また，子蜘蛛のスピードが蟻の1/3未満の場合はどうだろう？　その場合は，蟻が逃げ切れるだろうか，それともやはり子蜘蛛の側に別の有効な戦略があるだろうか？　上述の戦略では，2辺を占拠する子蜘蛛は蟻の1/3のスピードが要求されるが，蟻を追い回す3匹めの子蜘蛛はのんびり屋でもかまわない。いろいろと条件を変えてこの問題を考えてみるのも面白いかもしれない。