数学が好きなサラリーマンのブログ

数学が好きなサラリーマンのブログです。数学ネタから大学受験数学、ビジネスやライフスタイルまで数学が好きなサラリーマンの頭の中を大公開しています。

理科大入試で学ぶ数学講座 2020理1-(2)-(a)

f:id:mathbanker:20180925144149j:plain

ゴールデンウィークなんて、わかってたけど、あっという間だったな。というわけで楽しく問題解いていこう。今回は、ちょっと亜流な解法で。

問題

f:id:mathbanker:20210510193249p:plain
解説

 ありがちな最短経路問題の中で、全体の形が四角じゃない問題。そんなこと無視して、↑に4回、→に3回行けばいいのね、なんてやってはいけない。連続↑に4回とか行けないわけだから、単純に矢印並べではパターンを洗い出せない。

 

じゃどうするのかというと、原点に戻って考えてみる。必殺技が使えないときには、普通にパンチ・キックで敵に挑むわけだ。場合の数の原点は、丁寧に数えること。このとき、愛言葉は、もれなく、ダブりなく。カッコ良くいえば、MECEとなる。

 

基本姿勢は、この「もれなく、ダブりなく」(MECE)で、そこから楽をするべく、効率的な数え方を模索していくことになる。

 

Aを出発して指でなぞりながらBにたどり着く経路を数えるという、長地道な作業をどう効率化できるだろうか。

 

いくつか解法・考え方はあるけど、まずはシンプルに考えてみる。東に2回連続いかない条件は、否定条件ゆえ、一旦肯定状態である2回連続して東に進む状況を算出し、最後に引くことにしよう。さて、どんな仕組みで各場合は増えていくのだろう。

 

どれでもいいから、ひとつ経路を取り上げてみる。その経路のどこかの交点で、違う選択肢をとれば、別のパターンが生まれる。つまり、交点がパターンを増やすきっかけになっていると解釈できる。

 

じゃ、一般に交点でどのようにパターンが増えるのかを考察してみよう。最も単純化したケースからはじめる。最も単純化したケースとは、BをAから一歩目の地点においた場合のものだ。

 

ここから便宜的に、東方向と北方向にそれぞれ進んだ点を(東、北)と表すことにする。

 

そうすると、単純化したケースは(1,0)あるいは(0,1)とかける。どっちに進んでも1通りしか存在しない。

 

ではあと一歩進めてみよう。例えば、(2,0)の点。これは北に2回進むしかないから、これまた1通りしかない。

次に、(1,1)の点。ここは、(1,0)から来る場合と(0,1)から来る場合で合流地点となり、2通りとなる。(2,0)の点と異なり、”合流”することでパターン数がが増える。

 

このまま続けて本来のBにたどり着いてもいいんだけど、これを一般化して考えてみよう。

ある交点からみたとき、西側からだけやって来る場合と南からだけ来る場合、その両方から来る場合に分類できる。やってくるものは、それまでに形成したパターンを引き連れてくるわけだけど、西か南の一方からのみだったら、引き連れてきたパターン数をそのまま継承するのみとなる。

一方、両方からやって来る場合、それぞれが引き連れてきたパターンの合算がその交点にたどり着く総数となる。

 

このルールを用いて数字を当てていったのが、下の図だ(矢印がある箇所は、一番左の値)。

f:id:mathbanker:20210511002151p:plain

ここから、脇においておいた条件、東に連続2回動く場合を除外する必要がある。Aに近いところから順に考えると、(0,1)の点から連続東に進む場合を除外するから、(2,1)の点へのパターンは1通りになる。

 

(2,2)の点は、除外条件がなければ5パターンある。合流の片方が1になったから、合算値も1小さくなって4になる。ここには、(2,0)を通って東に2回進む場合が含まれるので、その1パターンも引いて3通りとなる。

 

こういった作業を順次繰り返して行ったものが、上の図だ。まず除外条件なしの場合の数を書いて、すでに修正したところの数字で合流値を洗い替える。最後に、その交点に東に2つ連続で進む方法があれば除算する。

 

(3,2)の点は、(1,2)の点から東に3回進む場合を除くわけだけど、(1,2)の点にたどり着く3パターンには(2,0)点から東に一つ進むパターンも含まれていて、これはすでに(2,2)の点へのパターン数を計算するときに除外されていることに注意。

 

この作業により、最終的には10通りとなることがわかる。

 

場合分けしてもっとスッキリ解く方法あるけど、たまにはこんな亜流な回答も乙かなと。

 

今回はここまで。