分からない問題はここに書いてね457

分からない問題はここ ..

179:１３２人目の素数さん
20/01/01 02:35:23 ws23IPni.net
>>152
の漸化式は問題文の文章そのまま立式してるだけ。
p s はsの部屋割りのとき最後の2人がバラける確率。
p [1,1] = 1 は定員1人の部屋2部屋なら必ずバラける。
p [m] =0 は定員m人の部屋一部屋なら必ず同室。
それ以外なら1人目をどの部屋に入れる確率も等しいのが仮定だから最後の2人が同室になる確率は
p(s)Σp(t)/部屋の数、ただしtはいずれか一部屋の定員を1だけ減らした部屋の組みを渡る。
この漸化式を満たすとき、示したのは
p [1,1,‥,1] = 1 (全ての部屋の定員が1なら必ずバラける)
p [2,1,‥,1] = 1/(部屋数) (漸化式から容易)
p [2,2] = 1/2 (漸化式から容易)
それ以外の場合は
p(s) <1-1/(部屋数)
最後のは帰納法。
いずれかの部屋に1人入れて(1,‥,1)になるのは{1,‥,1)か(2,1,‥,1)しかないのでこの場合は既に示せている。
いずれかの部屋に1人入れて[2,2]になるのは[3,2]か[2,2,1]。
これらの場合は
p [3,2]= 3/8 < 1-1/2
p [2,2,1] = 11/18 < 1 - 1/3
により成立。
いずれの部屋に1人入れても上記例外ケースが現れないなら帰納法の仮定により同室にならない確率は1-1/部屋数より小さい。
説明はザックリだけどルーチンワークで難しい議論は必要ない。

次ページ

続きを表示

1を表示