FC2ブログ

Welcome to my blog

[答1274] 最短経路

ヤドカリ

ヤドカリ



[答1274] 最短経路


 図のように、東西の道と南北の道が交わっていて、AからBへ最短経路で行き、

 同じ交差点を使わないように、BからAへ最短経路で帰ります。

 東西の道が5本で南北の道が14本のとき、その経路は何通り?

 また、東西の道が5本で南北の道がn本のとき、その経路は何通り?


[参考]

 この道順に囲まれる□の位置が、問題の例では、

 上から 1段目が 1~4 ,2段目が 3~6 ,3段目が 3~10 ,4段目が 9~13 です。

 この囲まれた部分が決まるとその周りを 右回りと左回りの2種類の道順があります。

 上から 1段目が 1~a ,2段目が b~c ,3段目が d~e ,4段目が f~n-1 とすれば、

 1≦a≦n-1 ,1≦b≦a ,a≦c≦n-1 ,b≦d≦c ,c≦e≦n-1 ,d≦f≦e です。

 eが決まれば fは e+1-d 通りですので、

  n-1  a  n-1  c  n-1
  Σ Σ Σ Σ Σ (e+1-d) = (n+2)(n+1)n(n-1)/144 、
  a=1  b=1  c=a  d=b  e=c

 右回りと左回りで、(n+2)(n+1)n(n-1)/72 としても求められますが、

 途中、省略しているΣの計算が大変です。


[解答]

 東西の道がm本で南北の道がn本のとき、(図は東西の道が5本,南北の道が14本のときです)

 右上図のように、Aのすぐ右に┳,Aのすぐ下に┣,Bのすぐ上に┫,Bのすぐ左に┻ の印を付ければ、

 右回りの道順は A,┳,………,┫,B,┻,………,┣,A で表されます。

 行きの「………」の部分は 下へ(m-2)回,右へ(n-2)回の移動で、

 帰りの「………」の部分は 上へ(m-2)回,左へ(n-2)回の移動だから、

 いずれも (m+n-4)!/{(m-2)!・(n-2)!} 通りで、K=(m+n-4)!/{(m-2)!・(n-2)!} とすれば、

 この道順は、K2 通りですが、左下図のような、途中で同じ交差点を通る道順も含まれます。

 途中で同じ交差点を通る場合は帰りに初めて同じ交差点にきたとき、Bを含むループができます。

 この交差点からBを回るルートだけを逆順にする道順は、右下図になり、

 右下図の A,┳,………,┻,B,┫,………,┣,A の道順は行きと帰りで、必ず同じ交差点を通ります。

 従って、左下図の途中で同じ交差点を通る道順と 1対1に対応し、同数です。

 行きの「………」の部分は 下へ(m-1)回,右へ(n-3)回の移動だから、

  (m+n-4)!/{(m-1)!・(n-3)!}=(n-2)K/(m-1) 通り、

 帰りの「………」の部分は 上へ(m-3)回,左へ(n-1)回の移動だから、

  (m+n-4)!/{(m-3)!・(n-1)!}=(m-2)K/(n-1) 通り、

 途中で同じ交差点を通る道順は、(m-2)(n-2)K2/{(m-1)(n-1)} 通りです。

 よって、右回りの道順で同じ交差点を通らないものは、

 K2-(m-2)(n-2)K2/{(m-1)(n-1)}

  ={(m-1)(n-1)-(m-2)(n-2)}K2/{(m-1)(n-1)}=(m+n-3)K2/{(m-1)(n-1)}

  =K・(m+n-3)(m+n-4)!/{(m-2)!・(n-2)!}/{(m-1)(n-1)}=K・(m+n-3)!/{(m-1)!・(n-1)!}

  =(m+n-3)!(m+n-4)!/{(m-1)!・(m-2)!・(n-1)!・(n-2)!} 通りあります。

 左回りのコースも同数あり、

 全部で 2・(m+n-3)!(m+n-4)!/{(m-1)!・(m-2)!・(n-1)!・(n-2)!} 通りです。

 m=5,n=14 のとき、

 2・16!・15!/(4!・3!・13!・12!)=2・16・15・14・15・14・13/(4!・3!)=127400 通りです。

 m=5 のとき、

 2・(n+2)!(n+1)!/{4!・3!・(n-1)!・(n-2)!}=2(n+2)(n+1)n(n+1)n(n-1)/(4!・3!)

 =(n+2)(n+1)2n2(n-1)/72 通りです。

.

スポンサーサイト



Comments 8

There are no comments yet.
ひとりしずか  
No title

いよいよ妖精が……

ニリンソウ  
No title

セリバオウレンですか、葉が違うだけのようですね。
この花が盛りになると
カタクリ、雪割草が出てきます。

POPS  
No title

こんばんは。
この花は見た事がありません。
シベが多く、俯き気味に咲く感じはクリスマスローズの様のも見えますが、違いますよね。
ナイス

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとナイス!をありがとうございます。
春の妖精と言えるような花はいろいろありますが、
セリバオウレンもいち早く春を知らせてくれる花です。

ヤドカリ  
No title

ニリンソウさん、コメントをありがとうございます。
そちらはキクバオウレンですね。
ユキワリソウも花の文化園で少し見ましたが、
まだ見栄えはしませんでした。

ヤドカリ  
No title

POPSさん、コメントとナイス!をありがとうございます。
セリバオウレンという野草です。
春になると咲き出す花のひとつです。

スモークマン  
No title

グーテンアーベント ^^
結局わからず...^^;
未だに熟読玩味中...^^;;
簡単そうなのに難しい問題は面白いけど...
アイデアが浮かばないと歯が立ちませんですばい...Orz...

ヤドカリ  
No title

スモークマンさん、コメントとナイス!をありがとうございます。
結局はABの往復から条件に合わなものを除くのですが、
条件に合わないものは∞の形の経路と同数だということです。