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

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

石兵八陣、迷路脱出法

 三国志に「石兵八陣(せきへいはちじん)」というのが出てきます。三国志というのは古い中国の魏、呉、蜀の物語。漢の終わり頃から三国時代、晋の始めまでの話です。自分の作戦ミスで呉の陸遜(りくそん)に追い詰められる前線の劉備玄徳(りゅうびげんとく)。蜀の軍師、諸葛孔明(しょかつこうめい)は馬良(ばりよう)に「魚腹浦(ぎょふくほ)には伏兵10万を置いてきた。陸遜をそこへおびき出せば捕らえることができる」と言います。孔明は蜀軍が破れたときのために石兵八陣を仕掛けておいたのです。馬良はそこへは何度も行っており、伏兵などいなかったことを知っているので訝(いぶか)ります。よくわからないのですが、これは孔明が大小の岩を積んで作った迷路みたいなものらしく、「強い殺気を感じる」と怪しんだ陸遜がそこへ迷い込みます。迷路になっているだけでなく、ときどき風が吹いたり海の水が入り込んだり、助けが入らなければ陸遜は命を落としていました。たくさんありますが、三国志の中の好きな場面のひとつです。
 さて、というわけで今回は迷路の話です。「迷路からの抜け出し方」として「右側の壁に触れながら進めばいい」というのが有名ですよね。しかし、これはうまくいかないこともあります。分かると思いますが、触れた壁が迷路の真ん中あたりで島になっている場合です。この方法は、触れた壁が出口までつながっていないと使えない、ってことです。数学の中にもっとちゃんとした脱出法(定理)があるので、紹介しましょう。これを使えば、どんな迷路からでも必ず脱出できます。歩きながら道や分岐点にマークをつけることが可能であれば、次の(1)~(3)に従って歩くと必ず迷路を抜け出せます。迷路のどこからスタートしても構いません。

f:id:Inuosann:20191018222521p:plain
 ひとつ心配なことがあります。「(3)の(c)で、1度しか歩いていない道がなかったらどうなるのか?」ということです。でも大丈夫。そんなことが起こるのは「この迷路は脱出不可能」なときなのです。いや、脱出できないんだから「大丈夫」じゃあないけれど、仕方ありません。周りを隙間なく壁で囲まれているような迷路だとどう歩いても抜け出せませんよね。そういう迷路は、歩いているうちにこのケースに当てはまる瞬間が来るわけです。
 定理なんだから証明もあります。すみません、ぼくは確認してませんが、分岐点の数に関する数学的帰納法で証明できるとか。この脱出法は20年以上前、多分一松信(ひとつまつしん)先生の一般向けの著書だったかと思うんですが、それで読みました。証明は書いてなく、「どうやればいいんだろう?」と疑問でした。まだ解決していませんが、そのうち。