第１問「メダルツアー」問題解答

「メダルツアー」問題の解法です。
問題文はこちら。
他の問題の解法は、第２問、第３問、第４問、第５問。

拾うメダルの個数の期待値を求める問題です。
w, h, m が大した大きさではないので、いろんな方法で解くことができます。

一つは、「和の期待値は期待値の和」のアプローチです。
この言葉の意味については、和の期待値は期待値の和 | 高校数学の美しい物語などを参照して下さい。
メダルの個数の和の期待値を求めるには、それぞれのメダルについて、そのメダルを拾う確率を求めて、和をとればよいのです。

自然数 i（1 ≦ i ≦ h）について、下から i 番目のメダルを考えましょう。
このメダルを拾う確率はいくらでしょうか。
下のような図を書いて考えましょう。

f:id:riverplus:20180319005019p:plain

スタート（A）からゴール（D）までの行き方は全部で ${}_{w+h} C _w$ 通りです。
このうち、A→B→C→D の順で通れば、i 番目のメダルを拾うことができます。
そのような行き方は、 ${}_{m+i-2} C _{m-1} \times {}_{w+h-m-i+1} C _{h-i}$ 通りです。
この 2 つの値の比が、i 番目のメダルを求める確率です。

i についてループを書けばOKです。
コード例は次の通りです。分母の部分は i には依存しないため、最後に割っています。

def bi(a, b):
    r = 1
    for i in range(b):
        r *= a-i
        r /= i+1
    return r

def f(w, h, m):
    answer = 0
    for i in range(1, h+1):
        answer += bi(m+i-2, m-1) * bi(w+h-m-i+1, h-i)
    return float(answer) / bi(w+h, w)

print f(10, 10, 3)

　
　
もうひとつ、別解を紹介します。

def f(w, h, m):
    return float(h) / (w+1)

print f(10, 10, 3)

・・実はこの問題、答えは h/(w+1) なんです。
O(1) です。
m の値に依存しません。
ビックリしますよね。

出題者もビックリしました。
この記事で証明を書こうとしたのですが、結局ギブアップしました。ごめんなさい。

追記

その後、まさにズバリな解法を教えてもらいました！ Vandermonde の恒等式という打ってつけがあるのですね！

第１問「メダルツアー」問題解答 - riverplus のブログ https://t.co/dggf3MaGdN
By using Vandermonde's identity : \sum_i {}_{m+i-2} C_{m-1} \times {}_{w+h-m-i+1} C_{h-i} = {}_{w+h_1} C_{h-1} which yields, divided by {}_{w+h} C_h, the surprizing formula \frac{h}{w+1}
Wow!
— TJ Takei (@karoyakani) 2018年3月19日