[logo] Web連載「数学ガールの秘密ノート」
Share

第293回 シーズン30 エピソード3
グラフ理論:偶奇の伝搬(前編)

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} $

図書室にて

いまは放課後。ここは高校の図書室。

が数学をやっていると、後輩のテトラちゃんがやってきた。

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

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

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

テトラちゃんはそう言って、封筒を二つ、机の上に置いた。

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

村木先生は、僕たちの数学教師だ。 僕たちにときどき、数学の問題が書かれた《カード》を渡す。

いや、正確には《カード》に数学の問題が書かれているとは限らない。

単なる数式がぽつんと書かれていたり、思わせぶりな図形が描いてあったり。 僕たちはそこから自分たちで問題を作り、解いて楽しむのだ。

もちろん解けないこともある。でも、 おもしろいことがわかってレポートにまとめることもある。

それは、学校の成績とは無関係の活動だ。 レポートを出したからといって点数をもらえるわけじゃない。

僕たちは村木先生の《カード》をきっかけとして、数学を楽しんでいるのだ。

今回の封筒も……

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

は、テトラちゃんが机に置いた二つの封筒を眺める。

片方の封筒は大きめで、もう一つの封筒は小さめだ。

「一つずつ開ける……」

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

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

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

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

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

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

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

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

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

「確かに」

そんな軽口を言いながら、テトラちゃんは大きな封筒を開けた。

中から出てきたのは……

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

大きな封筒に入っていた紙

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

テトラ「演出?」

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

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

大きな封筒に入っていたもう一枚の紙

「これは……地図?」

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

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

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

大きな封筒に入っていた《カード》

多角形で表された個々の領域は「国」を表している。

一つの国から出発して、国境を越えて諸国を巡遊し、出発した国に戻ってくるとしよう。 ただし、国境を越えるときには国を表す多角形の頂点を通過してはならない。

STARTからGOALまで巡遊した例では、国境を $10$ 回越えたことになる。

地図上のどの国から始めて、どんな道順をたどって巡遊しても、国境を越える回数は偶数になる。

「……なるほど?」

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

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

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

STARTからGOALまで、赤い三角形に番号を付けた

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

テトラちゃんは地図を何回か指でなぞってみて、確かに試した範囲では偶数回になるらしいことを確認した。

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

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

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

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

テトラ「あらら」

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

テトラ「……」

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

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

国境線はすべて直線で描かれている

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

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

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

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

「何が?」

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

$3$ 回の国境横断で巡遊できる三国地図

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

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

国境は地図の端まで伸びている

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

問題

長方形で与えられた地図があり、その中に $n$ 本の直線を描く($n$ は正の整数)。

一つの国から始めて、国境を越えて隣の国に行くことを繰り返して、最初の国に戻ってくるために国境を $m$ 回越えたとする。

どこの国から始めても、どのような巡遊を行っても、 $m$ は必ず偶数であることを証明せよ。

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

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 423本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2020年6月19日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home