問題:点Aから点Bまでの最短経路は全部で何通りあるか。ただし、斜線部分は通れないものとする。 解説:

問題:点Aから点Bまでの最短経路は全部で何通りあるか。ただし、斜線部分は通れないものとする。

解説:
斜線の部分を通る経路の総数を考える。斜線の部分を通るためには，図の直線l上の点を少なくとも1つは通る。そこで，最初にl上の点を通った後の経路をすべて，直線lに関して対称移動した経路を考える。例えば，A→P→Bの経路（太線）はA→P→B'(網の線）に移る。このとき，A→Bの経路はA→B'の経路と1対1に対応する。よって，斜線の部分を通る経路の数は12C5となる。ゆえに，求める経路の数は12C6-12C5 = 924-792 = 132 (通り）

上記の解説がよく分かりません。全体から斜線部分の経路を引いてるというのはなんとなく分かるのですが。。。分かりやすい解説をお願いいたします。

No.1 ベストアンサー 回答者： mabuterol 回答日時： 2023/02/24 12:08

斜線部分を通っても良い場合は分かりますか？

点 A から点 B に行く最短経路は要するには、右６回と上６回を移動すれば良いだけです。右と上の順番は自由に変えても最短経路です。これが 12C6 ですね。

しかし最初に上６回進んでしまうと斜線を横断してしまうのでルール違反です。なんなら最初に上２回進んでしまうだけでルール違反です。

だから、この問題で考える方法としては
① 斜線部分を横断する、しない関係なく全ルートの最短経路の総数から
② 斜線部分を横断する最短経路を引き算する
というような考え方になるでしょう。12C6 - ○○　という考え方です。

② についてですが、B を l に対して線対称の位置に移動させた B' に到着するには、必ずどこかで l を横断する必要があります。そして B と B' は線対称の関係ですから、l を通過して以降のルートは、右移動と上移動を反転させた関係になるのです。

例えば B から左に 1 つ移動した l 上の点は、B' から下に 1 つ移動した点となります。左と下が反転していますね。B から下に 1 つ、左に 2 つ移動した l 上の点は、B' から左に 1 つ、下に 2 つとなります。

つまり l を横断する過程で l 上の点のどこかに到着したら、そこから先は B に到着したければ右に n 回と上に m 回移動するならば、B' に行きたければ右に m 回と上に n 回を移動すれば良いのです。どっちも (n + m)Cn 通りの行き方になるでしょう。

さて B' に行くには右に 5 回を選ぶだけなので 12C5 です。それで 12C6 - 12C5 になります。

No.5 回答者： GOMΛFU 回答日時： 2023/02/24 16:37

1通りです。

紙を曲げて点Aと点Bをくっ付ければ良いのです。

No.4 回答者： usa3usa 回答日時： 2023/02/24 15:24

>上記の解説がよく分かりません。

＞分かりやすい解説をお願いいたします。

全体　X　通り
斜線部分の経路　Y　通り
のとき、斜線部分を通らない経路は？
という問題で、X,Yをそれぞれ計算しただけ

No.3 回答者： ありものがたり 回答日時： 2023/02/24 14:55

その「解説」に説明してあるとおりなんだが、

読んでどの部分が解らなかった？
十分丁寧に説明してあると思うけれども。

まず、意味不明な「斜線部分」というのは、
質問文中の図で道が点線で書いてある部分のこと
であるとして...

「斜線部分」も通って B へ行く最短経路は、
最初に直線 l 上の点を通る P 以降の部分を
直線 l に関して線対称に移動すれば、
A から B’ へ行く最短経路と一対一に対応している
ことは理解できた？
図の太線矢印の経路が、グレーの矢印の経路と
対応しているんだよ。

あとは、縦 m 歩, 横 n 歩で
特に通っちゃいけない道がないときの最短経路が
「縦」 m 個と「横」 n 個を一列に並べる並べ方
(m+n)Cn 通りであることから、

(A から B へ「斜線部分」を通らずに行く最短経路の数)
= (A から B へ特に制限なく行く最短経路の数)
　- (A から B へ「斜線部分」も通って行く最短経路の数)
= (A から B へ特に制限なく行く最短経路の数)
　- (A から B’ へ特に制限なく行く最短経路の数)
= (6+6)C6 - (7+5)C5
= 924-792
= 132
と計算できる。