今回のテーマは「中国人郵便配達問題」……
なんだそりゃ？と思ったら、なかなか面白い問題でした。
･問題
下図において点Pから出発し全ての道路を通って
再びPまで戻るとき、最低何本の道路を通るのか？
マス北野と同様に、一筆書きに着目したので
今週の問題はすぐに正解が導き出せてしまいました。
考え方を記してみると、
Pを始点にして一筆書きで書くと、点Pが偶点である事、
さらに奇点が8つある事から
この図形を描く為には最低でも5本の線が必要。
5本の線の内、1本は点Pがスタートで点Pがゴールの線
残りの4本は奇点と奇点を結んだ線となります。
この残りの4本の奇点同士を結んだ線に関しては、
行った後同じ道を戻ってくれば点Pを始点･終点とした線に
含める事が出来てしまいます。
という事で、全部の線分24本に、2度通る4本を加え28本。
下の図において、左図が道路全24本を簡略化して示したもので、
一筆書きにするために4本文追加したのが右図。
この問題はP対NP問題という、アメリカのクレイ数学研究所が
賞金を賭けた『数学21世紀の7大難問』の1つの要素になっていまして、
難問への興味を誘う良問だったと思います。
中村先生によって書かれた
『数学21世紀の7大難問』の解説本が下の本。
高校生でも分かるレベルで解説されているようなので、
どんな問題なのかを知るには良い本かも。
講談社
中村 亨（著）
発売日：2004-01-21
発送時期：通常24時間以内に発送
ランキング：2962
おすすめ度：
クレイ数学研究所が賞金付きで出した問題の解説
あの有名なミレニアム問題が身近に！
PR
