第293回 シーズン30 エピソード3

グラフ理論：偶奇の伝搬（前編）

図書室にて

テトラ「あ、先輩！　……いま、お忙しいですか？」

僕「いや、別に大丈夫だけど？」

テトラ「はい、村木先生からのお手紙です。どちらから開けますか？」

僕「村木先生からの新作問題ってことかな？　《カード》は封筒の中に入ってるの？」

テトラ「たぶん、この封筒の中に《カード》が入っているのだと思います。 二つの封筒をあたしにくださったとき、 どちらから開けてもいいけれど、必ず一つずつ開けるようにとだけ、先生はおっしゃっていましたが……」

僕「一つずつ開ける……」

テトラ「はいっ、そうです。きっと、どちらかの封筒に答えが書いてあるからですよね」

僕「うーん、僕は違うと思うなあ。 だって、最初から解答を見ちゃったらつまらないよね。 それに……いままで村木先生の問題で解答が付いてきたことなんてないよ」

テトラ「それもそうですね。ええと、あの、先輩？　先輩だったら、どっちから開けますか？　大きな封筒と、小さな封筒」

僕「そりゃ、大きな封筒だよね」

テトラ「あたしもそうです！……どうしてでしょう」

僕「大きな封筒の方が情報が多くて、易しい問題かな、と思っただけだよ。根拠はそんなにないけどね。テトラちゃんも大きな方から？」

テトラ「そうですね。大きな封筒の方が楽しいものがたくさん出てきそうなので……まずはそちらから開けたくなります」

僕「じゃあ、多数決で、大きな封筒から開けてみようか。いっしょに考えようよ」

テトラ「二人だと《多数決》と《全員一致》が同じ意味ですねっ！」

僕「確かに」

テトラ「これは……何でしょう。ずいぶん古い紙ですね。そこに線が引いてあります」

僕「何だろう。あ、でも古いのは紙の模様なんだね。きっと村木先生の演出なんじゃないかな」

テトラ「演出？」

僕「いや、何の演出かわからないけどね。あ、これ二枚重なっているよ。同じ紙かな……いや？」

テトラ「こちらには、赤い三角形がありますね。それからSTARTとGOALが書いてあります。これは……」

僕「これは……地図？」

テトラ「地図みたいです！　宝探しの地図でしょうか？」

僕「STARTからGOALまで行くってことかな」

テトラ「あっ、カードもありますよ。やっぱり村木先生のいつもの問題ですねっ！」

僕「……なるほど？」

テトラ「国々を巡遊する……ぐるっと回るってことですね。そしてスタートした国に戻ってきたときには、国境を《偶数回》越えている……でも、 いつでも《偶数》になるんでしょうか？」

僕「そこが問題なんだろうね。この《カード》では『国境を越える回数は偶数になる』と断言しているけれど、 これは『ほんとうにそうかな？』と言いたくなるよね」

テトラ「こちらの赤い三角形が描かれた地図は巡遊の一例なんですね。 STARTから、この赤い三角形に従って国境を越えて、ぐるっと回ってくる。GOALはSTARTと同じ国です。 確かに、この例だと $10$ 回で、偶数回になっています」

僕「うん、この例だと確かに偶数回になるね……いつもそうなるのかな」

テトラ「でも、『どの国から始めて、どんな道順をたどったとしても』というのは大変です！　かなりの根気が要りますよ！」

僕「そうなんだけど、すべてのパターンをたどるのは実質的に不可能だよね」

テトラ「でも、有限回ですよ」

僕「僕たちが使える時間も有限なんだけど……」

テトラ「あらら」

僕「どう考えたらいいか……」

テトラ「……」

僕「気がついたんだけど、 この地図を見ると、国境線はすべて《直線》で描かれているよね」

テトラ「ああ、確かにそうですね」

僕「だから、この地図に限定して考えるんじゃなくて、 国境線が直線になっているどんな地図でも成り立つことを証明した方がいいんじゃないかな。 つまり、《具体的な問題》を解く代わりに、《一般的な問題》を解くんだよ」

テトラ「なるほどです。《直線国境諸国巡遊偶数回横断問題》として解くわけですねっ！」

僕「いや、そんなすさまじい名前にしなくても……もっと短く《偶数回横断巡遊》としようよ」

テトラ「そうですね、失礼しました……あれ、ちょっとお待ちください、先輩。おかしいです」

僕「何が？」

テトラ「先輩は、国境線が直線になっているならどんな地図でも《偶数回横断巡遊》になるとおっしゃいましたよね。 でも、たとえば、こういう三国地図だとしたらどうでしょう。 これだと、国境横断は $3$ 回、つまり奇数ですよね？」

僕「テトラちゃんは正しいけど、この三国地図の国境は地図の端までは伸びていない。 途中で止まっていることになる。でも、村木先生の地図は地図の端までぜんぶ伸びている。 その違いはきっと大きいんじゃないかな」

テトラ「確かに、村木先生の地図の国境は地図の端まで伸びてます。あたし、よく見ているようで見てないんですね……」

僕「うん、だから、僕たちはこんなふうに問題を整理することができる」

テトラ「$n$ 本の直線で、国境を $m$ 回越える……こういう一般的な問題は、何をどう考えればいいんでしょう？　具体的な地図のときは、 根気よくがんばろう！　と思えるんですが、 $n$ や $m$ が出てくると急に不安になります」