最短経路問題の応用（池がある場合）の解き方とは【わかりやすく解説】

こんにちは、ウチダです。

いつもお読みいただきましてありがとうございます。

さて、いきなりですが、最短経路問題（場合の数）は

1. $A$ → $C$ → $B$
2. $C$ を通らずに $A$ → $B$
3. $C$ も $D$ も通らずに $A$ → $B$
4. 池がある場合

以上、主に $4$ パターンの応用があります。

ただ、この中で特に「池がある場合」。

この問題がかなり難しいのですが…

実はとっておきの解法があります！！

よって本記事では、最短経路問題の基本から応用まで

• 東北大学理学部数学科卒
• 教員採用試験に１発合格　→　高校教諭経験アリ
• （専門は確率論でした。）

の僕がわかりやすく解説します。

最短経路問題のテクニカルな解き方とは【「和の法則」を使います】

具体的な問題は後で解くとして、いきなりですがテクニカルな解法をご紹介します。

このテクニカルな解法は、

• $1$ 通りしか道順がないものに「 $1$ 」と記す。
• 図のように、和の法則を使って求めていく。

以上 $2$ 点を守れば、意外と簡単に使えます。

よって、$B$ 地点までの最短経路の総数は「 $35$ 通り」と求まりました。

一応当たっているか、通常の解法で確認すると…

$$\frac{7!}{4!3!}={}_7{C}_{3}=\frac{7・6・5}{3・2・1}=35 (通り)$$

と、確かに一致してますね！

[ふきだし set=”ウチダ”]通常の解法というのは、「同じものを含む順列」の考え方を利用した方法になります。「通常の解法がよくわからない…」という方は、「同じものを含む順列と組合せは”同じ”です【問題４選もあわせて解説】」の記事からご覧いただくと、よりスムーズに理解できると思いますよ。[/ふきだし]

さて、一見すると「同じものを含む順列」の考え方を利用した解法の方がスマートな気がします。

しかし、繰り返しになりますが「池がある問題」。

これだけは、このテクニカルな解法が非常に役に立つんですね～。

最短経路問題４選を実際に解いてみよう

ここからは、実際に最短経路問題を基本から発展まで解いていくことにします。

最初は基本のお話なので、もしすっ飛ばしたいという方がいらっしゃいましたら、以下のリンクをクリックしてください。

• １問目　… 　$A$ → $Ｃ$ → $Ｂ$ （基本）
• ２問目　… 　$C$ を通らない（少し応用）
• ３問目　… 　$C$ も $D$ も通らない（まあ応用）
• ４問目　… 　池がある最短経路問題（発展）

※「 $〇$ 問目」の部分がリンクになっており、クリックすると問題にジャンプします。

Ａ→Ｃ→Ｂの最短経路問題

問題１．下の図のような格子状の道路がある。このとき、以下の問いに答えよ。
(1)　交差点 $A$ から交差点 $B$ までの最短経路は何通りあるか。
(2)　(1)の中で、交差点 $C$ を通る場合の数を求めよ。

(1)は先程もご紹介した、最も基本となる問題です。

(2)は少しテクニックがいりますね。

【解答】

(1)　→ $5$ 個、↑ $3$ 個の順列の総数を求めればよいので、$$\frac{8!}{5!3!}={}_8{C}_{3}=56 (通り)$$

(2)　以下の $2$ つに分けて求める。

• ⅰ）… $A$ → $C$ の場合の数
• ⅱ）… $C$ → $B$ の場合の数

そして、最後に積の法則を用いて掛け算すればOK。

ⅰ）　$A$ → $C$ の場合の数

→ $3$ 個、↑ $1$ 個の順列の総数を求めればよいので、$\displaystyle \frac{4!}{3!}=4$ 通り。

ⅱ）　$C$ → $B$ の場合の数

→ $2$ 個、↑ $2$ 個の順列の総数を求めればよいので、$\displaystyle \frac{4!}{2!2!}=6$ 通り。

したがってⅰ）ⅱ）より、$4×6=24$ 通りである。

(解答終了)

(2)は区画整理（？）をすればわかりやすくなりますね！

色付き以外の部分は考えなくていい、ということになります。

Ｃを通らない最短経路問題

問題２．下の図のような格子状の道路がある。このとき、交差点 $C$ を通らない場合の数を求めよ。

問題１と道路は同じです。

今度は、$C$ を“通らない”場合の数を求めてみましょう。

↓↓↓

【解答】

通らない場合の数は、全体の場合の数から通る場合の数を引けばOK。

よって、問題１．(1)(2)より、$56-24=32$ 通りである。

(解答終了)

基本的に、何かを否定している場合の数を求めるときは、

（全体の場合の数） $-$ （肯定の場合の数）

が最適な解法です。

[ふきだし set=”ウチダ”]以上 $2$ 問が、最短経路問題の必ず押さえたい基本になります。次からは少しレベルアップしますよ～。[/ふきだし]

ＣもＤも通らない最短経路問題

問題３．下の図のような格子状の道路がある。このとき、交差点 $C$ も交差点 $D$ も通らない場合の数を求めよ。

さて、通らない交差点の数が $2$ つ以上になってしまうと、一気に難しくなってしまいます。

「問題２と何が違うのか」ぜひ考えながら解答をご覧ください♪

↓↓↓

【解答】

問題２と同様に、全体の場合の数から引く方針で考える。

上のベン図より、「 $C$ を通る場合の数」と「 $D$ を通る場合の数」を引いたとき、「 $C$ かつ $D$ を通る場合の数」が $2$ 回引かれることになる。

つまり、$1$ 回分足さなくてはならない。

ⅰ）$C$ を通る場合の数

$A$ → $C$，$C$ → $B$ とそれぞれ求めた上で、積の法則を使うと、$$\frac{4!}{2!2!}×\frac{5!}{3!2!}=6×10=60 (通り)$$

ⅱ）$D$ を通る場合の数

$A$ → $D$，$D$ → $B$ とそれぞれ求めた上で、積の法則を使うと、$$\frac{6!}{3!3!}×\frac{3!}{2!}=20×3=60 (通り)$$

ⅲ）$C$ かつ $D$ を通る場合の数

$A$ → $C$，$C$ → $D$，$D$ → $B$ と分けて求める必要がある。

よって、積の法則より、$$\frac{4!}{2!2!}×2!×\frac{3!}{2!}=6×2×3=36 (通り)$$

したがってⅰ）～ⅲ）より、全体の場合の数が $\displaystyle \frac{9!}{5!4!}=126$ 通りなので、

$126-(60+60-36)=126-84=42$ 通りである。

(解答終了)

[ふきだし set=”ウチダ”]「 $2$ 点以上を通らない最短経路問題」を解くには、集合と命題の話の基礎理解が必須となります。解答がよく理解できなかった方は、「和集合・補集合の要素の個数～（後日書きます。）」の記事をご参考ください。[/ふきだし]

池がある最短経路問題

問題４．下の図のような格子状の道路があり、池がある部分の道路は使用できない。このとき、交差点 $A$ から交差点 $B$ までの最短経路は何通りあるか。

さて、いよいよやってまいりました「池がある最短経路問題」。

ここでは冒頭に紹介したテクニックを用いて、鮮やかに解いてみせます！

【解答】

• $1$ 通りしかないところを先に埋めてしまう。
• 和の法則を用いて、他すべてを埋めていく。

以上 $2$ 点を守り、最短経路の総数を求めていこう。

したがって図より、$14$ 通りである。

(解答終了)

いかがでしょう。

「道が制限される　→　場合の数が少なくなる　→　数え上げが楽になる　→　和の法則を用いたテクニカルな解法が役に立つ」

こういった仕組みになっております。

一応、この問題を今まで通りに考えた解法も記しておきますね。

別解：今まで通りの解法

【別解】

図のように上手く対角線（分割線）を引くと、$3$ つの場合に分けられる。

したがって、$5+4+5=14$ 通りである。

(解答終了)

そもそも場合分けをしなければいけないこと。

それから、それぞれの場合において同じものを含む順列の総数を求めなくてはいけないこと。

以上から、池がある最短経路問題では、”和の法則を利用したテクニカルな数え上げ“が最も有効な手段であることがわかります。

最短経路問題に関するまとめ

改めて、本記事のポイントを $2$ つにまとめます。

1. 最短経路問題に必要な予備知識は、「同じものを含む順列」「和の法則・積の法則」「和集合・補集合の考え方」この $3$ つ。
2. 道が制限されればされるほど、”和の法則を利用したテクニカルな数え上げ“が役に立つ。

「場合の数」全 12 記事をまとめました。こちらから次の記事をCHECK!!

あわせて読みたい

場合の数とは？【高校数学Ａの解説記事総まとめ１２選】 「場合の数」の総まとめ記事です。場合の数とは何か、基本的な部分に触れた後、場合の数の解説記事全１２個をまとめています。「場合の数をしっかりマスターしたい」「場合の数を自分のものにしたい」方は必見です！！

以上、ウチダでした～。