最短経路

2017年12月21日

最短経路の問題です。

1.(東北大)
右の図のように,道路が碁盤の目のようになった街がある.地点Aから地点Bまでの長さが最短の道を行くとき,次の場合は何通りの道順があるか.
(1) 地点Cを通る.
(2) 地点Pは通らない.
(3) 地点Pおよび地点Qは通らない.

少し変わった問題を2つ。

2.(岩手大)
ある町には,図のように東西に6本の道と南北に7本の道がある.
(1) P地点からQ地点まで行く最短経路は何通りあるか.
(2) P地点からQ地点まで行く最短経路のうち,右折の回数と左折の回数の合計がちょうど8となるのは何通りあるか.

解答

3.(山口大)
図のように東西に6本,南北に10本の道がある.東西の道と南北の道の出会う地点を交差点とよび,隣どうしの交差点を結ぶ道を区間ということにする.A地点からB地点に進むとき,次の問いに答えなさい.ただし,その交差点においても,東西および北のいずれかに進むことはできるが,南に進むことはできないものとする.また,後戻りもできないとする.図の太線は道順の例を示したものである.
(1) A地点からB地点へ行く道順の総数を求めなさい.
(2) C地点を通って,A地点からB地点へ行く道順の総数を求めなさい.
(3) A地点からB地点まで16区画で行く道順の総数を求めなさい.

次にカタラン数に関わる問題です。次の問題はカタラン数が現れる1つの例ですが、カタラン数は色々なところに現れます。

4.(立命館大)
(1) 図1-①,図2は,正方形の土地の各辺を5等分して作った東西(右左)に6本,南北(下上)に6本の道を表したもので,その上に図2は,対角線AB(道でない)を引いたものである.この道を通る経路について,次の問いに答えよ.
(ア) 図1-①において,AからEを通ってBへ行く最短経路は何通りあるか.
(イ) 図1-②は,(ア)の経路において,EからBへ行く経路を,図の点線を軸に対称移動させたものであり,BはCに移る.この図において,AからEを通ってCへ行く最短経路は何通りあるか.

 
(ウ) 図2において,対角線ABより南側を通らないで,AからBへ行く最短経路は何通りあるかを考える.図3-①の太線は,対角線ABより南側を通る経路の例を示している.この経路は,どこかで対角線ABより南側の点線A’B’と必ず交わる.交わった点をPとする.Pから先の経路を点A’B’を軸に対称移動させたものが図3-②の太線である.
(ⅰ) AからBへ行く最短経路のうち,図3-①の太線の例のように,対角線ABより南側を通る最短経路は何通りあるか.
(ⅱ) 対角線ABより南側を通らないで,AからBへ行く最短経路は何通りあるか.


(2) 図4は,正方形の土地の各辺をn等分して作った東西(右左)に(n+1)本,南北(下上)に(n+1)本の道を表したものである.この道を通り,対角線ABより南側を通らないで,AからBへ行く最短経路は何通りあるか.

最後に3次元に拡張した問題です。

5.(名古屋市立大)
同じ大きさの立方体を12個積んでできた直方体を図に示す.頂点Aから頂点Bまで立方体の辺を通って最短距離で進むものとする.
(1) 進み方は全部で何通りあるか.
(2) 直方体の内部を少なくとも1度は通る進み方は何通りあるか.
(3) 頂点P, Q, Rのいずれも通らない進み方は何通りあるか.

関連ブログはこちら
にほんブログ村 教育ブログへ にほんブログ村 受験ブログへ