最短経路問題

問題

格子状の道がある。AからBまで最短経路で行くとき、次の問いに答えよ。

$(1)\quad$ AからBへの最短経路は何通りあるか。ただし、Aから右に$5$区画、上に$3$区画の格子とする。

$(2)\quad$ 点Cを必ず通る最短経路は何通りあるか。ただし、CはAから右に$2$区画、上に$1$区画の位置にあるとする。

$(3)\quad$ 点Dを通らない最短経路は何通りあるか。ただし、DはAから右に$3$区画、上に$2$区画の位置にあるとする。

解説

最短経路問題について解説します。

最短経路問題ってどんな問題ですか？

格子状（碁盤の目のような）の道で、ある地点から別の地点まで最短距離で行く道順が何通りあるかを求める問題だよ。

場合の数の中でも頻出の問題だから、しっかりマスターしよう！

最短経路では、目的地に近づく方向にしか進みません。つまり、戻ったり遠回りしたりはしないということです。

例えば、右に$5$区画、上に$3$区画の格子で、左下のAから右上のBへ行く場合、必ず「右に$5$回」「上に$3$回」進む必要があります。

なぜ組合せで求められるんですか？

最短経路では全部で$m+n$回移動するよね。

その$m+n$回のうち、「どの回で右に行くか」を選べば経路が$1$つに決まるんだ。

だから$m+n$回から$m$回を選ぶ組合せ ${}_{m+n} \mathrm{C}_m$ になるよ。

例えば、右に$3$回、上に$2$回の場合を考えてみましょう。$5$回の移動を「右→右→上→右→上」のように並べると、これは$5$個の並びから右$(\rightarrow)$の$3$個の位置を選ぶことと同じです。

それでは問題を解いていきましょう。

AからBへ行くには、右に$5$回、上に$3$回の計$8$回移動します。

$8$回の移動のうち、右に行く$5$回を選べばよいので、

${}_{8} \mathrm{C}_5 = {}_{8} \mathrm{C}_3$ だから、小さい方の数で計算した方が楽だよ。

これは ${}_n \mathrm{C}_r = {}_n \mathrm{C}_{n-r}$ という性質を使っているんだ。

特定の点を通る最短経路は、「A→C」と「C→B」に$\textcolor{red}{分けて}$考えるのがポイントだよ。

A→Cの最短経路は、右に$2$回、上に$1$回なので、

C→Bの最短経路は、右に$5-2=3$回、上に$3-1=2$回なので、

A→Cの各経路に対して、C→Bの経路がそれぞれ$10$通りあるので、積の法則より、

「通らない」経路って、どう数えればいいですか？

こういう「〜しない」パターンは$\textcolor{red}{\text{余事象}}$の考え方を使おう！

つまり、（全体）−（Dを通る経路）で求められるよ。

まず、Dを通る最短経路を求めましょう。

A→Dの最短経路は、右に$3$回、上に$2$回なので、

D→Bの最短経路は、右に$5-3=2$回、上に$3-2=1$回なので、

よって、Dを通る経路は $10 \times 3 = 30\text{通り}$ です。

$(1)$で全体が$56$通りと求めたので、Dを通らない経路は

「通らない」→「全体から通る場合を引く」という考え方は、確率の余事象と同じ発想だよ。

場合の数でもよく使うテクニックだから覚えておこうね！

ここでは最短経路問題について学習しました。

最短経路は「右$m$回、上$n$回」の並び方と考えて ${}_{m+n} \mathrm{C}_m$ で求めることがポイントです。

特定の点を通る場合は積の法則、通らない場合は余事象の考え方を使います。

色々なパターンの問題を解いて、しっかり慣れていきましょう！