問題プレビューID: e5a0f47a基本情報技術者試験 午前免除試験 2013年1月27日

問 3
基本情報技術者試験 午前免除試験 2013年1月27日

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

図は,左下の頂点を P,右上の頂点を Q とする縦 4 区画・横 5 区画の格子である。点 R は,P から右へ 2 区画,上へ 2 区画進んだ格子点上にある。

解説

正解は「エ」です。

最短経路は右と上への移動だけで進むので,経路の数は組合せで求められます。

  • P から R までは右へ 2 区画,上へ 2 区画の合計 4 区画であり,その経路数は (42)=6\binom{4}{2} = 6 通りです。
  • R から Q までは右へ 3 区画,上へ 2 区画の合計 5 区画であり,その経路数は (52)=10\binom{5}{2} = 10 通りです。

R を通るという条件から,求める経路数は両者の積となり,6×10=606 \times 10 = 60 通りです。

  • ア・イ・ウ: P から Q までの全経路は (94)=126\binom{9}{4} = 126 通りあり,R を通る経路だけを数えると 60 通りになります。これらの値にはなりません。

関連問題

本文が同じ・似ている問題を表示しています