数学の最短経路の問題について教えてください

数学の問題です。３×３のマス目を最短経路で進む数という問題なんですが、答えは6Ｃ3=20通り。
6Ｃ3　という考え方が理解できません。縦横６個から３つ選ぶという意味だと思うのですが、何度考えても分かりません。
分かりやすく教えてください。よろしくお願い致します。

No.6 ベストアンサー 回答者： ORUKA1951 回答日時： 2015/08/15 19:57

例えば、進む方向は左上から右下に進むとすると

1) 進行方向は→と↓の二方向のみ
2) 必ず→3回、↓3回
これは、順番には関係ないですね。

ならば、→だけ何回めの行動かを考えれば後は自動的に決まる。
１，２，３，４，５，６回目の行動
→，→，→，
→，→，　,→
→，→，　，　，→
・・・・・・・・・・・
　，　，　，→，→，→

6回の行動バターンのうち、３個を選択して、それを→とする。

確かに、閃きと経験から、₆C₃に、直接たどり着いく場合もありますが、順列の結果を同じ物の数、3×3で割っても良い。

この回答へのお礼

ご回答ありがとうございます。
図で解説してもらえたのでよく分かりました。この図からだと6C3として計算することが理解できます。
もっと頭を柔らかくして考えないといけないですね。とても勉強になりました。
ありがとうございました。

お礼日時：2015/08/21 19:49

No.5 回答者： stomachman 回答日時： 2015/08/11 10:46

ANo.3へのコメントについてです。

　どうもこう、なんかね、「パターン」みたいなものを「暗記」した上で、それに「当てはめ」て問題を解こうとなさってるような気もするんですが、もしそうだったら、それは思考をサボろうという駄目なアプローチ。丁寧に考えなくちゃ駄目です。

> たとえば１〜6の数字から3桁の整数を作る場合

でしたら、
「1」、「2」、…「6」と書いてあるカードが1枚ずつある。その中から3枚選ぶやり方は6C3通り。選んだのは整数を作るのに使う。
　たとえば「2」「3」「5」を選んだとして…
次に、選んだ3枚のカードを並べて桁の整数を作る。並べ方は3!通りあって
235
253
325
352
523
532
はどれも違う整数。


> 最短経路の問題の場合3!は必要ないんでしょうか?

「1回目の移動」、「2回目の移動」、…「6回目の移動」と書いてあるカードが1枚ずつある。その中から3枚選ぶやり方は6C3通り。選んだのが「タテ」で、選ばなかったのが「ヨコ」。
　たとえば「2回目の移動」「3回目の移動」「5回目の移動」を選んだとして…
選んだ3枚のカードを並べるやり方は3!通りあるけれども、
2回目の移動、3回目の移動、5回目の移動はタテ、他はヨコ
2回目の移動、5回目の移動、3回目の移動はタテ、他はヨコ
3回目の移動、2回目の移動、5回目の移動はタテ、他はヨコ
3回目の移動、5回目の移動、2回目の移動はタテ、他はヨコ
5回目の移動、2回目の移動、3回目の移動はタテ、他はヨコ
5回目の移動、3回目の移動、2回目の移動はタテ、他はヨコ
並べ方がどうであろうと、経路は一緒ですよね。

この回答へのお礼

何度もありがとうございます。
悩みに悩んでやっと理解できました。
想像力が乏しいので頭の中でなかなかイメージできませんでした。
これで最短経路の問題は迷わず解けると思います。
ありがとうございました。

お礼日時：2015/08/21 20:00

No.4 回答者： yhr2 回答日時： 2015/08/10 00:54

この問題を見て、普通「線の上を進む」とは解釈しないでしょう。

　私は「マス目」の中に置いた碁石（将棋の駒でもよい）を何回動かすか？　と解釈して、「縦2つ、横2つ進む。マス目の外に出るのに、もう1回？　それでも合計5回にしかならない」と考え、悩みました。
　多分、質問者さんの疑問も、そのことなのではありませんか？

　要するに、問題に「線上を進む」と明記してあるか、「マス目を進む」としてあるかがポイントかと思います。それを明記していないなら、「問題の書き方が不明確」という「国語の問題」になるかと思います。

この回答へのお礼

説明不足ですいません。マス目の線上を進む問題でした。

お礼日時：2015/08/10 11:15

No.3 回答者： stomachman 回答日時： 2015/08/09 15:53

「行き方」を「カドから出発して、タテ、ヨコ、タテ、…の順に行くんだよ」という風に表現するんです。

すると、タテヨコどういう順番であろうと、タテに3回、ヨコに3回移動すれば対角上のカドに到着。碁盤の目なんだから行き着く先は一緒です。だからとにかく、タテに3回、ヨコに3回移動しさえすれば良い。
　ここまでがまず腑に落ちないとどうにもなりません。

　腑に落ちたとしてです。すなわち(「1回目の移動」、「2回目の移動」、…「6回目の移動」)という6つのモノの中から3つを選んでそれをタテとし、残りをヨコにすれば宜しい。
　なので、「相異なる6つのモノの中から3つを選ぶやり方は何通りありますか？」という問題と同じです。

この回答へのお礼

ご回答ありがとうございます。
「相異なる6つのモノの中から3つを選ぶやり方は何通りありますか？」
またここで新たな疑問なんですが、たとえば１～6の数字から3桁の整数を作る場合6C3・3!=120　で合ってますかね?
もし合っていれば、最短経路の問題の場合3!は必要ないんでしょうか?
すいません、まだ自分の中で整理できていなくてもう少し考えてみたいと思います。
ありがとうございました。

お礼日時：2015/08/10 14:50

No.2 回答者： soixante 回答日時： 2015/08/08 17:36

縦と横の要素に分解して考えてみたらどうでしょう。

3x3のマス目。左下をA点、ゴールの右上をB点としましょうか。
で、横に動く動きをx、縦に動く動きをyと考えましょう。

AからBに到達するのに、最短で行くなら、横方向だけを考えたら、３つ進めば最短。
２つや１つでは無理。
これはいいですよね？

じゃあ縦方向の最短は？当然３つ。

実際にはAからBまで行くので、縦に３つ、横に３つの移動が最短。
つまり、合計6回進んだら最短で行けます。
xが3個とyが3個です。

あとはどういう順序で行くか。
xxxyyy ？ yyyxxx？ xyxyxy？
この並べ方の問題となります。

xの置き場所さえ決まれば、あとは勝手にyとなります。
６箇所の置き場所のうち、３つxを置く場所は？

6C3 。20通りのパターンがあるのです。

この回答へのお礼

ご回答ありがとうございます。
なるほど並べ方という考え方で6!/(3!・3!)=20というのは理解できました。
しかし　6C3　という考え方はまだ自分の中でスッキリしません。
でも一歩前進できたのでもう少し悩んでみたいと思います。
ありがとうございました。

お礼日時：2015/08/10 14:15

No.1 回答者： ojisans 回答日時： 2015/08/08 15:58

こんにちは。

最短経路の回答は、基本的に６C3＝20という計算式の定義がわからない場合は、文章で説明することが難しいですね。
しかしながら、最短経路は、図で表すと以外に理解できるものなのです。
最短経路の詳細を図で詳しく解説してくれているサイトが御座いますので、よろしければ拝見してみてはいかがでしょうか？
http://www004.upp.so-net.ne.jp/s_honma/urawaza/r …

参考になれば幸いです。

この回答へのお礼

ご回答ありがとうございます。
裏ワザの方が断然簡単で確実に答えに辿り着けますね。
参考になりました。

お礼日時：2015/08/10 11:18