FC2ブログ

Welcome to my blog

[答1402] 2回ずつ訪れる経路

ヤドカリ

ヤドカリ

P5200810.jpg



[答1402] 2回ずつ訪れる経路


 図のように、楕円周上に出発点Sと S以外にn個の点があり、1回の移動で隣の点に移ります。

 (2n+1)回の移動ですべての点を2回ずつ訪れる(ただしSは最初と途中1回)経路は、

 n=3 のとき 次の18個あります。
          1402-隣への移動
 S123S123,S123S321,S1S32123,S121S323,S12321S3,S12323S1,S1S32321,S12123S3,S1S12323,
 S321S321,S321S123,S3S12321,S323S121,S32123S1,S32121S3,S3S12123,S32321S1,S3S32121

 では、n=50 のときの経路の数は? また、n=97 のときの経路の数は?


[解答]

 n=1 のとき、S1S1 の1通り、

 n=2 のとき、

 S1S212,S12S12,S12S21,S121S2,S1212S,S2S121,S21S12,S21S21,S212S1,S2121S の10通り、

 以下 n≧3 として求めます。

 左回りの移動を [⊂]回数 ,右回りの移動を [⊃]回数 ,同じパターンび移動を [パターン]回数 で

 表すことにすれば、[⊂]から始める移動は、

  (1) [⊂](2n+1)

  (2) [⊂](n+1)-[⊃]n

  (3) [⊂]k-[⊃](n+1)-[⊂](n-k) k=1,2,……,n

  (4) [⊂](k-1)-[⊂⊂⊃⊂](n+1-k)/2-[⊂]k
   nが偶数のとき k=1,3,……,n-1 で nが奇数のとき k=2,4,……,n-1

  (5) [⊂]k-[⊃]k-[⊃⊃⊂⊃](n-k)/2-[⊃]
   nが偶数のとき k=2,4,……,n-2 で nが奇数のとき k=1,3,……,n-2

  (6) [⊂]k-[⊃]k-[⊃⊃⊂⊃]m-[⊃](n-2m-k+1)-[⊂](n-2m-k)
   k=1,2,……,n-3 m=1,2,……,[(n-1-k)/2]

  (7) [⊂⊂⊃⊂]k-[⊂](n-2k+1)-[⊃](n-2k)
   nが偶数のとき k=1,2,……,(n-2)/2 で nが奇数のとき k=1,2,……,(n-1)/2

  (8) [⊂⊃⊂]-[⊂⊂⊃⊂](n-1)/2 nが奇数のときのみ

  があり、(1)(2)は 1個ずつ、(3)は n個、(4)(5)の合計は (n-1)個です。

  以下、nが偶数のとき e=1 ,nが奇数のとき e=0 として、

  (6)は Σを k=1,2,……,n-3 のときの和として Σ[(n-1-k)/2] で、

  (n-1-k)の奇数の個数は、(n-3-e)/2個 だから、

  Σ[(n-1-k)/2]=Σ(n-1-k)/2-(n-3-e)/4=Σ(n-1)/2-Σk/2-(n-3-e)/4

  =(n-3)(n-1)/2-(n-3)(n-2)/4-(n-3-e)/4=(n-3)(n-1)/4+e/4個、

  (7)は (n-1-e)/2個 、(8)は (1-e)個ですので、

 2+n+(n-1)+(n-3)(n-1)/4+e/4+(n-1-e)/2+(1-e)=(n2+6n+9-5e)/4 個です。

 [⊃]から始める移動も同数だから、(n2+6n+9-5e)/2 個です。

 このままでもいいのですが、2e=1+(-1)n だから、

 (n2+6n+9-5e)/2=(2n2+12n+18-5・2e)/4={2n2+12n+13-5(-1)n}/4 個です。

 本問では、n=50 ,n=97 の場合なので、

 (2・502+12・50+13-5)/4=1402 通り ,(2・972+12・97+13+5)/4=5000 通りです。

.
スポンサーサイト



Comments 2

There are no comments yet.
スモークマン  
グーテンアーベント ^^

一筆書きに対応させて考えていましたが...
time up...というか...どう考えればいいのか暗中与作でした...^^;;
みなさん、流石です!!

ヤドカリ
ヤドカリ  
Re: グーテンアーベント ^^

スモークマンさん、コメントを有難うございます。
時間のかかる難しい問題だったと思います。
でも、4名の方が正解してくれました。
よく、こんな問題に取り組まれたものだと、
他人事のように言うしかないかも知れません。