第３３０問の解答

問題　［場合の数（最短経路）］

問題図 左図のような碁盤の目状の道路があります。

いま、Ａ地にいるマサル君はＢ地に、Ｘ地にいるトモエさんはＹ地に、それぞれ最短距離で進むものとします。

このとき、２人が通った道筋が途中で交わったり、同じ点や道を通ったりしないような２人の進み方は何通りあるでしょうか。

解答例１

長野　美光さん、おかひで博士さん、sugitakukunさん、toyoさん、うっしーさん、Nonさん、Banyanyanさん、トトロ＠Ｎさん、みっちん。さん、ponta55555さん、ミミズクはくず耳さん、をめがさん、有無相生さん、ふじさきたつみさん、ステップ　ばい　ステップさん、ねこやんさん、フランク長いさん、sodoさん、 他

２人とも、３×３の格子上の最短経路を進むので、それぞれ3+3Ｃ3＝２０通りあります。
そこで、マサル君の最短経路２０通りのそれぞれについて、
これと共通点を持たないトモエさんの最短経路を数えることにします。

参考図１

上図のようになりますので、
合計＝（１＋２＋３＋４＋３）＋（５＋７＋６＋９＋１０）＋（４＋７＋１０＋９＋１４）＋（１６＋１０＋１６＋１９＋２０）
　　　＝１７５通り
となります。

答：　１７５通り

以上

解答例２

マサルさん、CRYING DOLPHINさん、まるケンさん、 他

Ａ→Ｂ、Ｘ→Ｙで共通点を持つ最短経路（タイプＩ）とＡ→Ｙ、Ｘ→Ｂの最短経路（タイプＩＩ） の数は等しいことを示します。

参考図２

参考図３

タイプＩの任意の最短経路について、最初に２人の経路が共通となる点をＰとします。

このとき、Ａ→Ｐ→ＹはＡ→Ｙの最短経路、Ｘ→Ｐ→ＢはＸ→Ｂの最短経路となるので、
　タイプＩの経路数≦タイプＩＩの経路数　・・・　（１）

また、タイプＩＩの任意の最短経路について、Ａ→Ｙの経路に関してＸとＢは反対側にあるので、
Ａ→ＹとＸ→Ｂの最短経路は、必ず共通点を持ちます。

初めて共通となる点をＰとすると、Ａ→Ｐ→ＢはＡ→Ｂの最短経路、Ｘ→Ｐ→ＹはＸ→Ｙの最短経路となるので、
　タイプＩＩの経路数≦タイプＩの経路数　・・・　（２）

（１）、（２）より、タイプＩの経路数＝タイプＩＩの経路数　が示されます。

さて、Ａ→Ｂ、Ｘ→Ｙの最短経路数は、それぞれ3+3Ｃ3＝２０通りなので、合計２０×２０＝４００通り。

また、Ａ→Ｙ、Ｘ→Ｂの最短経路数は、それぞれ4+2Ｃ2＝１５通りなので、合計１５×１５＝２２５通り。（タイプＩＩ）

求める経路数＝４００−２２５＝１７５通りとなります。

（その他の解法）