長方形の中の網目状に道がある。対角間を最短距離で進む時、道順は何通りあるか？

質問

---- ---- ----
l　　　l　　　l　　　l
---- ---- ----
l　　　l　　　l　　　l
--- - ---- ----
l　　　l　　　l　　　l
---- ---- ----

図が悪いのですが、長方形の中に縦４本横３本の線が引いてあります。（網目状になっています。）
長方形の右下をＡ左上をＢとします
ＡＢ間を最短距離で進む時、道順は何通りあるか？

本日の数学の問題です。いったい何通りあるのですか？気になって仕方ありません。

ぼくは４０本だと思うのですが。

回答No.6

prome · ベストアンサー

hikaru_macさん、stomachmanさんのおっしゃる通りで、
厳密な議論に基づいた回答だと思います。
私は別の考え方をしてみます。

Ｂ━┳━┳━┳━┓
┃　┃　┃　┃　┃
┣━╋━ｇ━ｅ━ｃ
┃　┃　┃　┃　┃
┣━╋━ｆ━ｄ━ｂ
┃　┃　┃　┃　┃
┗━┻━┻━ａ━Ａ

上の図で説明します。
Ａ点からａ点までは明らかに１通り、Ａ点からｂ点へも１通りです。
ではｄ点は？
－－これはａ点を通るコースとｂ点を通るコースがあるので２通りです。
ｃ点は？
－－これは明らかに１通りです。
ｅ点は？
－－これはｃ点を通るコースとｄ点を通るコースなので、１＋２＝３通り。
ｆ点は？
－－これはＡ－ｄ－ｇを結ぶ線に対してｅ点と対称なので、ｅ点と同じく３通り。
ｇ点は？
－－ｅ点を通るコースとｆ点を通るコースがあるので、３＋３＝６通り。
つまり
Ｂ━┳━┳━┳━┓
┃　┃　┃　┃　┃
┣━╋━６━３━１
┃　┃　┃　┃　┃
┣━╋━３━２━１
┃　┃　┃　┃　┃
┗━┻━┻━１━Ａ
となります。この議論をＢ点まで進めていくと、
35━20━10━４━１
┃　┃　┃　┃　┃
15━10━６━３━１
┃　┃　┃　┃　┃
５━４━３━２━１
┃　┃　┃　┃　┃
１━１━１━１━Ａ
となり、３５通りと答えが出ます。

ここまで進めていくと、鋭い方は気がつくと思いますが、
数学で習ったパスカルの三角形と同じです。つまり
　　　　　　１　　　１
　　　　　１　　２　　１
　　　　１　３　　　３　１
　　　１　４　　６　　４　１
　　１　５　10　　　10　５　１
　１　６　15　　20　　15　６　１
１　７　21　35　　　35　21　７　１

がパスカルの三角形ですが、逆三角形
　　ａ ｂ
　　　ｃ
の部分は、ｃ＝ａ＋ｂになっているというものです。
このパスカルの三角形の各行は、二項定理つまり（ｘ＋ｙ）＾ｎを展開した時の
係数の並びということも高校数学で習いました。
そしてこの係数はｎＣｒで表されることもご存知でしょう。
問題のＢ点は７Ｃ３（７と３は下に小さく書いたものとします）＝３５です。

これでなぜコンビネーションが出てくるのかもおわかりかと思います。

社内で情報処理試験対策講座の講師をしていた時、この説明をして
わかりやすいと好評でした。オンラインではなかなか説明しにくいですが。

お礼

ほほぉ。
かなりわかりやすかったです。
とても参考になりました。

ありがとうございました

回答No.5

hikaru_mac

No.1の回答者のhikaru_macです。
図は

┏┳┳┳┓
┣╋╋╋┫
┣╋╋╋┫
┗┻┻┻┛

でいいのですか？
実は私はMacを使っているのでもしかしたらアスキーアート（文字の絵）はうまく見えていないかも知れません。（等幅フォントにすればいいのか、はてな）

ちなみにもちろん、線の部分を通るんですよね？
まさかマスの中を進むんじゃないですよね？

えーと、そのようにすると、、、、
左４回上３回。
コマンドの入力は例えば
・左左左左上上上
ほかにも
・左左左上左上上
などなど。
これらを全部書き出してみると、

（7*6*5*4*3*2*1）÷{(4*3*2*1)*(3*2*1)}
=(7*6*5)/(3*2*1)
=35
35通りとなります
----
ちなみにコンビネーションとは高校数学の教科書の「場合の数、組み合わせ」という項目で勉強します。
あなたの学年とかが分からないので説明は今回もいたしません。
この程度の問題ならしらみつぶしでもいいと思います
（200*300のマス目になると、さすがにしらみつぶしは出来ない）
（もししりたければ、あなたの学年にもよりますが一応勉強してからもう一度御質問ください。もちろん、あなたの現在の状況によってはわたしが説明する事もあり得ますが。）

----
No.2の回答ですが
「その後は最短距離ですから1通りしか選択できません。 」
と言っているけど、はしっこを選んでいけばは、確かに1通りしかないけれど
上に行ったり左に行ったりした場合は、最短経路が1通りではないと思います。それで、どの私の答えとも違った回答が出てしまったのだと思われます。

お礼

図はその通りです。（当方WINですが、図はちゃんと分かりました。）
道は、線を通ります。

ぼくは中三です。調べたら、コンビネーションとか何となく分かった気がしました。

ありがとうございました

回答No.4

stomachman

長方形の「中」に縦４本横３本ですよね。図では全然そうは見えないが…
と思ったら、「長方形の中に、縦３本　横２本の線が引いてあります。」という訂正ですか。なるほど。
　ということは、長方形の角から出発したくても、長方形の角に道が来てないから動けません。答は０通り。

　あ、いやいや、だとすると、きっと「長方形の辺そのものも道」ってことでしょうね。そうするとですよ。
　隣り合う角または交差点の間を移動するのを１回の動き、と数えます。横に動くのを「横」縦に動くのを「縦」と書きます。最短距離、ってのはつまり横4回、縦3回動くってこと。都合7回動く訳です。7つの動きの中に、縦が3つ。残りが横。7つの中から3つ選んで、それを縦ということにすれば、残りは横。てことは、
「7つの中から3つ選ぶやり方は何通りあるでしょうかっ。」という組み合わせ(combination)の数を求めればよい。
7C3 = 7! /(3! 4!) = (7×6×5)/(3×2) = 7×5 = 35　通り。

combination（コンビネーション、組み合わせ）については、「順列 組み合わせ」で過去の質問を検索すれば解説が見つかります。例えば↓

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=159077

お礼

ちょっと難しくてよく分かんないんですけど、３５通りみたいですね。
ありがとうございました

回答No.3

tamatokuro

式は分からないですが、数えてみたら２０本でした。

お礼

ぼくも数えてみたんですよ。
デモ、断念しました。。。。

ありがとうございました

回答No.2

BIGMAC

図のままですと、右下Aからの道筋は2通り、2通りいった次は、また2通り、その次も2通り、その後は最短距離ですから1通りしか選択できません。

従って、
2×2×2×1＝8通り

説明文の通りですと、
2×2×2×2×1＝16通り

で、どうでしょう？

お礼

済みません。図、分ともに間違いです。
何を錯乱していたのやら（笑

ありがとうございました

回答No.1

hikaru_mac

マス目は３×３でいいんですよね？
質問の文と図がかみあってないような、、、？

ＡからＢに進むのに、左のキーを３回、上のキーを３回たたけばよい。
左３回上３回。
たたく順番がいろいろあって、それぞれが異なる道順になっている。
たたく順番（コマンド入力手順）は全部で何通りか　を考えれば良い。

「左」という文字と「上」という文字の並び替えの問題と同じで
その総数は
6C3となる。（CはコンビネーションのC。両端の数字はは下に小さくかいたつもり。）
6C3=(6*5*4)/(3*2*1)=20

こたえは20通りではないでしょうか？

コンビネーションとか、気になったらまた質問して下さい。

補足

あ、すみません。
勘違いで、図が、おかしいですね。
正確には、マス目は３×４です。
長方形の中に、縦３本　横２本の線が引いてあります。

でも、ありがとうございました。

コンビネーションとは何ですか？