入試問題に挑戦第１３４回

＜問題＞
　下の図のような道路があります。Ａ地点からＢ地点まで最短の道のりで進むことにします。次の問いに答えなさい。

（１）曲がり角を３回曲がる方法は何通りありますか。

（２）曲がり角を４回曲がる方法は何通りありますか。

（０４年頌栄女子学院）

入試問題に挑戦第１３４回解答編

＜解答＞
　あわてて考えようとすると方針が立たずに、ただひたすら数えることになりそうな問題です。順序を決めて、通る交差点を絞り込んで数えていく方法もありますが、ここでは「道順の問題」と「順列」の関連性を意識しながら解いてみましょう。

　まず、AからBまで最短の道のりで進む方法は全部で７０通りあります。これは図の中の交差点に数字を書きながら足し算を繰り返すことでもとめることもできますが、順列と組み合わせを使うと、

　「右」方向へ４回、「上」方向へ４回進めばBに着くことから、「右・右・右・右・上・上・上・上」という８文字の並べ方が何通りあるかという問題になります。８個の順列から、右４個、上４個のダブり分を除けばよいので、

　（８×７×６×５×４×３×２×１）÷（４×３×２×１）÷（４×３×２×１）＝７０（通り）

　この考え方をもとに問題を解いていきます。

（１）３回曲がるということを最も簡単に表すと「右→上→右→上」（右から始める場合）です。AからBに行くにはあと「右」「上」が２個ずつ必要です。

　そこで、残りの「右」と「上」をはじめの４個の「右」や「上」のところにつけてやれば、同じ「右→右」なら曲がらないので大丈夫です。

　つまり、

　この４つの箱を用意して、残りの「右」２個は青い箱、「上」２個は赤い箱に入れる入れ方を数えればよいことになります。

　ここで、「右」２個の入れ方は、下の表のように３通りあります。

　「上」２個の入れ方も同様に３通りあるので、全部で　３×３＝９（通り）　あります。

　これは、「上→右→上→右」（上から始める場合）でも同じだけあるので、

　３回曲がる方法は、　９×２＝　１８（通り）

（２）（１）と同じように考えると、４回曲がるのは「右→上→右→上→右」です。

　残りは「右」１個、上「２個」です。「上」２個の場合は（１）と同様に３通り、「右」１個については下の表のように３通りです。

　つまり、　右から始める場合が　３×３＝９（通り）　なので、

　４回曲がる方法は、全部で　９×２＝　１８（通り）