３×５の格子の長方形がある。４つの頂点で左下をｐ、右上をｑとする。

質問

３×５の格子の長方形がある。４つの頂点で左下をｐ、右上をｑとする。
ｐからｑへの最短距離の道順は、８Ｃ３通り。
これは良いとして、ｐからｑへの最長距離になる場合は何通りでそのときの距離
を求めよ。ただし、一マスは１×１とし、一度通った辺は通られないとする。
うまい数え方はあるのでしょうか。アイデアを教えてもらえればと思います。

回答No.2

osu_neko09 · ベストアンサー

３×５の格子の長方形の、辺の数は（３＊６）＋（４＊５）＝３８。
一度通った辺は通られないとするなら、結局は一筆書きですよね。
左下から、右上まで　ということは、こんな図の一筆書きをすることと同じ。

この図には奇点（図で赤い点で示す）が１６個あります。一筆書きは、奇点が０個か２個でないと書けないので、奇点を１４個減らさないといけません。

よって最低でも７本の辺を通らないのですが、左下隅、右上隅のどちらの辺を外しても、隣接していない奇点２つが残ってしまいます。よってさらにもう一本以上の辺を通り道から外す必要が出てきます。

よって、最低８本の辺を外した、距離３０が最長となります。図の緑の経路が一例です。

お礼

数学は、問題を数量化して、解くためにはアイデアが大切
なことをしみじみ感じました。ありがとうございました。

回答No.1

nattocurry

交差したり、角で接したりしても良いのでしょうか？

補足

交差したり、角で接したりしても良いとします。