最短距離（場合の数）

質問

縦５ます、横６ますの方眼紙があって左下から右上まで線上を最短で通って行くとき、４回曲がるのは何通りか？

どこかの点を通る問題ならできるのですが、、、
どうやって数えれば良いのかわかりません。教えていただけますでしょうか。
答えは７０通り。

回答No.1

kony0 · ベストアンサー

おぉ。よくありそうで、はじめてみる問題です！

（１歩目が右の場合）
→○→○→○→○→○→
1.上の５つある○の中から２つ選ぶ→5C2=10とおり
2.２つ選んだ○の中に、合計５個の↑を割り振る。ただし○の中に少なくとも１個は↑が入る。→４とおり

（１歩目が上の場合）
同じように考えて、4C2×5とおり

お礼

初見でも解けるとはやはり。
すごいです。初見で解けるようにならなくちゃだめですね。

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

回答No.3

ticky

少しわかりにくいかもしれませんが、＃２の方と同じく、xy平面上で考えてください。

この方眼紙は、(0,0)-(0,6)-(5,6)-(5,0)の長方形の枠で囲まれています。
始点と終点は枠上にあります。つまり、枠の上でスタート、枠の上でゴールですから、この枠の上で、２回曲がることになります。
ということは、スタートして、始めに枠の上で曲がり、枠の内側に入って、一回曲がり、もう一回曲がって、枠の上に出た地点で曲がり、ゴールすることになります。

この、枠の内側で曲がる２点は、x軸に平行な直線上か、y軸に平行な直線上にあります。
また、２点は重なってはいけませんし、枠の内側になければいけません。
この条件を満たす、２点の組が何通りあるかを計算します。

まず、２点がx軸に平行な直線上にある場合について考えます。
枠の上の(0,y)、(6,y)の点は含みませんから、(1,y)から(5,y)までの間の、５つの点から、２つを選びます。これは(5×4)/2=10通りあります。
また、この２点が存在しうる直線は、枠の上を除くので、y=1からy=4までの４通り。
10×4＝40通りになります。

同様に、２点がy軸に平行な長句線上にある場合については、枠の上の(x,1)から(x,4)までの４つの点から２点を選ぶのは、(4×3)/2=6通り。
２点が存在できる直線は、x=1からx=5までの５通り。
よって6×5=30通り。

最後に、双方の場合を足して、40+30=70通りとなります。

＃１の方の解き方は、多分これと同じでしょう。

回答No.2

fushigichan

ONEONEさん、こんばんは。
これも難しい問題ですね。

まず、説明しやすいように、方眼紙をxy平面のグラフだと考えてください。
左下の座標が原点、右上は(6,5)ということになります。
(0,0)から(6,5)まで行くのに、４回曲がっていく行き方を考えればいいです。

１回目２回目、３回目、４回目のの通過点をそれぞれ
t1,t2,t3,t4としましょう。

t1のとりうる場所は、
t1=(1,0)(2,0)(3,0)(4,0)(0,1)(0,2)(0,3)
の７とおりあります。
このぞれぞれの場合について場合わけします。

t1=(1,0)のとき
t2=(1,1)(1,2)(1,3)(1,4)の４とおり。
それを(1,k)とおくと、
t3=(2,k)(3,k)(4,k)(5,k)の４とおり。
このとき、t4は一意に決まるので、
４×４＝１６とおり。

t1=(2,0)のとき
t2=(2,1)(2,2)(2,3)(2,4)の４とおり。
そのそれぞれについてt3は
t3=(3,k)(4,k)(5,k)の３とおりあるので
４×３＝１２とおり。

t1=(3,0)のとき
t2=(3,1)(3,2)(3,3)(3,4)の４とおり。
そのそれぞれについて、t3は
t3=(4,k)(5,k)の２とおり。
４×２＝８とおり。

t1=(4,0)のとき
t2=(4,1)(4,2)(4,3)(4,4)の４とおり。
そのそれぞれについて、t3は
t3=(5,k)の１とおり。
４×１＝４とおり。

t1=(0,1)のとき
t2=(1,1)(2,1)(3,1)(4,1)(5,1)の５とおり。(k,1)とすると
そのそれぞれについて、t3は
t3=(k,2)(k,3)(k,4)の３とおり。
t4は一意に決まるので
５×３＝１５とおり。

t1=(0,2)のとき
t2=(1,2)(2,2)(3,2)(4,2)(5,2)の５とおり。
そのそれぞれについて
t3=(k,3)(k,4)の２とおり。
５×２＝１０とおり。

t1=(0,3)のとき
t2=(1,3)(2,3)(3,3)(4,3)(5,3)の５とおり。
そのそれぞれについて、
t3=(k,4)しかない。t4は一意に決まるので
５×１＝５とおり。

以上、全てを足し合わせると
１６＋１２＋８＋４＋１５＋１０＋５＝７０
７０通りとなります。
いずれの場合についても、t4の位置は一意に決まることがポイントです。
ご参考になればうれしいです。