最短経路の道順の解き方と公式｜足し算で数える理由・通れない道・必ず通る点の例題【中学受験】

うかるくん

道順を全部書き出していたら、とちゅうでわからなくなっちゃった。

合格先生

交差点に数を書こう。最後の1歩は左からか下からなので、左の数と下の数を足せばいいんだ。

最短経路の道順の数え方

ごばんの目のような道で、AからBまで遠回りしないで行く道順（最短経路）が何通りあるかを数える問題です。遠回りしないとは、右上のBへ行くなら右か上にだけ進むということです。

なぜ足し算で数えられるのか

右か上にしか進まないので、ある交差点に着く最後の1歩は、「左のとなりの交差点から右へ」来るか、「下のとなりの交差点から上へ」来るかのどちらか1つです。

左の交差点までの道順が3通りあれば、そのあと右へ1歩進む道順も3通り。下の交差点までが3通りなら、そのあと上へ1歩進む道順も3通り。この2つのグループは最後の1歩がちがうので、同じ道順が両方に入ることはありません。また、どの道順もどちらかに必ず入ります。だから、もれなく、重なりなく数えるには足せばよいのです。

はしの交差点が1になるのは、Aからまっすぐ進む1通りしかないからです。こうして、Aに近い交差点から順に数を書いていけば、最後にBの数が答えになります。

（参考）横4・たて3の道では、どの道順も「右4回・上3回」の合わせて7歩です。7歩のうちどこで上に進むか（3か所）を選ぶ数なので、高校で習う組合せでは ${}_7\mathrm{C}_3=35$ と計算できます。足し算で出した35と同じです。

中学受験（算数）での使い方

よくある間違い

合格先生

通れない道を通ってくる数は足してはだめだ。その交差点は、もう一方からの数だけになるぞ。

• 通れない道の先でも足してしまう：×の道を通ってくる数は足しません。その交差点は、もう一方からの数だけになります。
• はしの交差点をまちがえる：はしの1は「Aからまっすぐ行ける」交差点だけです。通れない道の先にあるはしの交差点は0になります。
• 必ず通る点で足し算をする：「Pまで」と「Pから」はつながるので、足すのではなくかけ算です。

練習問題

うかるくん

はしは1、あとは足し算で進めよう。

1. 中学受験 横に3区画、たてに3区画のごばんの目の道で、左下から右上まで遠回りしないで行く道順は何通りですか。
   答えと解説を見る

   各段は 1,1,1,1／1,2,3,4／1,3,6,10／1,4,10,20。答え 20通り
2. 中学受験 横に5区画、たてに2区画の道で、左下から右上まで遠回りしないで行く道順は何通りですか。
   答えと解説を見る

   各段は 1,1,1,1,1,1／1,2,3,4,5,6／1,3,6,10,15,21。答え 21通り
3. 中学受験 横に3区画、たてに2区画の道で、左下Aから右へ1区画・上へ1区画の点Pを通って右上Bまで行く道順は何通りですか。また、Pを通らない道順は何通りですか。
   答えと解説を見る

   AからPまで2通り、PからBまで（横2・たて1）3通りで $2\times3=6$。全部で10通りなので、通らないのは $10-6=4$。答え 通る6通り、通らない4通り

関連する公式

• 樹形図と数え上げ
• 色の塗り分け
• 順列・組合せの公式（${}_n\mathrm{C}_r$ で数える）
• 同じものを含む順列
• 確率の基本と余事象

よくある質問

あわせて読みたい

• 合格大作戦 算数・数学公式辞典（公式一覧）