問題概略
下の図は T 都 S 区にある G 街という商店街の地図を表しています。線が道路です。
G 街の入り口(左下)にいるマサルさんが,この街の右上にあるカレー屋さんに行くことにしました。マサルさんは次の 2 つのルールにしたがってカレー屋さんを目指します。
- 前(地図上では上)または右または左にのみ進むことができる
- 来た道を戻ることはしない
図中の赤い線はその進み方のうちの 1 つを表しています。マサルさんが入り口からカレー屋さんに行く道のりは何通りあるでしょうか。
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
↑に注目
これは「気づけば一発」系の問題です。
入り口からカレー屋さんまでの経路は 4 つの↑といくつかの→,←の順列です。
↑が何番目にくるか決めれば→,←の並び順は自動的に決まります。
たとえば問題文中の図は左下図のように↑を決める場合の経路です。
求める経路数は の「625」です。