わんこら日記
甘くて切ない日記。わんこら式数学の勉強法、解説記事

階段状の道における最短距離の道のりの個数
この前、将棋のネット対戦した話で、

「角の動きはランダムウォークの理論に則って動かしてるからな」

とか言わけわからんこと言うてたら、ボコボコにされて鼻血止まらんようになった話書いたやん。


そのランダムウォークって言うのは

次の位置は確率的に無作為に決定される

ってことやねんけど、数学の質問とかでランダムウォークについての話があって


原点に点Pがあって、次の2つの操作を考える。

操作1,点Pをx軸正方向に1,y軸正方向に1移動
操作2,点Pをx軸正方向に1,y軸正方向に-1移動

この2つの操作を繰り返して点PがB(m,n)に移動する経路の個数は操作1がp回であったとすると

直線OBの傾き×m_C_p(=n/m・m_C_p)

って公式があるとか聞いてん。


それで、おえ~!?こんなんで求まるん?ってしばらく白目むいて半笑いで気絶しててんけど、なんとか色々考えてみてわかった。


まず、この問題を考えてくれ。

090421_m1.jpg

図のAからBへの最短距離の道のりの個数はなんぼか?

これは普通に考えれば色々複雑な計算せなあかんけど、結果から言うと図形的な対称性を考えれば簡単な式で表されて

(i+j)_C_j - (i+j)_C_(j-1)

通りやねん。


これは高校数学でも使えんこともない定理やから覚えてたら役立つと思うけど実際試験に使うのは説明が大変かもしれんな。

それでなんでこうなるか言うと、

090421_m2.jpg

(i+j)_C_j
って言うのは図のように欠けた部分を補った長方形の経路でAからBまでの最短距離の道のりの個数なわけや。
これはさすがにお決まりやな。

それで
(i+j)_C_(j-1)
って言うのは図のように長方形を少し延長して、Bから左に1,上に1の位置にある点B'とすると,AからB'までの最短距離の道のりの個数と言うことになるわけや。

それで、今求めるのは点Bを通る傾き1の直線をlとするとAからBへの道のりのうち直線lを越えないものを求めるわけやから、それが

(i+j)_C_j - (i+j)_C_(j-1)

ってことは(i+j)_C_(j-1)通り、つまりAからB'までの最短距離の道のりの個数が直線lを越えるAからBまでの最短距離の道のりの個数と等しいと言うことになる。


だからそれが何故等しいかを考えたらええわけや。

090421_m3.jpg

直線lを上に1平行移動した直線上にある点を左から
P_1,P_2,…,P_k,…,P_j
とすると、AからBまでの最短距離の道のりのうち直線lを越えるものは、これらP_1,P_2,…,P_k,…,P_jの点のうち最初に通るものがP_1,最初の通るものがP_2,…,最初に通るものがP_k,…,最初に通るものがP_j
のどれかに分類されるわけや。

これはあれやろ。
重複に数えてなくて、全部尽くされてるのがわかるやろ。

そんなん決めつけられても困るかもしれんけど。


それでP_1,P_2,…,P_jのうち最初に通るものがP_kの時、P_kからBまでの最短距離の道のりと、P_kからB'までの最短距離の道のりは対称性から同じ個数になってるのわかるかな。

ちょうどP_kからBまでの長方形と、P_kとB'までの長方形が点P_1,P_2,…,P_jを通る直線について対称になってるやろ。

だから同じ個数やねん。
と言うことは、AからBまでの最短距離の道のりのうち直線lを越えるものの個数は、

AからP_1,P_2,…,P_jのうち最初にP_kを通りB'に行く最短距離の道のりの個数をk=1~jまで全部足したのと同じなわけや。

でも
AからP_1,P_2,…,P_jのうち最初にP_kを通りB'に行く最短距離の道のりの個数をk=1~jまで全部足したものは、
AからB'に行くには必ず最初にP_1,P_2,…,P_jのうち最初にどれか通るし、どれも重複してないから、
ただ単にAからB'までの最短距離の道のりの個数のことになるやん。

つまり(i+j)_C_(j-1)通りやな。

これがAからBまでの最短距離の道のりのうち直線lを越えるものの個数なわけやから、直線lを越えないものは全体から引いて

(i+j)_C_j - (i+j)_C_(j-1)

通りになるねん。


ランダムウォークの最初に書いた公式はこれを応用させてるだけや。

090421_m4.jpg

[問題]

xy平面において原点に点Pがあり、次の操作を考える。

S:点Pをx方向に+1,y方向に+1移動
T:点Pをx方向に+1,y方向に-1移動

操作S,Tを繰り返して、点Pが(m,n)に移動する経路のうち、x軸上の点を通らないのは何通りあるか?


[解答と解説]
x方向にm回進まなあかんから操作はm回行われてるからSの回数kとすると、Tの回数はm-kでy方向にn進むには
k-(m-k)=n
より
k=(m+n)/2

kはちゃんと整数になるような問題設定になってると言うことで許してくれ。

それで経路を書いてみると、x軸上の点を通らないってことやから最初は必ずSで(1,1)に進んで経路をはちょうど階段みたいにになっててさっきやった問題に帰着されることがわかるねん。

点A(m,n),点B(1,1)とすると

点Aから点Bまでの道のりを考えたらええわけや。
BからAまで進むんもAからBまで進むんも道のりの個数は同じやからな。

090421_m5.jpg

図をひっくりかえして、最初の問題みたいな形にすると横には操作Tの回数、m-k回移動せなあかん。
それで縦にはSの回数から最初にSの操作を1回してるからk-1回移動せなあかんわけや。

だから図のAからBまでの道のりは縦と横全部でm-1個より

(m-1)_C_(m-k) - (m-1)_C_(m-k-1)

通り。

これで求まったな。


ただ一番最初に書いた公式では
直線OAの傾き=n/mで
n/m×m_C_k
ちゃうんか!ってど汚い濡れ雑巾でしばかれそうやけど、単にそこは式変型をするだけで

(m-1)_C_(m-k) - (m-1)_C_(m-k-1)
=(m-1)!/((m-k)!(k-1)!) - (m-1)!/((m-k-1)!k!)
=(m-1)!/((m-k-1)!(k-1)!)×(1/(m-k) - 1/k)
=(m-1)!/((m-k-1)!(k-1)!)×(2k-m)/(k(m-k))
=(m-1)!/((m-k)!k!)×(2k-m)

k=(m+n)/2やから2k-m=nで

=n(m-1)!/((m-k)!k!)
=n/m×m!/((m-k)!k!)
=n/m×m_C_k
=直線OAの傾き×m_C_k

でも直線の傾きをかけたらええって言うのはおもろいな。

数学、物理

高校数学の公式や問題の解説

テーマ:日記 - ジャンル:日記

▲ページトップへ
この記事に対するトラックバック
トラックバックURL
→http://wankora.blog31.fc2.com/tb.php/1776-86c4bd0c
この記事にトラックバックする(FC2ブログユーザー)
▲ページトップへ
プロフィール

わんこら

Author:わんこら
京都大学理学部を数学専攻で卒業した数学と物理講師

現在、東京で働いています。

かずスクール
で数学を教えてます。

わんこら式数学の勉強法
数学の勉強方法や仕方を説明

詳しいプロフィール


メッセージはこちらへ
メール
迷惑メールにされる危険性があるので出来るだけ
kazuyuki_ht○guitar.ocn.ne.jp
(○を@にしてください)に送ってください

勉強とかでどんな悩み持ってるかなど色々と教えてくれると嬉しいです。
わんこら式のやり方についてはわんこら式診断プログラムを参考にしてメールください
都合がつかず遅れたり返せなかったりする場合があるのは申し訳ないです

リンクはばりばりのフリー
一言メールくれれば相互リンクします。


カテゴリーと名作集
読者に受けが良かった記事を集めてたり、今までの記事をカテゴリー別にまとめてます。



水と空気と街並とからだ
中学時代からの親友てつろうのブログ。
今年、滋賀医科に合格した医学生です。

リンク集
リンク集はこっちです。

このブログは携帯でも見られます。

ランキングサイト


↓ランキング参加中




にほんブログ村 その他日記ブログ 日々のできごとへ

blog Ranking


お勉強BLOGЯanK

リンク

カテゴリー

メールフォーム

名前:
メールアドレス:
件名:
本文:

ブロとも申請フォーム

この人とブロともになる

FC2カウンター

月別アーカイブ

ブログ内検索

RSSフィード