Question

Marieee

地点Aから地点Eまで最短距離で行く経路は何通りあるかという問題です。解き方を教えて頂けないでしょうか🙏🏻

A
B
Di
C
(各4点×2)
E

Answer 1

✨ 最佳解答 ✨

dio

点Aから点Eまで最短経路で移動するのに、
必要な辺の数は6です。

また、移動するための行動パターンは、
下、横、奥の3つの方向しかありません。

下が2回、横が3回、奥が1回と決まるので、
これらの道順の並び方の組み合わせ数は、
6C2 × 4C3 =60通りです。

ただし、図の形状から通れない道も、
計算しているので除外する必要があります。
1. 横横横から始まるパターン 3通り
2. 奥横横横から始まるパターン 1通り
の計4通りです。
したがって、60-4=56通りが解です。

（もし間違えてたら、教えてください）

Answer 2

K

先にご回答されている方に恐縮ながら次いで指摘するのですが、消去する経路はもっとあります。画像の経路は全て存在しない経路を通ります。よって6C5=6通り消去され、答えは60-6=54通りです。

K

もしくは経路の通り方の足し算を行っていくやり方もあります。画像のような点O,A,B,Cを考えたときに、O→Aまでの経路がa通り、O→Bまでの経路がb通りであるとします。もし、Cに行く方法がA→CとB→Cしかないとすると、O→Cに行く経路は当然a+b通りです。これを今回の問題に適用すると、画像の下の様になり、同じく54通りであることが確認できます(ちなみにAから見てEは右側、下側、奥側にあるので、左側、上側、手前側に行くような経路は最短経路ではありませんので考えていません。そのために図に矢印をふってあります)このやり方は通行不可などを場合分けして考える必要がなく、ただ足し算しておくだけなのでかなり便利です。