茖確�

Taro

あれ？
間違えたと思って再検証していたんですが(激汗)

○saka　　 1月22日（木） 0:05:36　　 MAIL:tarox@nifty.com HomePage:もうひとつの理科チャレ２　　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("マサルさんがＡ地点を出発点にして８秒間歩くとき、その途中で１度以上Ａ地点に戻っているような歩き方は" + 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とかその辺の答えを送ってしまった・・・ｗ

　　 1月22日（木） 0:10:27　　　　20342

浜直君

8×2＝1616＝4二乗よって4×4ますのイチイチ解法でＯＫですよね。

　　 1月22日（木） 0:12:26　　　　20343

DCT

2連続ですいません＾＾；
14秒って・・・ｗ　　あーもっと柔軟にしなきゃ

　　 1月22日（木） 0:12:45　　　　20344

ほげ

８秒間歩くとは書いていなかったのでたとえば２秒で戻ってきたら
そこで打ち切りだと思っていました。で18通りにしてました。

まさかと思ってC(8,4)を計算したけど
70通りだと　
右左右右右右右右は考えないんでしょうか
「８秒以内にＡ地点に戻って」きてますよ？？　

　　 1月22日（木） 0:25:26　　 MAIL:micci@sansu.org 　　20346

CRYING DOLPHIN

？？？７０通り？？

こんな場合はどうなるんでしょう？
「右左（←この時点でＡに着いている）左左左左左左」
これだと、７０通りには含まれていないはずですが。。

それとも、私が題意を思い切り勘違いしてる？

１年ピカチュウ組　　 1月22日（木） 0:25:34　　 HomePage:算数の限界ってどのくらい？　　20347

みかん

右が４つ、左が４つを一列に並べるというパターンですね。
（８！）÷（４！×４！）＝７０

　　 1月22日（木） 0:27:04　　　　20348

kasama

#20347、#20346　私もそう思いました。８秒以内⇒８秒ピッタリの方が適当ですね。

和歌山　　 1月22日（木） 0:29:04　　 MAIL:kasama@s34.co.jp 　　20349

ミキティ

#20346,#20347
に同じく、70を答えた後、違うと思い***を答えました……。

　　 1月22日（木） 0:29:11　　　　20350

吉川　マサル

う、しまった...。

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

　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
「８秒間歩くとき、一度でもＡ地点に戻っているような」という言い方だと、
やはり「右左右右右右右右」もカウントしなければならなくなると思いますが、
いかがでしょうか…

１年ピカチュウ組　　 1月22日（木） 0:38:20　　 HomePage:算数の限界ってどのくらい？　　20354

吉川　マサル

#20354
　はい、「右左右右右右右右」も１通りとしてカウントするというのが題意です。答えのほうはもう一度検証してみます...。m(__)m

MacOS X　　 1月22日（木） 0:41:26　　 MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ　　20355

もありす５５

今回ばっかりはミスがひどすぎますね(^^;
以内とちょうどじゃ違いすぎでしょ。

　　 1月22日（木） 0:47:47　　　　20356

吉川　マサル

ゴメンナサイ、私のミスの内容が分かりました。

　なんと「８秒以内に一度もＡ地点を通らない場合」を計算していることに気付かず、２５６から引くのを忘れていました....。

MacOS X　　 1月22日（木） 0:47:50　　 MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ　　20357

辻。

最初「８秒以内にぴったり戻る」と解釈し18通り
でも掲示板に入れないので他の回答を考える
次に「１回戻ってもまた歩き出して８秒後にＡに戻ってくる」と
考えますが、これだと8Ｃ4＝70　で簡単すぎるのでは？
と思い認証したら入れました(^^)

やや風邪気味　　 1月22日（木） 0:50:25　　 HomePage:辻部屋。　　20358

まるケン

８秒後にＡに戻る歩き方と、８秒間一度もＡに戻らない歩き方とが同じ数になるんですね。これはこれで、ちょっとした発見。
ちなみに、１０秒後にＡに戻る歩き方も１０秒間一度もＡに戻らない歩き方は、やっぱりどちらも２５２通りで一緒になります。
ふしぎだぁ、、、

　　 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 を利用すると、たとえば数え上げは難しそうな数ということで、

「１６秒後に一度もＡに戻らない歩き方は何通り？」

なんて問題にすると、一見なかなか難しそうでＧＯＯＤですね。

　　 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

吉川　マサル

今回のミスに関する処置についてご報告します。

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

　ということで、訂正前の答えとして（ただし、それを見る時間のことも考えて）は、午前１時までの答案としては、「１８通り」および「１８６通り」の２通りを正解扱いといたします。

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

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

　今回の件で気を悪くされた、あるいは迷惑を被った多くの方々に深くお詫び申し上げます。すみませんでした。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

出題ミスでしたか。偶然にも正解が一致したのと思ってました(大汗)

はじめ２秒右に行った際に残り６秒で出発点に戻らない場合をカタラン数を
求めるようなマス目を書いて調べ、それを２倍し２５６から引きました。
http://homepage1.nifty.com/t/387.png　のような図です。

○saka　　 1月22日（木） 1:37:33　　 MAIL:tarox@nifty.com HomePage:もうひとつの理科チャレ２　　20366

Taro

#20360
げ！同様の図が先に描かれてました(^^;

○saka　　 1月22日（木） 1:40:42　　 MAIL:tarox@nifty.com HomePage:もうひとつの理科チャレ２　　20367

吉川　マサル

とりあえず、AM 1:00以前のメイルについて、１８および１８６を正解として順位表を作成しなおしました。

#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

トトロ＠Ｎ

用事で遅くなりましたが、それが良かったようです。
２秒後、４秒後、６秒後、８秒後に初めてＡに戻る場合に分けて考えました。

兵庫県明石市　　 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

かんクン

訂正後の問題文を見て、１７６通りでここに入れず悩んでいました。
「途中で１度以上」とあるので、８秒後に初めてＡ地点に戻ってくる場合
は数えないのが普通なのでは？　でも「訂正とお詫び」を見て、ひょっと
したらと思ったら、ここに来れました。

　　 1月22日（木） 3:30:43　　　　20376

とまぴょん

訂正後の問題をみて納得です。
酔ってるので、一度A地点に戻ってきても、そこで立ち止まることなくふらふらして通過するやろうなあと考えていましたので・・・

＞「７０通り」につきましては、「８秒ぴったりで帰ってくる場合」と、私のミスした「８秒以内で１度もＡに戻らない場合」が偶然（ではなくて実は必然なのですが）

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

　　 1月22日（木） 5:12:31　　 MAIL:y-tomari@zd5.so-net.ne.jp 　　20377

UnderBird

座標で、原点スタート、右を右1、左を上1に移動と考えると、８回目の場所は、（０，８）（１，７）（２，６）（３，５）（４，４）（５，３）（６，２）（７，１）（８，０）で（１，１）（２，２）（３，３）（４，４）を通らないで各格子点上へ行くまでの回数を対称性も含めて数えました。

　　 1月22日（木） 8:07:19　　 MAIL:shimotorikouichi@hotmail.com 　　20378

あ～く＠旧Ｎ

xy平面上で格子点を置き、x軸、y=x、y=-x+8で囲まれた内部の点を考える。
このとき、原点から出発しy=-x+8に到着する場合の数を調べればよい。
（x軸上に戻っては行けない）
すると、その場合の数は7+14+14=35となるので、求める場合の数は
2~8 -35*2 =186

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

こういう問題は格子点問題に置き換えると分かりやすいですね（と思うのは私だけ？）

　　 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 様が描かれている図と同じやり方です。２５６通りから、一度も原点を通過しない場合を引き算するという余事象の考えですね。

都内某所　　 1月22日（木） 9:57:28　　　　20382

小西孝一

おはようございます。
２秒後で初めてが２×２^6＝１２８、
４秒後で初めてが２×２^4＝３２、
６秒後で初めてが４×２^2＝１６
８秒後で初めてが両端４こが２通り×真ん中４こが５通り＝１０
と超地道にやりました。

ど田舎　　 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

ほげ

なかったですか　…　５分以前に掲示板に入ろうとして入れず
そういえば問題UP後　５分たたないと　掲示板がひらかないんだなあ
開くまでの間に答を送っとこう　と　送付した記憶があるのですが…

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

HNを使い分けてるわけではないのですが　本名とごっちゃになっている
今日この頃です。（*^_^*）

北の隠れ家　　 1月22日（木） 16:12:46　　 MAIL:micci@sansu.org HomePage:みっちの隠れ家　　20386

寝不足文君

こんばんわ、８回ぐらい入れてやっと正解しました。やっぱ小学５年じゃきついです。この問題とくのに、だいぶ時間たちました。でも１００位以内には入れてよかったです。最初ときかた分からなくて、なんとなく計算したので入力しましたが、最後は２５６通りからおかしいのをすべて出してそれを引きました。
もっと簡単な方法見つけられればなぁと思っています。

　　 1月22日（木） 19:46:25　　 MAIL:eido@kyoto.email.ne.jp 　　20387

とまぴょん

題意を2n秒後の場合に拡張してみました。カタラン数を考えながら、combination とシグマと２のべき乗で下記のようになりました。
∑〔(2rCr / r+1) x 2^{2(n-r)-1} 〕 (ただし　r = 0 to n-1 ) 　

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

＃20364のはなしでは、上式と2^(2n)－2nCn は等しいということになりますね。　不思議ですねえ・・

　　 1月22日（木） 20:21:41　　 MAIL:y-tomari@zd5.so-net.ne.jp 　　20388

いちたすには

「かんクン」さんに同感です
「途中」なんだから２、４、６秒後だろうって思いました

　　 1月22日（木） 21:04:58　　　　20389

えーーーだいぶおくれますタ

　　 1月22日（木） 21:30:56　　　　20390

>M.Hossieさん
やはりセンターの処理能力は地道に演習するしかないんですね。
地道に磨いていきます。ありがとうございました

昨日考えて頭がごちゃごちゃして解けなかった。返答する前に問題ＵＰされました。

　　 1月22日（木） 21:37:25　　　　20391

zizi

プログラムで解きました。
右と左を二進数であらわして00000000から11111111までの２５６通りを
0だったら-1、1だったら1と左から交互に足して途中で0になったら当たり。
算数で解きたいです。

　　 1月22日（木） 21:52:53　　　　20392

なか

出遅れました。

２＾８－８Ｃ４＝１８６、
パスカルの三角形の８段目の「中央の７０」を除く和ともいえる。
ちゃんと一般項も　２＾ｎ－２ｎＣｎ。

うーむ、裏返しだ。
８秒後に原点にいる場合の数と、
一度も原点にこない場合の数が等しいということですが、なんでだろう。

北海道　　 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:もうひとつの理科チャレ２　　20395

吉川　マサル

#20389、#20376
　仰る通り、曖昧な表現でした。訂正させていただきます。重ね重ねの失態、申し訳ありません...。m(__)m

MacOS X　　 1月23日（金） 1:03:09　　 MAIL:masaru-y@kt.rim.or.jp HomePage:算チャレ　　20396

小学名探偵

２ｎ歩目に元の位置にいる場合の数２ｎＣｎと、
２ｎ歩までに一度も元の位置を通らない場合の数が等しいのは何故？

よく分かってないのですが、+側の半分だけ考えて、例えば、８歩のときは、
ほげさんにしたがって
1，6，14，14になり、これを記号でa1, a2, a3, a4とします。最後のa4＝１４は
カタラン数です。
２ｎ歩目のとき、a1, a2,...anまであり、その合計S(n)が２ｎＣｎ／２に等しいとします。
２ｎ歩目のときの合計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(ｎ+1)Ｃ(ｎ+1）
ということで帰納的に求められます。
もっと分かりやすいのがありませんか。

　　 1月23日（金） 19:45:11　　　　20397

小学名探偵

８行目は”２（ｎ+1）歩目”に読み替えてください

　　 1月23日（金） 19:48:13　　　　20398

ｎ

カタラン数？(゜⊿゜)シラネ。でも問題は面白かた

　　 1月23日（金） 20:49:06　　　　20399

ちこりん

＞無名子さん
上下にどうやって移動するのかは聞かないほうがいいですか？

　　 1月24日（土） 21:18:32　　　　20401

小学名探偵

８歩目に元の位置に戻る経路の数と、それまでに
一度も元の位置を経ることがない経路の数が等しいということですが、
なぜでしょう？

やっぱり、算チャレ第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，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,0)を通ります。
第１経路はそこから(8,0)へ行きます。
第２経路は、(4,1)を経由して(7,1)へ行きます。
第３経路は、(4,2)を経由して(6,2)へ行きます。
第４経路は、(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月25日（日） 20:53:42　　　　20406

遠い山のぽきょぽん

今回は間違った答えでここに入ったときに正しい答えの数値を見てしまったので
順位表には不参加とします。
解法は２＾８からカタラン数みたいなのを引きました。

入った後に再考するのを今回に限って怠ってしまったのが残念です。

遠い山から　　 1月25日（日） 22:37:23　　　　20407

小学名探偵

数楽者さんへ
＞第１経路はそこから(8,0)へ行きます。
これについては、（4，0）の位置で乗り換えます（変換します）。
＞第２経路は、(4,1)を経由して(7,1)へ行きます。
2つのゴール（4，4）と（７，1）を結ぶ線分の垂直二等分線は（3，0）を通ります。
ここで乗り換えます。
＞第３経路は、(4,2)を経由して(6,2)へ行きます。
2つのゴール（4，4）と（７，1）の垂直二等分線は（2，0）を通ります。
ここで乗り換えます。
＞第４経路は、(4,3)を経由して(5,3)へ行きます。
2つのゴール（4，4）と（７，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

小学名探偵

訂正　
数楽者さんへ
＞第１経路はそこから(8,0)へ行きます。
これについては、（4，0）の位置で乗り換えます（変換します）。
＞第２経路は、(4,1)を経由して(7,1)へ行きます。
2つのゴール（4，4）と（７，1）を結ぶ線分の垂直二等分線は（3，0）を通ります。
ここで乗り換えます。
＞第３経路は、(4,2)を経由して(6,2)へ行きます。
2つのゴール（4，4）と（6，2）の垂直二等分線は（2，0）を通ります。
ここで乗り換えます。
＞第４経路は、(4,3)を経由して(5,3)へ行きます。
2つのゴール（4，4）と（5，3）の垂直二等分線は（1，0）を通ります。
ここで乗り換えます。

　　 1月26日（月） 0:32:33　　　　20409

小学名探偵

もう少し整理してみます。
その前に、８歩目に元に位置に戻るようなランダムウォークを
帰巣型と呼び、８歩目（一般的には２ｎ歩目）までに
一度も元の位置を経ないランダムウォークを
家出型と呼ぶことにします。
また、最初の一歩が”→”に進むランダムウォークを前向きと
呼び、最初の一歩が”←”に進むランダムウォークを後ろ向きと
呼ぶことにします。そして、
家出型のゴール（例えば、（8，0）、（6，2）の地点）と
帰巣型のゴール（4，4）を結ぶ線分の垂直二等分線を
対称軸と呼ぶことにします。

経路の乗り換え（交換）の条件、方法は、
１）前向き家出型の経路は前向き帰巣型経路に対応させ、
後ろ向き家出型の経路は後ろ向き帰巣型経路に対応させます。
２）前向き家出型の経路が（ｘ、0）の位置で、つまりｘ軸上の位置で、
対称軸と「交差」するときは、
その交差点で乗り換えます。すなわち、
交差点から前向き家出型の経路のゴールまでのパスを
対称軸について対称なパスに交換します。これにより、
前向き帰巣型経路の１つに変換されます。
後ろ向きについては、家出型の経路が（0、ｙ）の位置で対称軸と
交差するときは、その交差点で乗り換えます。
３）前向き家出型の経路が（ｘ、0）の位置（ｘ軸上）で対称軸と
交差しないときはどうするか、これが課題です。
この前向き家出型の経路が（ｘ、ｙ）の位置（ｙは0でない）で対称軸と
交差するとき、その交差点から乗り換えを行います。
ただし、この乗り換えだけだと不十分で
（つまり、１対１対応にならないので）、この交差点に着く
前のパスについても「なんらかの適当な交換」を行うようにします。
これが課題です。このようなケースでは、「最初」のパス交換位置は
やはりｘ軸上で行わなくてならないはずです（前向きの場合）。
もちろん、このパス交換は
対称軸について対称にはなりません。
いま、分かっているのはこの程度で、あとは皆様にお願いします。

　　 1月26日（月） 15:43:29　　　　20410

linearsupertrain

全体（2の８乗）から途中や最後に一度も原点を経ない歩き方（n通り）を引く方法でけっこう楽に解けました。nの求め方は以下の通りです：
nに含まれる全ての歩き方は、必ず反対側への１通りの対称な行き方があります。（例：→→→→→→←←と←←←←←←→→）なので一方通行で計算したn'の２倍がnになります。n'を求めるには、歩き始めるからの連続の歩数で場合わけするとよいでしょう。

　　 1月26日（月） 19:43:33　　 MAIL:secret 　　20411

小学名探偵

　　 1月27日（火） 20:58:23　　　　20412

小学名探偵

＃２０４１０の続きです。
一応、解けたようです。

家出型経路と帰巣型経路間のパス交換に関する
基本的性質やルールは次の通りです。
（１）ある前向きの帰巣型経路K(i)を前向きの家出型経路I(i)に変換する場合：
この場合、原点から帰巣型経路K(i)のゴールに向かって
辿っていって、順次、経路I(i)の各部を決めていくのがよいようです。
（１_0）最初の一歩は同じです。（0，0）から（1，0）へ
（１_1）経路K(i)があるノード（x,y）で↓ターンするとき、すなわち、
（x-1, y）、（x, y）、（x, y+1）を通るとき、
経路K(i)のノード（x,y）に対応する経路I(i)のノードを
（ｓ, ｔ）とすると、経路I(i)はそこから（ｓ+1, ｔ）に進ませます。
ｓ＞＝ｘ、ｔ＜＝ｙ
（１_2）経路K(i)があるノード（x,y）で→ターンするとき、すなわち、
（x, y-1）、（x, y）、（x, y+1）を通るとき、
経路I(i)は（ｓ, ｔ）から（ｓ+1, ｔ）に進ませます。
（１_3）経路K(i)と経路I(i)が再び（ｘ,y）で出会ったならば、
経路K(i)がそこで↓ターンすればルール（１_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）
の家出型の経路に変換されます。

（２）ある前向きの家出型経路I(i)を前向きの帰巣型経路K(i)に変換する場合：
この場合、家出型経路I(i)のゴールから原点に向かってさかのぼっていって、
順次、経路K(i)の各部を決めていくのがよいようです。
このさかのぼる方向において：
(２_0）最初の一歩は反対です。
（２_1）経路I(i)があるノード（s, t）で↑ターンするとき、すなわち、
（s+1, t）、（s, t）、（s, t-1）を通るとき、
経路Ｉ(i)のノード（s, t）に対応する経路K(i)のノードを
（x, y）とすると、経路K(i)はそこから（x-1, y）に進ませます。
（さかのぼっているので実際には戻らせているのですが)
ｓ＞＝ｘ、ｔ＜＝ｙ
（２_2）経路Ｉ(i)があるノード（s, t）で←ターンするとき、すなわち、
（ｓ, ｔ+1）、（ｓ, ｔ）、（ｓ-1, ｔ）を通るとき、
経路Ｋ(i)は（ｘ, ｙ）から（ｘ, ｙ-1）に進ませます。
（２_3）経路I(i)と経路K(i)が（s, t）で出会ったならば、
経路I(i)がそこで↑ターンすればルール（２_1）を経路Ｋ(i)に適用します。
そこで↑ターンしなければ次に経路I(i)が↑ターンするところまで
経路Ｋ(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で述べた方法（ルール）で、ある帰巣型経路を家出型の経路に変換した場合、
または、この逆の変換をした場合、両経路について次の位置関係が保たれます。
任意のステップ（原点からｋ番目のステップ）において、
帰巣型経路の位置（ｘ, y）と家出型の経路の位置（s, t）との間には、
45度の位置関係があります。
（両者が同じ位置のときも45度の位置関係にあるとみなします）

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

したがって、異なる帰巣型経路は異なる家出型経路に変換され、
この逆も真です。
したがって、
（n, n)をゴールとする帰巣型経路の個数と、l+m=2nである
（l, m）をゴールとする家出型経路の個数は等しいです。

　　 1月27日（火） 23:42:57　　　　20414