たてとよこに並んだ道を、遠回りしないで進む
たてとよこに道がまっすぐ並んだ町を、上から見た形を考えます。
左下のAから右上のBまで歩くとき、行き方はひとつではありません。
どの道を選ぶかで、曲がる場所は変わります。そのかわり、変わらないものもあります。
遠回りをしなければ、右に3区画、上に2区画進むところは、どの行き方でも同じです。
この「遠回りしない行き方」を最短経路といいます。AからBまでの最短経路が何通りあるのか、数えてみます。
最短で行くなら、進む向きは右と上だけ
Aから見ると、Bは右上にあります。
なので、最短で向かうときに進むのは、右か上のどちらかだけになります。
左の図は、右と上だけで進んでいます。矢印は全部で5本、右が3回と上が2回です。
右の図は、途中で左にもどっています。左にもどると、そのぶんまた右へ進み直すことになるので、進む回数が増えます。
下に進んだときも同じで、下がったぶんをまた上がることになります。
最短経路はどれも、右3回と上2回の合わせて5回です。違っているのは、その順番だけです。
小さい道なら、全部書き出して数えられる
順番だけが違うのなら、その順番を全部書き出せば数えられます。
実際に書き出してみると、10通りありました。
もれなく書き出すときのコツは、樹形図のときと同じで、先に順番を決めておくことです。
ただ、この方法は道が増えるとすぐに苦しくなります。よこ5区画・たて5区画になると道順は252通りで、書き出していられる数ではありません。
そこで、書き出さずに数える方法を見ていきます。
交差点に「そこまでの行き方の数」を書きこむ
使うのは、交差点に数を書きこんでいくやり方です。それぞれの交差点に、そこまで何通りで来られるかを書き入れていきます。
まず、いちばん下の行と、いちばん左の列を見ます。
ここに並ぶ交差点へは、まっすぐ進むしか行き方がありません。だから、どれも1になります。
次に、その内側です。
下から2番目の行には、左から1・2・3・4が並びます。いちばん上の行は1・3・6・10です。
これらの数は、左どなりの数と、下の数を足したものになっています。上の行の6であれば、左の3と下の3を足した数です。
そして右上のBには10が入ります。書き出して数えた10通りと、ぴったり同じです。
なぜ左の数と下の数を足すだけでいいのか
足し算になる理由は、Bに着く直前の一歩を見ると分かります。
Bに入ってくる道は、左の交差点から右に進む道と、下の交差点から上に進む道の2本だけです。右や上から入ってくることはありません。
左の交差点までは6通りの行き方があって、そのどれもが、最後に右へ一歩進めばBに着きます。
下の交差点までは4通りで、こちらは最後に上へ一歩進めばBに着きます。
この2つのグループは重なりません。最後の一歩が右向きか上向きかで、はっきり分かれているからです。
数え落としもありません。Bに着く道は、必ずどちらかのグループに入ります。
だから6と4を足した10が、Bまでの行き方の数になります。
同じことは、ほかのどの交差点でも起きています。左と下から順に数が決まっていくので、Aに近いところから順番に書きこんでいけます。
ポイント
- 最短経路で進む向きは右と上だけで、進む回数も決まっています。違うのは順番だけです。
- いちばん下の行といちばん左の列は、行き方が一本道なのですべて1になります。
- 内側の交差点は、左の数と下の数を足すと出ます。入ってくる道が、左と下の2本しかないためです。
- 書き出せないほど道が増えても、書きこむ方法なら同じ手順で数えられます。
練習問題
【練習問題】①
よこ2区画・たて2区画の道を、左下のAから右上のBまで遠回りせずに進みます。道順は何通りありますか？
タップで答えを見る
答え：6通り
いちばん下の行といちばん左の列に1を入れ、内側を左＋下で足していきます。
真ん中が2、その上と右がどちらも3になり、右上のBに6が入ります。
【練習問題】②
よこ3区画・たて3区画の道を、同じようにAからBまで遠回りせずに進みます。道順は何通りありますか？
タップで答えを見る
答え：20通り
いちばん下の行と左の列はすべて1です。下から2行目が1・2・3・4、3行目が1・3・6・10、いちばん上の行が1・4・10・20と並びます。
右上のBに入るのは20です。
【練習問題】③
よこ3区画・たて2区画の道では、道順は10通りでした。では、たてとよこを入れかえて、よこ2区画・たて3区画にすると何通りになりますか？
タップで答えを見る
答え：10通りで、変わりません
書きこんでみると、下から2行目が1・2・3、3行目が1・3・6、いちばん上の行が1・4・10となり、右上に10が入ります。
たてとよこを入れかえると、書きこまれる数の並びも、たてよこが入れかわった形になります。右上に出る数は同じままです。
まとめ
最短経路の数え方は、まず全部書き出してみて、そのあと交差点に数を書きこむ方法へつなげると、なぜ足し算で出せるのかが見えてきます。
足すのは、その交差点に入ってくる道が左と下の2本しかないからです。重なりも取りこぼしもないので、そのまま足せます。
道が増えて書き出せなくなっても、書きこむ手順は変わりません。並んだ数の増え方を見ていくと、数の規則性の話ともつながってきます。