平成20年秋期試験問題 午前問5

図の線上を,点Pから点Rを通って,点Qに至る最短経路は何通りあるか。
05.png

  • 16
  • 24
  • 32
  • 60
正解 問題へ
分野:テクノロジ系
中分類:基礎理論
小分類:応用数学
解説
点Pから点Rに至る最短経路の長さは4で、列挙してみると、
  • ↑↑→→
  • ↑→↑→
  • ↑→→↑
  • →→↑↑
  • →↑→↑
  • →↑↑→
の6通りになりますが、どの経路も「上方向に2回,右方向に2回」の移動を行うことは共通しています。

4回行われる移動のうち上2回の位置が決まると自動的に右2回の位置も決定することから、経路の組合せ数は、4つの中から2つを選ぶ組合せ数と同様の計算で求めることができることになります。

このことを利用すると、組合せ数を求める公式を使って

 4C24×32=6通り

と経路数を計算で求めることができます。

同様に点Rから点Qに至る最短経路数は、

 5C35×4×33×2=10通り

になります。

最終的に求める点Pから点Rを通って,点Qに至る最短経路ですが、点Pから点Rに至る6通りのそれぞれに対して、点Rから点Qに至る10通りが存在するので、

 6×10=60

正解は60通りになります。

この問題の出題歴


Pagetop