第293回 グラフ理論:偶奇の伝搬(前編)

「僕」とテトラちゃんが封筒に入れられた謎の問題に挑戦! でも、封筒は二つあって……

登場人物紹介

:数学が好きな高校生。

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

$ \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \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$が出てくると急に不安になります」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに13巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 「紙の端まである直線で分けられた地図は偶数回で巡遊(2色で塗り分け)できる」ということを… https://t.co/iLT1T0OMv7 4ヶ月前 replyretweetfavorite

aramisakihime 「うわあ、なんでこんなに時間が掛かったんだろう」→私もです。うまい考えが出そうで出ないもどかしさ…。 4ヶ月前 replyretweetfavorite

012F840A_orange 独立点集合……かな 4ヶ月前 replyretweetfavorite

Lsdu2DalePerry 「別の国になる……わかった!」 今週の【僕】の言葉である。 4ヶ月前 replyretweetfavorite