100個の席
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[独りの超電波プログラマ>http://d.hatena.ne.jp/kudzu/]]の...
面白かったので解いてみた
#contents
*問題 [#v8eee50a]
100個席がある飛行機に100人の客がいます。全ての席は指定席...
2人目以降は自分の席が空いていれば自分の席に座りますが、...
100人目の客が自分の席に座れる確率は何%でしょうか?
補足:1人目は1の席を含む100個の席からランダムに座る.
*解法 [#ob2af8c6]
-ある人が自分の座席に座れるという事象と座れないという事象...
-n人目が座れない確率をp(n)で表して,小さい方から考える.
**n=1の場合 [#tbe7a9ae]
#mimetex(p\(1\)=\frac{99}{100})
-1人目はランダムに選ぶので,これでOK
**n=2の場合 [#s5582682]
#mimetex(p\(2\)=\frac{1}{100})
-2人目は1人目が2人目の席に座った場合のみ座れない
**n=3の場合 [#md9c2b37]
#mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
-第1項が1人目が3人目の席に座る可能性
-第2項が1人目が2人目の席に座り且つ2人目が3人目の席に座る...
-それぞれの和となる
#mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
-整理すると約分される
**n=4の場合 [#j8d86422]
#mimetex(p\(4\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
-第1項が1人目が4人目の席に座る可能性
-第2項が1人目が2人目の席に座り且つ2人目が4人目の席に座る...
-第3項が1人目が3人目の席に座り且つ3人目が4人目の席に座る...
-第4項が1人目が2人目の席に座り且つ2人目が3人目の席に座り...
-それぞれの和となる
-&mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}...
#mimetex(p\(4\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
#mimetex(=\frac{1}{99}\(1+\frac{1}{98}\)=\frac{1}{99}\cdo...
*一般化に向けて [#c10d3088]
-ここで既に&mimetex(p\(n\)=\frac{1}{102-n});の可能性がぷ...
-よくよく見ると,再帰的なパターンが隠れている
-「自分の席じゃないところに座る人」の列を,若い番号を左側...
n=1のとき
1
n=2のとき
1-2
n=3のとき
1-3
1-2-3
n=4のとき
1-4
1-2-4
1-3-4
1-2-3-4
-ってな具合になっている.
-よく見てみると
n=4のとき n=3のとき
1-4 <- 1-3 3が4に変わっただけ
1-2-4 <- 1-2-3 3が4に変わっただけ
1-3-4 <- 1-3 4が右(最後)に付いた
1-2-3-4 <- 1-2-3 4が右(最後)に付いた
-ってな具合に,1個前のパターンで再帰的に表現される場合分...
-つまりp(n)は
--n-2人目以前がn人目の席に座ってしまう可能性
--n-1人目がn人目の席に座ってしまう可能性
--の和で表せる.
-n-2人目以前がn人目の席に座る可能性
--これはn-1人目が自分の席に座れない可能性に等しいのでp(n-...
-n-1人目がn人目の席に座ってしまう可能性
--これはn-1人目が,自分の席に座れなかった時にn人目の席に...
--n-1人目が座る段階で,残りの席は 1/(100-(n-2))=1/(102-n)
--よって,p(n-1)/(102-n)で表せる.
-この2項の和なので,p(n)は下記漸化式で表せる.
#mimetex(p\(n\)=p\(n-1\)+p\(n-1\)\cdot\frac{1}{102-n})
*一般化(証明) [#pa7ab737]
-ここまでで,p(n)を漸化式で表せた.
-一般項を求めたいのだが,p(n)を一般項にするのは一筋縄では...
-だが,おそらく&mimetex(p\(n\)=\frac{1}{102-n});であると...
**命題 [#ab3b5e2b]
-下記漸化式は,n>1において一般項&mimetex(p\(n\)=\frac{1}{...
#mimetex(p\(n\)=p\(n-1\)+p\(n-1\)\cdot\frac{1}{102-n})
**証明 [#efa15664]
-n=2のとき
#mimetex(p\(2\)=\frac{1}{100})
--自明
-n=3のとき
#mimetex(p\(3\)=p\(2\)+p\(2\)\cdot\frac{1}{102-3}=\frac{1...
--n=3のとき成り立つ
-nが成り立つときのn+1のとき
#mimetex(p\(n+1\)=p\(n\)+p\(n\)\cdot\frac{1}{102-\(n+1\)}...
#mimetex(=\frac{1}{102-n}\(\frac{102-n-1}{102-n-1}+\frac{...
-これはp(n)のnをn+1で置き換えたものであり,n+1でも成り立...
-よって,この問題,100人目が座れない確率は
#mimetex(p\(100\)=\frac{1}{102-100}=\frac{1}{2})
-となり,座れる確率も&mimetex(\frac{1}{2});となる.
ジャンル[[:数学]]
終了行:
[[独りの超電波プログラマ>http://d.hatena.ne.jp/kudzu/]]の...
面白かったので解いてみた
#contents
*問題 [#v8eee50a]
100個席がある飛行機に100人の客がいます。全ての席は指定席...
2人目以降は自分の席が空いていれば自分の席に座りますが、...
100人目の客が自分の席に座れる確率は何%でしょうか?
補足:1人目は1の席を含む100個の席からランダムに座る.
*解法 [#ob2af8c6]
-ある人が自分の座席に座れるという事象と座れないという事象...
-n人目が座れない確率をp(n)で表して,小さい方から考える.
**n=1の場合 [#tbe7a9ae]
#mimetex(p\(1\)=\frac{99}{100})
-1人目はランダムに選ぶので,これでOK
**n=2の場合 [#s5582682]
#mimetex(p\(2\)=\frac{1}{100})
-2人目は1人目が2人目の席に座った場合のみ座れない
**n=3の場合 [#md9c2b37]
#mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
-第1項が1人目が3人目の席に座る可能性
-第2項が1人目が2人目の席に座り且つ2人目が3人目の席に座る...
-それぞれの和となる
#mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
-整理すると約分される
**n=4の場合 [#j8d86422]
#mimetex(p\(4\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
-第1項が1人目が4人目の席に座る可能性
-第2項が1人目が2人目の席に座り且つ2人目が4人目の席に座る...
-第3項が1人目が3人目の席に座り且つ3人目が4人目の席に座る...
-第4項が1人目が2人目の席に座り且つ2人目が3人目の席に座り...
-それぞれの和となる
-&mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}...
#mimetex(p\(4\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{...
#mimetex(=\frac{1}{99}\(1+\frac{1}{98}\)=\frac{1}{99}\cdo...
*一般化に向けて [#c10d3088]
-ここで既に&mimetex(p\(n\)=\frac{1}{102-n});の可能性がぷ...
-よくよく見ると,再帰的なパターンが隠れている
-「自分の席じゃないところに座る人」の列を,若い番号を左側...
n=1のとき
1
n=2のとき
1-2
n=3のとき
1-3
1-2-3
n=4のとき
1-4
1-2-4
1-3-4
1-2-3-4
-ってな具合になっている.
-よく見てみると
n=4のとき n=3のとき
1-4 <- 1-3 3が4に変わっただけ
1-2-4 <- 1-2-3 3が4に変わっただけ
1-3-4 <- 1-3 4が右(最後)に付いた
1-2-3-4 <- 1-2-3 4が右(最後)に付いた
-ってな具合に,1個前のパターンで再帰的に表現される場合分...
-つまりp(n)は
--n-2人目以前がn人目の席に座ってしまう可能性
--n-1人目がn人目の席に座ってしまう可能性
--の和で表せる.
-n-2人目以前がn人目の席に座る可能性
--これはn-1人目が自分の席に座れない可能性に等しいのでp(n-...
-n-1人目がn人目の席に座ってしまう可能性
--これはn-1人目が,自分の席に座れなかった時にn人目の席に...
--n-1人目が座る段階で,残りの席は 1/(100-(n-2))=1/(102-n)
--よって,p(n-1)/(102-n)で表せる.
-この2項の和なので,p(n)は下記漸化式で表せる.
#mimetex(p\(n\)=p\(n-1\)+p\(n-1\)\cdot\frac{1}{102-n})
*一般化(証明) [#pa7ab737]
-ここまでで,p(n)を漸化式で表せた.
-一般項を求めたいのだが,p(n)を一般項にするのは一筋縄では...
-だが,おそらく&mimetex(p\(n\)=\frac{1}{102-n});であると...
**命題 [#ab3b5e2b]
-下記漸化式は,n>1において一般項&mimetex(p\(n\)=\frac{1}{...
#mimetex(p\(n\)=p\(n-1\)+p\(n-1\)\cdot\frac{1}{102-n})
**証明 [#efa15664]
-n=2のとき
#mimetex(p\(2\)=\frac{1}{100})
--自明
-n=3のとき
#mimetex(p\(3\)=p\(2\)+p\(2\)\cdot\frac{1}{102-3}=\frac{1...
--n=3のとき成り立つ
-nが成り立つときのn+1のとき
#mimetex(p\(n+1\)=p\(n\)+p\(n\)\cdot\frac{1}{102-\(n+1\)}...
#mimetex(=\frac{1}{102-n}\(\frac{102-n-1}{102-n-1}+\frac{...
-これはp(n)のnをn+1で置き換えたものであり,n+1でも成り立...
-よって,この問題,100人目が座れない確率は
#mimetex(p\(100\)=\frac{1}{102-100}=\frac{1}{2})
-となり,座れる確率も&mimetex(\frac{1}{2});となる.
ジャンル[[:数学]]
ページ名: