問題:点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ベストアンサー
- 回答日時:
斜線部分を通っても良い場合は分かりますか?
点 A から点 B に行く最短経路は要するには、右6回と上6回を移動すれば良いだけです。右と上の順番は自由に変えても最短経路です。これが 12C6 ですね。
しかし最初に上6回進んでしまうと斜線を横断してしまうのでルール違反です。なんなら最初に上2回進んでしまうだけでルール違反です。
だから、この問題で考える方法としては
① 斜線部分を横断する、しない関係なく全ルートの最短経路の総数から
② 斜線部分を横断する最短経路を引き算する
というような考え方になるでしょう。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.4
- 回答日時:
>上記の解説がよく分かりません。
>分かりやすい解説をお願いいたします。
全体 X 通り
斜線部分の経路 Y 通り
のとき、斜線部分を通らない経路は?
という問題で、X,Yをそれぞれ計算しただけ
No.3
- 回答日時:
その「解説」に説明してあるとおりなんだが、
読んでどの部分が解らなかった?
十分丁寧に説明してあると思うけれども。
まず、意味不明な「斜線部分」というのは、
質問文中の図で道が点線で書いてある部分のこと
であるとして...
「斜線部分」も通って 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
と計算できる。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(就職・転職・働き方) 会社の交通費について 4 2022/07/17 07:27
- 地図・道路 建築、土木工事に詳しい方教えてください。 高速道路 (高架)片側1車線の道路を片側2車線往復4車線に 4 2022/08/29 13:21
- その他(IT・Webサービス) 乗換案内(区間の一部を指定して有料特急を使用する検索) 4 2023/06/25 22:26
- 電車・路線・地下鉄 電車の本数が1時間に1本しかないなら、単線化はなぜされないのですか。 7 2023/07/15 17:01
- 政治 沿線住民の利益を考えれば、赤字路線は切り捨てるのは当然ではないか? 4 2022/04/12 08:59
- 物理学 ごめんなさい。基本的な事だけど、日本語があまりわかりません。 一般のベクトルの線積分では、その値が経 4 2022/07/06 19:23
- 大学・短大 設計速度の問題 1 2022/10/13 15:15
- 電車・路線・地下鉄 北陸本線が、1時間1本以上を保持するわけ。 2 2022/06/06 20:05
- その他(ニュース・社会制度・災害) JRへの除草作業をさせるためには? 4 2022/05/12 15:07
- 物理学 ふと疑問に思ったのですが写真のような回路のとき、キルヒホッフの法則からI1 =I2になることから、赤 3 2023/08/11 00:14
このQ&Aを見た人はこんなQ&Aも見ています
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
(1800×900)と書いてあ...
-
縦の長さが60センチ 横の長さが...
-
ブリルアンゾーンについて
-
整形の勉強をしています。 長軸...
-
力のモーメント
-
時間領域、周波数領域とはなにか
-
三点支持について
-
directionとorientationの(方向...
-
〇〇の原理について説明せよ と...
-
生体組織の異方性
-
距離と道のりの英語での表現に...
-
相乗モーメントってなんですか?
-
加重平均を用いた運搬距離の算...
-
TD、MDって何の略?
-
「あさっての方向」の語源を教...
-
ご質問です。機械設計の問題で...
-
余角と補角を図で示して教えて...
-
走向傾斜 EW45°N
-
ティッシュペーパーの向きで強...
-
sp3混成軌道について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
(1800×900)と書いてあ...
-
縦の長さが60センチ 横の長さが...
-
整形の勉強をしています。 長軸...
-
余角と補角を図で示して教えて...
-
図形群の法則性の問題
-
四角形の寸法表記方法 縦×横...
-
力のモーメント
-
三点支持について
-
線電荷密度ρの半径Rの無限長の...
-
SEMのstigma調整って何ですか
-
上下方向の力を左右方向に変換...
-
相乗モーメントってなんですか?
-
「長手」の対義語は何でしょうか?
-
TD、MDって何の略?
-
x成分14N y成分24N っていうの...
-
「逆方向、別方向」はどういう...
-
モータのd軸、q軸ってどうゆう...
-
角度からベクトルに変換するに...
-
ブリルアンゾーンについて
-
鉛筆を芯だけにするには?
おすすめ情報