Taro
あれ?
間違えたと思って再検証していたんですが(激汗)
○saka   1月22日(木) 0:05:36   MAIL:tarox@nifty.com HomePage:もうひとつの理科チャレ2  20339
拓パパ
やられました、70+20+6+2=98と回答して安心していました.
都内某所   1月22日(木) 0:09:07   MAIL:dr-yasu@nifty.com   20340
kasama
受験生皆さん、センター試験お疲れ様でした。いよいよ、これからが正念場ですね。ご健闘を祈っております。頑張れ!受験生。

で、私は今回もプログラムです。
public class Question387 {
 private static int count = 0;
 public static void main(String args[]) {
  walk(1, 1, false);
  walk(1, -1, false);
  System.out.println("マサルさんがA地点を出発点にして8秒間歩くとき、その途中で1度以上A地点に戻っているような歩き方は" + count + "通りです");
 }
 private static void walk(int n, int p, boolean flag) {
  if (p == 0) flag = true;
  if (n >= 8) {
   if (flag) ++count;
   return;
  }
  walk(n+1, p+1, flag);
  walk(n+1, p-1, flag);
 }
}

#20364 に合わせて再々修正(2004/01/22)
和歌山   1月22日(木) 14:24:39   MAIL:kasama@s34.co.jp   20341
DCT
98とかその辺の答えを送ってしまった・・・w
   1月22日(木) 0:10:27     20342
浜直君
8×2=1616=4二乗よって4×4ますのイチイチ解法でOKですよね。
   1月22日(木) 0:12:26     20343
DCT
2連続ですいません^^;
14秒って・・・w  あーもっと柔軟にしなきゃ
   1月22日(木) 0:12:45     20344
ほげ
8秒間歩くとは書いていなかったのでたとえば2秒で戻ってきたら
そこで打ち切りだと思っていました。で18通りにしてました。

まさかと思ってC(8,4)を計算したけど
70通りだと 
右左右右右右右右は考えないんでしょうか
「8秒以内にA地点に戻って」きてますよ?? 
   1月22日(木) 0:25:26   MAIL:micci@sansu.org   20346
CRYING DOLPHIN
???70通り??

こんな場合はどうなるんでしょう?
「右左(←この時点でAに着いている)左左左左左左」
これだと、70通りには含まれていないはずですが。。

それとも、私が題意を思い切り勘違いしてる?
1年ピカチュウ組   1月22日(木) 0:25:34   HomePage:算数の限界ってどのくらい?  20347
みかん
右が4つ、左が4つを一列に並べるというパターンですね。
(8!)÷(4!×4!)=70
   1月22日(木) 0:27:04     20348
kasama
#20347#20346 私もそう思いました。8秒以内⇒8秒ピッタリの方が適当ですね。
和歌山   1月22日(木) 0:29:04   MAIL:kasama@s34.co.jp   20349
ミキティ
#20346,#20347
に同じく、70を答えた後、違うと思い***を答えました……。
   1月22日(木) 0:29:11     20350
吉川 マサル
う、しまった...。

 まず問題文ですが、「8秒間歩くとき、一度でもA地点に戻っているような」歩き方は何通り?としなくてはなりませんでした。現状ですと、「18通り」のほうも正解としなくてはならない気がします。

 C-Dさん及びほげさんの疑問例については、ちょっと考えてみます。m(__)m
MacOS X   1月22日(木) 0:29:24   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20351
ほげ
C-Dさん と意見が一致しましたね
その場合の数は 186通りになりますか
北の隠れ家   1月22日(木) 0:30:40   MAIL:micci@sansu.org HomePage:みっちの隠れ家  20352
GoBack
2+(4-2)+(20-(2+(4-2)))+(70-(20-(2+(4-2))))=70?
   1月22日(木) 0:36:20     20353
CRYING DOLPHIN
#20352
はい、そうなりました。
(まだこっちの方の解き方は書かないほうがいいだろうか…)

#20351
「8秒間歩くとき、一度でもA地点に戻っているような」という言い方だと、
やはり「右左右右右右右右」もカウントしなければならなくなると思いますが、
いかがでしょうか…
1年ピカチュウ組   1月22日(木) 0:38:20   HomePage:算数の限界ってどのくらい?  20354
吉川 マサル
#20354
 はい、「右左右右右右右右」も1通りとしてカウントするというのが題意です。答えのほうはもう一度検証してみます...。m(__)m
MacOS X   1月22日(木) 0:41:26   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20355
もありす55
今回ばっかりはミスがひどすぎますね(^^;
以内とちょうどじゃ違いすぎでしょ。
   1月22日(木) 0:47:47     20356
吉川 マサル
ゴメンナサイ、私のミスの内容が分かりました。

 なんと「8秒以内に一度もA地点を通らない場合」を計算していることに気付かず、256から引くのを忘れていました....。
MacOS X   1月22日(木) 0:47:50   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20357
辻。
最初「8秒以内にぴったり戻る」と解釈し18通り
でも掲示板に入れないので他の回答を考える
次に「1回戻ってもまた歩き出して8秒後にAに戻ってくる」と
考えますが、これだと8C4=70 で簡単すぎるのでは?
と思い認証したら入れました(^^)
やや風邪気味   1月22日(木) 0:50:25   HomePage:辻部屋。  20358
まるケン
8秒後にAに戻る歩き方と、8秒間一度もAに戻らない歩き方とが同じ数になるんですね。これはこれで、ちょっとした発見。
ちなみに、10秒後にAに戻る歩き方も10秒間一度もAに戻らない歩き方は、やっぱりどちらも252通りで一緒になります。
ふしぎだぁ、、、

   1月22日(木) 1:04:17   MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋  20359
ほげ
http://micci.sansu.org/zukei/santyare-387.htm
に解法を掲載しました。
#20347
>まだこっちの方の解き方は書かないほうがいいだろうか
答えを書いてしまったので解法もUPしました。
#20359 まるケンさんのように不思議だと思います
きっと目からうろこ があるんでしょうね。
眠たいので 明日かんがえてみようっと
その間にどなたかがカキコしてくれるかも...(^.^)

北の隠れ家   1月22日(木) 1:09:51   MAIL:micci@sansu.org HomePage:みっちの隠れ家  20360
takaisa
2^8-8C4=256-70=186
   1月22日(木) 1:11:07     20361
まるケン
一人ぼけ、一人突っ込みです。

#20359 を利用すると、たとえば数え上げは難しそうな数ということで、

「16秒後に一度もAに戻らない歩き方は何通り?」

なんて問題にすると、一見なかなか難しそうでGOODですね。
   1月22日(木) 1:11:57   MAIL:take4310@mobile.email.ne.jp HomePage:まるケンの部屋  20362
ほげ
順位表が新しくなりましたね。
正解値を送付しておきました。

この掲示板にはまだ○○ではいれるようなので 数値を変えたほうがいいのでは。

必要なら 私のカキコの正解の数値や解法のURLは消しても結構です。
メールを見る暇がないだろうと思いここに書きました
では おやすみなさい
北の隠れ家   1月22日(木) 1:20:13   MAIL:micci@sansu.org HomePage:みっちの隠れ家  20363
吉川 マサル
今回のミスに関する処置についてご報告します。

 まず、問題文については、当初は「8秒以内に戻ってくるような歩き方の場合の数」(ちょっと表現が違うかも知れません...。手元のファイルも直してしまったので)というものでした。訂正後は「8秒間歩くとき、その途中で一度でもAに戻ってくるような歩き方の場合の数」としました。
 訂正前の文章からの解釈としてありえるものは、「8秒以内にAに戻ってきて、その後動かない」(これだと18通り)というものと、新しい問題文の題意(これだと186通り)だと思います。8秒ぴったりで帰ってくる、というのは解釈に無理があるかと思います...。

 ということで、訂正前の答えとして(ただし、それを見る時間のことも考えて)は、午前1時までの答案としては、「18通り」および「186通り」の2通りを正解扱いといたします。

 「70通り」につきましては、「8秒ぴったりで帰ってくる場合」と、私のミスした「8秒以内で1度もAに戻らない場合」が偶然(ではなくて実は必然なのですが)一致してしまった故に私が正解扱いとしてしまったものですので、大変申し訳ありませんが、不正解扱いとさせていただきます。(このページには現在は70で入れるようになっていますが、2時くらいには186でのみ入れるようにするつもりです)

 今回のミスの原因は#20357にあるようなかなり単純なものでした。#20359のまるケンさんの書きこみにあるように、実は「8秒間1度もAに戻らない歩き方」と「8秒後ぴたりにAに戻ってくる歩き方」は一致する(偶数秒後であれば必ず一致する)のですが、それを意識しすぎてミスしてしまいました。申し訳ありませんでした。

 今回の件で気を悪くされた、あるいは迷惑を被った多くの方々に深くお詫び申し上げます。すみませんでした。m(__)m
MacOS X   1月22日(木) 1:20:56   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20364
ひだ弟
恐れ入ります、0:30より前くらいに18で送ったつもりですが順位表にありません。送り間違えでしょうか?
   1月22日(木) 1:30:56     20365
Taro
出題ミスでしたか。偶然にも正解が一致したのと思ってました(大汗)

はじめ2秒右に行った際に残り6秒で出発点に戻らない場合をカタラン数を
求めるようなマス目を書いて調べ、それを2倍し256から引きました。
http://homepage1.nifty.com/t/387.png のような図です。
○saka   1月22日(木) 1:37:33   MAIL:tarox@nifty.com HomePage:もうひとつの理科チャレ2  20366
Taro
#20360
げ!同様の図が先に描かれてました(^^;
○saka   1月22日(木) 1:40:42   MAIL:tarox@nifty.com HomePage:もうひとつの理科チャレ2  20367
吉川 マサル
とりあえず、AM 1:00以前のメイルについて、18および186を正解として順位表を作成しなおしました。

#20365
 調べてみました。ひだ弟さんからは、0:04と0:28にメイルを頂いていて、前者は16、後者は70となっていました。m(__)m
MacOS X   1月22日(木) 1:45:44   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20368
トトロ@N
用事で遅くなりましたが、それが良かったようです。
2秒後、4秒後、6秒後、8秒後に初めてAに戻る場合に分けて考えました。
兵庫県明石市   1月22日(木) 1:57:02   MAIL:h-sakai@zb3.so-net.ne.jp   20369
ひだ弟
えっ、18? どこでどうしくじったか。お恥ずかしい限りです。
。。。あってれば結構いいタイムだったなぁ。

確認ありがとうございます。>マサルさん
   1月22日(木) 2:03:02     20370
はなう
ありゃりゃ、掲示板に入れないから、もう今日は諦めようっておもって寝てました。風邪で熱があるもので。。

186か18でいいんですね、良かった。
場合の数が解けないのはやだなとか思って寝ながら小一時間考えてました(笑
   1月22日(木) 2:11:02     20371
ひだ弟
#20370
うわ〜間違えた。「えっ、16(で送ってました)?」と書きたかったのです。
訳わからないコメントになってますね。
   1月22日(木) 2:15:13     20372
仮面ランナー サブスリー
<A HREF="javascript:comment('20368')">#20368</A>
失礼します。私も0:20に18を送信していないでしょうか?
<BR>その寸前に10(丁度8秒後に戻る場合)も送ったようですが...
   1月22日(木) 2:17:16     20373
吉川 マサル
#20373
 調査しましたら、ちゃんとありました。失礼いたしました。m(__)m
MacOS X   1月22日(木) 2:47:50   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20374
仮面ランナー サブスリー
#20374
どうもお手数おかけしました。>マサル様
タグいらなかったのか〜(謎
   1月22日(木) 3:13:07     20375
かんクン
訂正後の問題文を見て、176通りでここに入れず悩んでいました。
「途中で1度以上」とあるので、8秒後に初めてA地点に戻ってくる場合
は数えないのが普通なのでは? でも「訂正とお詫び」を見て、ひょっと
したらと思ったら、ここに来れました。
   1月22日(木) 3:30:43     20376
とまぴょん
訂正後の問題をみて納得です。
酔ってるので、一度A地点に戻ってきても、そこで立ち止まることなくふらふらして通過するやろうなあと考えていましたので・・・

>「70通り」につきましては、「8秒ぴったりで帰ってくる場合」と、私のミスした「8秒以内で1度もAに戻らない場合」が偶然(ではなくて実は必然なのですが)

なぜ必然なのか、わかりやすいご説明があるとうれしいです

   1月22日(木) 5:12:31   MAIL:y-tomari@zd5.so-net.ne.jp   20377
UnderBird
座標で、原点スタート、右を右1、左を上1に移動と考えると、8回目の場所は、(0,8)(1,7)(2,6)(3,5)(4,4)(5,3)(6,2)(7,1)(8,0)で(1,1)(2,2)(3,3)(4,4)を通らないで各格子点上へ行くまでの回数を対称性も含めて数えました。
   1月22日(木) 8:07:19   MAIL:shimotorikouichi@hotmail.com   20378
あ〜く@旧N
xy平面上で格子点を置き、x軸、y=x、y=-x+8で囲まれた内部の点を考える。
このとき、原点から出発しy=-x+8に到着する場合の数を調べればよい。
(x軸上に戻っては行けない)
すると、その場合の数は7+14+14=35となるので、求める場合の数は
2~8 -35*2 =186

・・・疲れて家に帰ってきて即寝てしまいました・・・今回のは最初から解き方が分かったためか少々自分の阿呆らしさを責めながら解いていましたw

こういう問題は格子点問題に置き換えると分かりやすいですね(と思うのは私だけ?)
   1月22日(木) 8:15:06     20379
ほげ
0:05ごろに解答を送付していると思います。でも他の名前で掲載されてるからいいかな(*^。^*) (謎)
得意の送付忘れ といううわさもあるし。
北の隠れ家   1月22日(木) 8:43:58   MAIL:micci@sansu.org HomePage:みっちの隠れ家  20380
ハラギャーテイ
おはようございます。

カタラン数が頭に浮かびました。長年の経験でした。

九州は雪です。どうやって行こうかと思っています。
北九州   1月22日(木) 9:39:00   HomePage:ハラギャーテイの制御工学にチャレンジ  20381
M.Hossie
 こんばんにゃ。ほげ様や Taro 様が描かれている図と同じやり方です。256通りから、一度も原点を通過しない場合を引き算するという余事象の考えですね。
都内某所   1月22日(木) 9:57:28     20382
小西孝一
おはようございます。
2秒後で初めてが2×2^6=128、
4秒後で初めてが2×2^4=32、
6秒後で初めてが4×2^2=16
8秒後で初めてが両端4こが2通り×真ん中4こが5通り=10
と超地道にやりました。
ど田舎   1月22日(木) 10:18:18     20383
ミミズクはくず耳
ありそうなのに初めてのパターンの問題でした。
解き方は例によって碁盤の目の街路図で、
カタラン数と同様に斜め半分にして、
初めて戻るものを数え、残りの回数は好きに行っていいです。
しかし、いろんな変形があるものですね。
会社かなっ!   1月22日(木) 11:39:20   MAIL:mae02130@nifty.com   20384
吉川 マサル
#20380
 えと、どんなお名前でお送りになっているでしょう?「ほげ」様で検索しても見つからなかったのですが...。
MacOS X   1月22日(木) 15:10:01   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20385
ほげ
なかったですか … 5分以前に掲示板に入ろうとして入れず
そういえば問題UP後 5分たたないと 掲示板がひらかないんだなあ
開くまでの間に答を送っとこう と 送付した記憶があるのですが…

答とコメントを書いて 送付をわすれたかも知れないですね
いいです いいです 別名で正解者に乗ってるし(^。^)
お手数をおかけしました。

HNを使い分けてるわけではないのですが 本名とごっちゃになっている
今日この頃です。(*^_^*)
北の隠れ家   1月22日(木) 16:12:46   MAIL:micci@sansu.org HomePage:みっちの隠れ家  20386
寝不足文君
こんばんわ、8回ぐらい入れてやっと正解しました。やっぱ小学5年じゃきついです。この問題とくのに、だいぶ時間たちました。でも100位以内には入れてよかったです。最初ときかた分からなくて、なんとなく計算したので入力しましたが、最後は256通りからおかしいのをすべて出してそれを引きました。
もっと簡単な方法見つけられればなぁと思っています。
   1月22日(木) 19:46:25   MAIL:eido@kyoto.email.ne.jp   20387
とまぴょん
題意を2n秒後の場合に拡張してみました。カタラン数を考えながら、combination とシグマと2のべき乗で下記のようになりました。
堯(2rCr / r+1) x 2^{2(n-r)-1} 〕 (ただし r = 0 to n-1 )  

8秒後は上式でn=4として186です

#20364のはなしでは、上式と2^(2n)−2nCn は等しいということになりますね。 不思議ですねえ・・
   1月22日(木) 20:21:41   MAIL:y-tomari@zd5.so-net.ne.jp   20388
いちたすには
「かんクン」さんに同感です
「途中」なんだから2、4、6秒後だろうって思いました
   1月22日(木) 21:04:58     20389
n
えーーーだいぶおくれますタ
   1月22日(木) 21:30:56     20390
n
>M.Hossieさん
やはりセンターの処理能力は地道に演習するしかないんですね。
地道に磨いていきます。ありがとうございました

昨日考えて頭がごちゃごちゃして解けなかった。返答する前に問題UPされました。
   1月22日(木) 21:37:25     20391
zizi
プログラムで解きました。
右と左を二進数であらわして00000000から11111111までの256通りを
0だったら-1、1だったら1と左から交互に足して途中で0になったら当たり。
算数で解きたいです。
   1月22日(木) 21:52:53     20392
なか
出遅れました。

2^8−8C4=186、
パスカルの三角形の8段目の「中央の70」を除く和ともいえる。
ちゃんと一般項も 2^n−2nCn。

うーむ、裏返しだ。
8秒後に原点にいる場合の数と、
一度も原点にこない場合の数が等しいということですが、なんでだろう。
北海道   1月22日(木) 23:58:36   MAIL:naka@sansu.org HomePage:naka's Home Page  20393
なか
酔歩

今回の問題のような確率過程を学術用語で「酔歩」といいます。
random walk を 酔歩 と翻訳した学者さん、よほどお酒が好きだった?
北海道   1月23日(金) 0:07:39   MAIL:naka@sansu.org HomePage:naka's Home Page  20394
Taro
時間を2秒単位で回を出していくと2,10,44,186,772のように続くようです。
ここにありました
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A068551
○saka   1月23日(金) 0:30:57   MAIL:tarox@nifty.com HomePage:もうひとつの理科チャレ2  20395
吉川 マサル
#20389#20376
 仰る通り、曖昧な表現でした。訂正させていただきます。重ね重ねの失態、申し訳ありません...。m(__)m
MacOS X   1月23日(金) 1:03:09   MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ  20396
小学名探偵
2n歩目に元の位置にいる場合の数2nCnと、
2n歩までに一度も元の位置を通らない場合の数が等しいのは何故?

よく分かってないのですが、+側の半分だけ考えて、例えば、8歩のときは、
ほげさんにしたがって
1,6,14,14になり、これを記号でa1, a2, a3, a4とします。最後のa4=14は
カタラン数です。
2n歩目のとき、a1, a2,...anまであり、その合計S(n)が2nCn/2に等しいとします。
2n歩目のときの合計S(n+1)=4*S(n) - an
になります。
以下計算すると、
S(n+1)=4*S(n) - an
   =4/2(2nCn ) -2nCn/(n+1)
   =2n!*2/(n!*n!) -2n!/{n!*(n+1)!}
   =(2n+1)!/{n!*(n+1)!}
   =(1/2)2(n+1)!/{(n+1)!*(n+1)!}
   =(1/2)*2(n+1)C(n+1)
ということで帰納的に求められます。
もっと分かりやすいのがありませんか。
   1月23日(金) 19:45:11     20397
小学名探偵
8行目は”2(n+1)歩目”に読み替えてください
   1月23日(金) 19:48:13     20398

カタラン数?(゜゜)シラネ。でも問題は面白かた
   1月23日(金) 20:49:06     20399
ちこりん
>無名子さん
上下にどうやって移動するのかは聞かないほうがいいですか?
   1月24日(土) 21:18:32     20401
小学名探偵
8歩目に元の位置に戻る経路の数と、それまでに
一度も元の位置を経ることがない経路の数が等しいということですが、
なぜでしょう?

やっぱり、算チャレ第330回で話題になったような
乗り換えの法則(対称性の置換)で説明できそうです。
実際に説明すると面倒なんですが、以下に試みます。
いま、(a, b)という記号において、aは元の位置から「右にa歩」を表し、
bは「左にb歩」を表すとします。
例えば、(2,3)は右に2歩、左に3歩の位置にいることを表します。
例えば、(3,3)や(4,4)は元の位置にいることになります。
この(a, b)を座標に見立て、8*8の8路盤
(というか直角2等辺三角形で等辺の長さが8のものを
一辺が1の正方形で区分けしたような形)
を考えます。例えば左上を原点(0,0)にとります。

次に一対一の対応を、原点から
(4,4)の位置に至る経路と、
一度も元の位置を経ることなしに直角2等辺三角形の斜辺
(対角線)上の他の位置(8,0)、(7,1)、…(1,7)、(0,8)
に至る経路との間でチェックするために、
両者の間で経路の一部交換(乗り換え)をします。
例えば、位置(8,0)との間では原点(0,0)から
(4,0)までは同じ経路ですが、
(4,0)から(8,0)に至る経路は
(4,0)から(4,4)に至る対称な経路に置換します。
つまり、「(4,0)と(8,4)を結ぶ直線」について
対称な経路に変換します。
同様にして、例えば位置(6,3)との間では
位置(4,3)後の(6,3)までの経路を、
(4,3)と(5,4)を結ぶ直線について
対称な経路に変換します。
以上のような対称経路置換(乗り換え)を
(8,0)、(7,1)、…(1,7)、(0,8)の
すべての位置までの経路について行うと
(0,0)から(4,4)に至るすべてのランダムウォーク経路が
カバーされます。要するに、
一度も元の位置を経ることなしに
(8,0)、(7,1)、…(1,7)、(0,8)の各位置に至る各経路について、
適当な対称経路交換により8歩目に元の位置に至る経路に変換でき、
逆に、8歩目に元の位置に至る経路のそれぞれについて
適当な対称経路変換により(8,0)、(7,1)、…(1,7)、(0,8)の
いずれかの位置に至る経路に変換できます。
よって、両者の経路の数は同じです。
   1月25日(日) 7:43:11     20402
とまぴょん


以上のような対称経路置換(乗り換え)を
(8,0)、(7,1)、…(1,7)、(0,8)の
すべての位置までの経路について行うと
(0,0)から(4,4)に至るすべてのランダムウォーク経路が
カバーされます。

小学名探偵さん、帰納法に引き続きすばらしい考察ですね。
私も同様なことを考えていたところでした。ただ、上記のことがいえそうだけど数学的にきちっとできないところで悶々としておりました。
数式ですぱっといえるとすっきりするんですけどね。
   1月25日(日) 12:03:59   MAIL:y-tomari@zd5.so-net.ne.jp   20403
数楽者
小学名探偵さんご苦労さまです。
最終到達点と(4,4)を結ぶ線分の垂直二等分線に関する対称変換ですね。
気になることがあります。
次の4経路がこの方法では同じ相手に変換される気がします。
その4経路は、すべて(4,0)を通ります。
第1経路はそこから(8,0)へ行きます。
第2経路は、(4,1)を経由して(7,1)へ行きます。
第3経路は、(4,2)を経由して(6,2)へ行きます。
第4経路は、(4,3)を経由して(5,3)へ行きます。
変換後の経路はすべて(0,0)-(4,0)-(4,4)になると思います。
何か工夫があるといいのですが。
私の勘違いでなければいいのですが。
横浜   1月25日(日) 17:52:48   MAIL:iida@ae.keio.ac.jp   20404
小学名探偵
数学者さんへ
実はその問題が解けていないのです。すみません。
   1月25日(日) 20:21:25     20405
小学名探偵
数楽者さん、とまぴょんさんへ
ご指摘ありがとうございます。
何か工夫して、1対1の対応が明確になると良いのですが
よろしくおねがいします。
   1月25日(日) 20:53:42     20406
遠い山のぽきょぽん
今回は間違った答えでここに入ったときに正しい答えの数値を見てしまったので
順位表には不参加とします。
解法は2^8からカタラン数みたいなのを引きました。

入った後に再考するのを今回に限って怠ってしまったのが残念です。
遠い山から   1月25日(日) 22:37:23     20407
小学名探偵
数楽者さんへ
>第1経路はそこから(8,0)へ行きます。
これについては、(4,0)の位置で乗り換えます(変換します)。
>第2経路は、(4,1)を経由して(7,1)へ行きます。
2つのゴール(4,4)と(7,1)を結ぶ線分の垂直二等分線は(3,0)を通ります。
ここで乗り換えます。
>第3経路は、(4,2)を経由して(6,2)へ行きます。
2つのゴール(4,4)と(7,1)の垂直二等分線は(2,0)を通ります。
ここで乗り換えます。
>第4経路は、(4,3)を経由して(5,3)へ行きます。
2つのゴール(4,4)と(7,1)の垂直二等分線は(1,0)を通ります。
ここで乗り換えます。

実は、いま6*6(6歩のランダムウォーク)で考えてます。
原点から(2,0)、(2,1)を経て(5,1)に至る経路は
原点から(1,0)、(1,1)、(3,1)を経て(3,3)に至る経路
に対応させないといけないようですが、上の方法だけでは無理で
一工夫要りそうです。
   1月26日(月) 0:26:55     20408
小学名探偵
訂正 
数楽者さんへ
>第1経路はそこから(8,0)へ行きます。
これについては、(4,0)の位置で乗り換えます(変換します)。
>第2経路は、(4,1)を経由して(7,1)へ行きます。
2つのゴール(4,4)と(7,1)を結ぶ線分の垂直二等分線は(3,0)を通ります。
ここで乗り換えます。
>第3経路は、(4,2)を経由して(6,2)へ行きます。
2つのゴール(4,4)と(6,2)の垂直二等分線は(2,0)を通ります。
ここで乗り換えます。
>第4経路は、(4,3)を経由して(5,3)へ行きます。
2つのゴール(4,4)と(5,3)の垂直二等分線は(1,0)を通ります。
ここで乗り換えます。
   1月26日(月) 0:32:33     20409
小学名探偵
もう少し整理してみます。
その前に、8歩目に元に位置に戻るようなランダムウォークを
帰巣型と呼び、8歩目(一般的には2n歩目)までに
一度も元の位置を経ないランダムウォークを
家出型と呼ぶことにします。
また、最初の一歩が”→”に進むランダムウォークを前向きと
呼び、最初の一歩が”←”に進むランダムウォークを後ろ向きと
呼ぶことにします。そして、
家出型のゴール(例えば、(8,0)、(6,2)の地点)と
帰巣型のゴール(4,4)を結ぶ線分の垂直二等分線を
対称軸と呼ぶことにします。

経路の乗り換え(交換)の条件、方法は、
1)前向き家出型の経路は前向き帰巣型経路に対応させ、
後ろ向き家出型の経路は後ろ向き帰巣型経路に対応させます。
2)前向き家出型の経路が(x、0)の位置で、つまりx軸上の位置で、
対称軸と「交差」するときは、
その交差点で乗り換えます。すなわち、
交差点から前向き家出型の経路のゴールまでのパスを
対称軸について対称なパスに交換します。これにより、
前向き帰巣型経路の1つに変換されます。
後ろ向きについては、家出型の経路が(0、y)の位置で対称軸と
交差するときは、その交差点で乗り換えます。
3)前向き家出型の経路が(x、0)の位置(x軸上)で対称軸と
交差しないときはどうするか、これが課題です。
この前向き家出型の経路が(x、y)の位置(yは0でない)で対称軸と
交差するとき、その交差点から乗り換えを行います。
ただし、この乗り換えだけだと不十分で
(つまり、1対1対応にならないので)、この交差点に着く
前のパスについても「なんらかの適当な交換」を行うようにします。
これが課題です。このようなケースでは、「最初」のパス交換位置は
やはりx軸上で行わなくてならないはずです(前向きの場合)。
もちろん、このパス交換は
対称軸について対称にはなりません。
いま、分かっているのはこの程度で、あとは皆様にお願いします。
   1月26日(月) 15:43:29     20410
linearsupertrain
全体(2の8乗)から途中や最後に一度も原点を経ない歩き方(n通り)を引く方法でけっこう楽に解けました。nの求め方は以下の通りです:
nに含まれる全ての歩き方は、必ず反対側への1通りの対称な行き方があります。(例:→→→→→→←←と←←←←←←→→)なので一方通行で計算したn'の2倍がnになります。n'を求めるには、歩き始めるからの連続の歩数で場合わけするとよいでしょう。
   1月26日(月) 19:43:33   MAIL:secret   20411
小学名探偵
#20410の続きです。
一応、解けたようです。

家出型経路と帰巣型経路間のパス交換に関する
基本的性質やルールは次の通りです。
(1)ある前向きの帰巣型経路K(i)を前向きの家出型経路I(i)に変換する場合:
この場合、原点から帰巣型経路K(i)のゴールに向かって
辿っていって、順次、経路I(i)の各部を決めていくのがよいようです。
(1_0)最初の一歩は同じです。(0,0)から(1,0)へ
(1_1)経路K(i)があるノード(x,y)で↓ターンするとき、すなわち、
(x-1, y)、(x, y)、(x, y+1)を通るとき、
経路K(i)のノード(x,y)に対応する経路I(i)のノードを
(s, t)とすると、経路I(i)はそこから(s+1, t)に進ませます。
s>=x、t<=y
(1_2)経路K(i)があるノード(x,y)で→ターンするとき、すなわち、
(x, y-1)、(x, y)、(x, y+1)を通るとき、
経路I(i)は(s, t)から(s+1, t)に進ませます。
(1_3)経路K(i)と経路I(i)が再び(x,y)で出会ったならば、
経路K(i)がそこで↓ターンすればルール(1_1)を経路I(i)に適用します。
そこで↓ターンしなければ次に経路K(i)が↓ターンするところまで
経路I(i)は同じパスを進みます。

例:帰巣型経路が
(0,0)、(1,0)、(1,1)、(2,1)、(3,1)、(3,2)、(4,2)、ゴール(4,4)の場合、
(0,0)、(1,0)、(2,0)、(2,1)、(3,1)、(3,2)、(4,2)、ゴール(6,2)
の家出型の経路に変換されます。

(2)ある前向きの家出型経路I(i)を前向きの帰巣型経路K(i)に変換する場合:
この場合、家出型経路I(i)のゴールから原点に向かってさかのぼっていって、
順次、経路K(i)の各部を決めていくのがよいようです。
このさかのぼる方向において:
(2_0)最初の一
   1月27日(火) 20:58:23     20412
小学名探偵
#20410の続きです。
一応、解けたようです。

家出型経路と帰巣型経路間のパス交換に関する
基本的性質やルールは次の通りです。
(1)ある前向きの帰巣型経路K(i)を前向きの家出型経路I(i)に変換する場合:
この場合、原点から帰巣型経路K(i)のゴールに向かって
辿っていって、順次、経路I(i)の各部を決めていくのがよいようです。
(1_0)最初の一歩は同じです。(0,0)から(1,0)へ
(1_1)経路K(i)があるノード(x,y)で↓ターンするとき、すなわち、
(x-1, y)、(x, y)、(x, y+1)を通るとき、
経路K(i)のノード(x,y)に対応する経路I(i)のノードを
(s, t)とすると、経路I(i)はそこから(s+1, t)に進ませます。
s>=x、t<=y
(1_2)経路K(i)があるノード(x,y)で→ターンするとき、すなわち、
(x, y-1)、(x, y)、(x, y+1)を通るとき、
経路I(i)は(s, t)から(s+1, t)に進ませます。
(1_3)経路K(i)と経路I(i)が再び(x,y)で出会ったならば、
経路K(i)がそこで↓ターンすればルール(1_1)を経路I(i)に適用します。
そこで↓ターンしなければ次に経路K(i)が↓ターンするところまで
経路I(i)は同じパスを進みます。

例:帰巣型経路が
(0,0)、(1,0)、(1,1)、(2,1)、(3,1)、(3,2)、(4,2)、ゴール(4,4)の場合、
(0,0)、(1,0)、(2,0)、(2,1)、(3,1)、(3,2)、(4,2)、ゴール(6,2)
の家出型の経路に変換されます。

(2)ある前向きの家出型経路I(i)を前向きの帰巣型経路K(i)に変換する場合:
この場合、家出型経路I(i)のゴールから原点に向かってさかのぼっていって、
順次、経路K(i)の各部を決めていくのがよいようです。
このさかのぼる方向において:
(2_0)最初の一歩は反対です。
(2_1)経路I(i)があるノード(s, t)で↑ターンするとき、すなわち、
(s+1, t)、(s, t)、(s, t-1)を通るとき、
経路I(i)のノード(s, t)に対応する経路K(i)のノードを
(x, y)とすると、経路K(i)はそこから(x-1, y)に進ませます。
(さかのぼっているので実際には戻らせているのですが)
s>=x、t<=y
(2_2)経路I(i)があるノード(s, t)で←ターンするとき、すなわち、
(s, t+1)、(s, t)、(s-1, t)を通るとき、
経路K(i)は(x, y)から(x, y-1)に進ませます。
(2_3)経路I(i)と経路K(i)が(s, t)で出会ったならば、
経路I(i)がそこで↑ターンすればルール(2_1)を経路K(i)に適用します。
そこで↑ターンしなければ次に経路I(i)が↑ターンするところまで
経路K(i)は同じパスを進みます。

例:さかのぼる方向で見て、家出型の経路が
(6,2)、(4,2)、(4,1)、(3,1)、(2,1)、(2,0)、(1,0)、(0,0)の場合、
(4,4)、(4,2)、(3,2)、(3,1)、(2,1)、(1,1)、(1,0)、(0,0)に
変換された帰巣型経路が出来ます。
   1月27日(火) 20:58:24     20413
小学名探偵
#20413で述べた方法(ルール)で、ある帰巣型経路を家出型の経路に変換した場合、
または、この逆の変換をした場合、両経路について次の位置関係が保たれます。
任意のステップ(原点からk番目のステップ)において、
帰巣型経路の位置(x, y)と家出型の経路の位置(s, t)との間には、
45度の位置関係があります。
(両者が同じ位置のときも45度の位置関係にあるとみなします)

つまり、この45度の位置関係を保ちながら、変換するわけです。

したがって、異なる帰巣型経路は異なる家出型経路に変換され、
この逆も真です。
したがって、
(n, n)をゴールとする帰巣型経路の個数と、l+m=2nである
(l, m)をゴールとする家出型経路の個数は等しいです。
   1月27日(火) 23:42:57     20414