031格子状の道路の最短経路

問題

図のような格子状の道路がある。 $P=(0,0)$ 、 $Q=(6,4)$ とし、さらに、

R=(2,1),\qquad S=(4,3),\qquad T=(3,2)

とする。PからQまで行く最短経路について、次のものは何通りあるか。

(1) すべての最短経路

(2) Rを通る経路

(3) R、Sをともに通る経路

(4) Tを通らない経路

同じものを含む順列の王道問題です。応用問題ではありますが、本問題はそこまで難しくしていません。

中学受験を経験した人は、似た問題を解いたことがあるかもしれません。その場合は、経路の各交差点に小さく数字を書き込み、順に足していく解法を使ったのではないでしょうか。

本問題では、右へ進むことを $\rightarrow$ 、上へ進むことを $\uparrow$ で表します。すると(1)は、6個の $\rightarrow$ と4個の $\uparrow$ を並べ替える問題に帰着します。

この対応が分かりにくい人は、 $\rightarrow$ を6個、 $\uparrow$ を4個、適当な順番に並べてみてください。その矢印に従ってPから進むと、自然にPからQまでの最短経路が1つできあがります。

つまり、1つの最短経路と、6個の $\rightarrow$ 、4個の $\uparrow$ の並び方が対応しています。

PからRまでは、右へ2回、上へ1回進む。
$\frac{3!}{2!}=3$
より、3通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。
RからQまでは、右へ4回、上へ3回進む。
$\frac{7!}{4!\,3!}=35$
より、35通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。
PからRまでの経路と、RからQまでの経路を組み合わせるので、
$3\times35=105$
より、105通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。

$\frac{3!}{2!}=3$
より、3通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。
RからSまでは、右へ2回、上へ2回進む。
$\frac{4!}{2!\,2!}=6$
より、6通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。
SからQまでは、右へ2回、上へ1回進む。
$\frac{3!}{2!}=3$
より、3通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。
$3\times6\times3=54$
より、54通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。

PからTまでは右へ3回、上へ2回、TからQまでも右へ3回、上へ2回進む。

したがって、Tを通る経路は、
$\frac{5!}{3!\,2!}\times\frac{5!}{3!\,2!} =10\times10 =100$
通りである。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。
(1)で求めたすべての最短経路から、Tを通る経路を引く。
$210-100=110$
より、110通り。
AIの回答には誤りが含まれる場合があります。ThinkingFlowの確認済み結果・最終解答と照合してください。