この前、将棋のネット対戦した話で、
「角の動きはランダムウォークの理論に則って動かしてるからな」
とか言わけわからんこと言うてたら、ボコボコにされて鼻血止まらんようになった話書いたやん。
そのランダムウォークって言うのは
次の位置は確率的に無作為に決定される
ってことやねんけど、数学の質問とかでランダムウォークについての話があって
原点に点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)
って公式があるとか聞いてん。
それで、おえ～！？こんなんで求まるん？ってしばらく白目むいて半笑いで気絶しててんけど、なんとか色々考えてみてわかった。
まず、この問題を考えてくれ。
図のAからBへの最短距離の道のりの個数はなんぼか？
これは普通に考えれば色々複雑な計算せなあかんけど、結果から言うと図形的な対称性を考えれば簡単な式で表されて
(i+j)_C_j - (i+j)_C_(j-1)
通りやねん。
これは高校数学でも使えんこともない定理やから覚えてたら役立つと思うけど実際試験に使うのは説明が大変かもしれんな。
それでなんでこうなるか言うと、
(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までの最短距離の道のりの個数と等しいと言うことになる。
だからそれが何故等しいかを考えたらええわけや。
直線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)
通りになるねん。
ランダムウォークの最初に書いた公式はこれを応用させてるだけや。
[問題]
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まで進むんも道のりの個数は同じやからな。
図をひっくりかえして、最初の問題みたいな形にすると横には操作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
でも直線の傾きをかけたらええって言うのはおもろいな。
数学、物理
高校数学の公式や問題の解説
- 関連記事
-
テーマ:日記 - ジャンル:日記
|
