職業能開センターの試験(数学)の解説お願いします

図のように、東西に4本、南北に7本の道路が碁盤の目のようになった街があります。
A点をスタートして、B点まで行くとき、最短の道を通っていく道順は何通りですか。
ただし、P点とQ点は、工事のため通行できないものとします。

この問題の答えは、48通りと書いてありました。

解き方を教えてください・・・＞＜

No.1 回答者： 21pponOK 回答日時： 2012/02/13 02:36

何となく目に付いたので答えてみました。

僕の場合は下の流れで解きます。

(1)AB地点間の道順を全通り求める
(2)P地点を通る道順を求める
(3)Ｑ地点を通る道順を求める
(4)PとQ両方を通る道順を求める

そして、(5)「(1)ー(2)－(3)＋(4)」を計算する


ここで、なぜPとQ両方を通る道順を足しているのかというと、

P地点を通る合計とＱ地点を通る合計を引いたときに、
PとQの両方を通る道順が重複してしまって、
2回分引いてしまっているからです。

つまり余分に引いてしまった分を足しているわけです。




あとは数字を当てはめて、ご自分でお考え下さい！
応援してます！

No.2 ベストアンサー 回答者： Pochi67 回答日時： 2012/02/13 04:38

　むかーし、引退された島田氏が某クイズ番組でやっていた、簡単な解き方を。

　始点Aから次に進む方に「１」を書き入れます。
　この場合は上と右にある、ひとつめの交点です。
　隣の交点への行き方は1通りです。

　最短なので、上か右にしか移動せず、下や左には移動しません。
　なので、上にある交点と右にある交点全てに「１」を書き入れます。

　次に始点Aから右に１、上に１の所にある交点に「2」を書き入れます。
　これは、右に行ってから上に進んだのと、上に行ってから右に進んだのの、2通りがあるからです。

　それぞれの交点は右に行くか上に行くかの2通りなので、順番にひとつ左にある交点の数字と、ひとつ下にある交点の数字を足していくと、その交点への道順の通り数がわかることになります。

　このやり方だと、通れない道は最初から数えなくて済むという利点が。

　但し、全ての交点に書き込んでいかないといけないという面倒な面もあります。


　　1　　4　　7　　14　19　30　48

　　1　　3　　3　　7　Q5　　11　18
　　　　　　 　P
　　1　　2　　3　　4　　5　　6　　7

　　A　　1　　1　　1　　1　　1　　1　


　普通は、中学数学で習う「パーミュテーション」を使います。
　参考　：　http://www.t-tsushin.net/kaihou/baa/p4.html
　考え方は、No．1さんの回答を参考にしてください。

この回答へのお礼

すごい！
とってもよくわかりました^^

どうもありがとうございます。

お礼日時：2012/02/13 13:55