100個の席

独りの超電波プログラマのblog記事で見かけた数学の問題

面白かったので解いてみた

問題†

100個席がある飛行機に100人の客がいます。全ての席は指定席ですが、最初に乗った人が適当な席を選んで座ってしまいました。

2人目以降は自分の席が空いていれば自分の席に座りますが、埋まっていた場合、適当な席に座ります。

100人目の客が自分の席に座れる確率は何%でしょうか？

補足：1人目は1の席を含む100個の席からランダムに座る．

解法†

• ある人が自分の座席に座れるという事象と座れないという事象は背反であり，ここではn人目が座れない確率を考える．
• n人目が座れない確率をp(n)で表して，小さい方から考える．

n=1の場合†

#mimetex(p\(1\)=\frac{99}{100})

• 1人目はランダムに選ぶので，これでOK

n=2の場合†

#mimetex(p\(2\)=\frac{1}{100})

• 2人目は1人目が2人目の席に座った場合のみ座れない

n=3の場合†

#mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{99})

• 第1項が1人目が3人目の席に座る可能性
• 第2項が1人目が2人目の席に座り且つ2人目が3人目の席に座る可能性
• それぞれの和となる

  #mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{99}=\frac{1}{100}\(1+\frac{1}{99}\)=\frac{1}{100}\(\frac{99}{99}+\frac{1}{99}\)=\frac{1}{100}\cdot\frac{100}{99}=\frac{1}{99})

• 整理すると約分される

n=4の場合†

#mimetex(p\(4\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{99}+\frac{1}{100}\cdot\frac{1}{98}+\frac{1}{100}\cdot\frac{1}{99}\cdot\frac{1}{98})

• 第1項が1人目が4人目の席に座る可能性
• 第2項が1人目が2人目の席に座り且つ2人目が4人目の席に座る可能性
• 第3項が1人目が3人目の席に座り且つ3人目が4人目の席に座る可能性
• 第4項が1人目が2人目の席に座り且つ2人目が3人目の席に座り且つ3人目が4人目の席に座る可能性
• それぞれの和となる
• &mimetex(p\(3\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{99});&mimetex(=\frac{1}{99});より下記の様に式変形できる．

#mimetex(p\(4\)=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{99}+\frac{1}{100}\cdot\frac{1}{98}+\frac{1}{100}\cdot\frac{1}{99}\cdot\frac{1}{98}=\frac{1}{99}+\frac{1}{99}\cdot\frac{1}{98})

#mimetex(=\frac{1}{99}\(1+\frac{1}{98}\)=\frac{1}{99}\cdot\frac{99}{98}=\frac{1}{98})

一般化に向けて†

• ここで既に&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-1)で表せる
• 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})

一般化(証明)†

• ここまでで，p(n)を漸化式で表せた．
• 一般項を求めたいのだが，p(n)を一般項にするのは一筋縄ではいかない．
• だが，おそらく&mimetex(p\(n\)=\frac{1}{102-n});であると思われるので，帰納法で証明する．

命題†

• 下記漸化式は，n>1において一般項&mimetex(p\(n\)=\frac{1}{102-n});で表せる．

  #mimetex(p\(n\)=p\(n-1\)+p\(n-1\)\cdot\frac{1}{102-n})

証明†

• n=2のとき

  #mimetex(p\(2\)=\frac{1}{100})

  • 自明
• n=3のとき

  #mimetex(p\(3\)=p\(2\)+p\(2\)\cdot\frac{1}{102-3}=\frac{1}{100}+\frac{1}{100}\cdot\frac{1}{99}=\frac{1}{99}=\frac{1}{102-n})

  • n=3のとき成り立つ
• nが成り立つときのn+1のとき

  #mimetex(p\(n+1\)=p\(n\)+p\(n\)\cdot\frac{1}{102-\(n+1\)}=\frac{1}{102-n}+\frac{1}{102-n}\cdot\frac{1}{102-\(n+1\)}=\frac{1}{102-n}\(1+\frac{1}{102-n-1}\))

#mimetex(=\frac{1}{102-n}\(\frac{102-n-1}{102-n-1}+\frac{1}{102-n-1}\)=\frac{1}{102-n}\(\frac{102-n}{102-n-1}\)=\frac{1}{102-\(n+1\)})

• これはp(n)のnをn+1で置き換えたものであり，n+1でも成り立つことが証明された．
• よって，この問題，100人目が座れない確率は

  #mimetex(p\(100\)=\frac{1}{102-100}=\frac{1}{2})

• となり，座れる確率も&mimetex(\frac{1}{2});となる．

ジャンル:数学

最新の20件