酔いつぶれて録画予約を失敗してしまった「コマネチ大学数学科」だが、上記のブログに問題と、非常に丁寧な解説が載っていた。詳細は上記ブログを参照してもらうとして、酔っ払い爺としては、実践あるのみ。ホントにそうなのかを検証してみよう。
「スタート」ボタンを押してから、キーボードの方向キーで郵便配達夫を操作してほしい。
問題は「郵便局から出発して、すべての家に郵便物を配達し、再び、郵便局に戻る、この間の移動距離が最小となるような経路を見つけよ!というもの。小さいひとマスの辺を「1」としたとき、最短経路の移動距離を求めることになる。
で、経路を最短にするには、できるだけ、同じ道を通らないこと。一筆書きができれば(無駄な移動を省くという意味で)それに越したことはないのだが、どうやら、この図形は一筆書きができない。ならば、どうすればよいのか、というのが、この問題のポイントだ。
重複して通る経路をどこにするか。「ケーニヒスベルクの橋」問題で、オイラーは、一筆書きができる必要十分条件として、「すべての頂点の次数が偶数」または「次数が奇数の頂点の数が2で、残りの頂点の次数はすべて偶数」のいずれかとした。つまり、奇数点を偶数にすれば、いいんだよね。そう考えると、自ずとバイパスを設置するポイントが見えてくる。
そんなわけで、パターンを知ってしまうと、意外と簡単な問題。このバイパスを設置する(二度通る経路を決める)と、スタート地点がどこにあろうが、最短距離ですべての家に郵便物を配達できる。この問題の答え(1マスの辺を1とすると)、最短距離「28」で、すべての家に郵便物を届け、出発点の郵便局に戻ってほしい。
初めまして、シャブリです。
TBありがとうございました。
私の偏狭ブログを見つけてくださり、
こんな形で紹介されて、いやはや、とても嬉しい限りです。
早速、ゲームをやりました。よく出来てますね。
答えを知っているので、いろんな道順で試してみて楽しみましたよ!(resetはre-loadで…)
コマネチ大学は初回から見ていたのですが、きちんと書き留めるようになったのは最近なのです。
ブログにUPできるのは今年の分だけかと思いますが、どうぞ贔屓にして下さい。
これからも宜しくお願いいたします。
(こちらからもTBさせていただきますね)
I appreciate in your usual cooperation.
Best Regards,Chablis
コマネチ大学 #33
たけしのコマネチ大学 2007/01/11OA
今回のテーマは、
「中国人 郵便配達問題」
文化大革命の最中、郵便局に配属された中国人クワン・メイ・コウ(間違ってるかも..)が中国の数学雑誌に記事を書いた問題。
アメリカ人、アラン・ゴールドマンがこのような名前を付けたとされて…