最短経路の数の問題の解答

ここは、ここをクリックした先の問題の解答です。
 
【問１】
　以下の図のＡ点からＢ点まで図の格子上を縦横に進んで行く最短の経路の数を求めよ。

【解１】
　この経路の数は、以下の図のＣかＤかＥかＦを通る各々の場合毎に最短経路の数を計算して合計して求めます。

（Ｃを通る場合）

（Ｄを通る場合）

（Ｅを通る場合）

（Ｆを通る場合）

（合計）
以上の経路の数の合計は、
５＋５０＋５０＋５＝１１０通り
（解１おわり）

【解２】
　この経路の数を、以下の図のＧを通る経路も含む全部の最短経路の数から、Ｇを通る最短経路の数を引き算して求めます。

Ｇも通り得る全ての最短経路の数は、以下の図の数です。

つまり、Ｇを通る経路も含む全部の最短経路の数は、以下の様に求めます。

Ｇを通る最短経路の数は、以下の様に求めます。

Ｇを通る経路も含む全部の最短経路の数から、Ｇを通る最短経路の数を引き算します。

２１０－１００＝１１０通り
（解２おわり）

【問２】
　以下の図のＡ点からＢ点まで図の格子上を縦横に進んで行く最短の経路の数を求めよ。


【解１】
　この経路の数を、以下の図の点Ｅ，Ｆ，Ｇも通り得る全部の最短経路の数から、Ｅ，Ｆ，Ｇを通る最短経路の数を引き算して求める。

点Ｅ，Ｆ，Ｇも通り得る全部の最短経路の数は、

である。
　点Ｅを通る最短経路の数＝
(点Ａから点①までの経路の数)×(点②から点Ｂまでの経路の数)＝

である。
　点Ｆを通る最短経路の数＝
(点Ａから点①までの経路の数)×(点③から点Ｂまでの経路の数)＝

である。
　点Ｇを通る最短経路の数＝
(点Ａから点④までの経路の数)×(点③から点Ｂまでの経路の数)＝

である。
　ゆえに、点Ｅ，Ｆ，Ｇを通らずに点Ａから点Ｂまで行く最短経路の数＝
(点Ｅ，Ｆ，Ｇも通り得る全部の最短経路の数)－(点Ｅを通る最短経路の数)－(点Ｆを通る最短経路の数)－(点Ｇを通る最短経路の数)＝

である。
（解１おわり）

【解２】
　この経路の数を、以下の図の点①，Ｇも通り得る全部の最短経路の数から、①，Ｇを通る最短経路の数を引き算して求める。

点①，Ｇも通り得る全部の最短経路の数は、

である。

（１）点①を通る最短経路：

　点①を通る最短経路の数＝
(点Ａから点①までの経路の数)×(点①から点Ｂまでの経路の数)＝

である。

（２）点Ｇを通る最短経路：

　点Ｇを通る最短経路の数＝
(点Ａから点④までの経路の数)×(点③から点Ｂまでの経路の数)＝

である。
　ゆえに、点①，Ｇを通らずに点Ａから点Ｂまで行く最短経路の数＝
(点①，Ｇも通り得る全部の最短経路の数)－(点①を通る最短経路の数)－(点Ｇを通る最短経路の数)＝

である。
（解２おわり）

【問３】
　 赤玉４個、白玉３個、青玉１個がある。この中から４個を取って作る組み合わせの総数を求めよ。

【解１】
　下図の格子パターンの点Ａから点Ｂまで至る最短経路の１つが、青玉１個、白玉３個、赤玉４個から、４個の玉を選ぶ１つの組み合わせに、１対１対応する。その経路の総数が求める解である。

（解１おわり）

リンク：
高校数学の目次