入試数学コンテスト第2回第6問解答解説

第6問 [確率]

第6問

nn を 22 以上の整数とする。

座席が nn 個ある飛行機に, nn 人の乗客が一列に並んで順番に乗ろうとしている。各乗客の座る席は決まっているが, 列の最初に並んでいた人が自分の席番号を忘れてしまった。そこで乗客たちは次の手順で座席に座ることにした。

  • 列の最初の人は, nn 個の席のうちひとつをランダムに選んで座る。
  • それ以外の乗客は, 自分の番が来たときに自分の席が空いていればそこに座り, そうでないときは空いている席のうちひとつをランダムに選んで座る。

ただし, 席をランダムに選ぶときは空いている席を等確率で選ぶとする。

(1) n=100n = 100 のとき, 列の最後に並んでいた人が自分の席に座る確率を求めよ。

(2) n=200n = 200 のとき, 列の 44 番目に並んでいた人が自分の席に座る確率を求めよ。

(3) kk を 2≤k≤n2 \leq k \leq n を満たす整数とするとき, 列の kk 番目に並んでいた人が自分の座席に座る確率を nn と kk で表せ。

状況設定が複雑な「場合の数・確率」分野の問題です.こういった問題に対しては,

  • 小さい数の場合で実験してみる
  • うまく確率を設定して漸化式を立てる

などの方法が有効です.

以下の解答では列の kk 番目に並んでいる人の席を「席 kk」と書くことにします.

(1)

まずは (1) です.求める確率は, nn 人の乗客がいるときに,nn 人目が席 nn に座る確率 pnp_n です.これを n=100n=100 のときに直接計算するのは難しそうなので,漸化式を立てることを考えましょう.

nn が小さい場合の結果を使いたいので,11 人目が座った後の状況を考えてみます.

  • 11 人目が席 11 に座るとき

このときは全員が正しい席に座れます.

  • 11 人目が席 ii(i>1i > 1)に座るとき

このときは,22 〜 i−1i-1 人目までが正しい席に座り,ii 人目が残った席 1,i+1,i+2,…,n1, i+1, i+2, \dots, n の中からランダムに座ることになります.これは,ii 人目を改めて先頭として座っていく状況だと思うことができます.

実際にはもう少し細かい処理が必要ですが,この考え方で pnp_n の漸化式を作ることができそうです.

第6問(1)

nn 人の乗客がいるときに,nn 人目が正しい席に座る確率 pnp_n とおく.考えている事象を以下のように排反に場合分けする.

  • 11 人目が席 11 に座るとき

このときは全員が正しい席に座れるから,nn 人目が正しい席に座る確率は 1n⋅1\frac{1}{n} \cdot 1 である.

  • 11 人目が席 ii(1<i<n1 < i < n)に座るとき

このときは,22 〜 i−1i-1 人目までが正しい席に座り,ii 人目が残った席 1,i+1,i+2,…,n1, i+1, i+2, \dots, n の中からランダムに座ることになる.これは,(席 ii が席 11 に置き換わっているという点を除けば)ii 人目から nn 人目までの n−i+1n-i+1 人で問題文のやり方で飛行機に乗る状況と同じである.しかも,nn 人目の人から見ると,席 ii が席 11 に置き換わっていることは「自分の席に座れる確率」を計算する上で影響がない.(∵\because i≠ni \neq n なので.)

よってこの場合, nn 人目が正しい席に座る確率は 1n⋅pn−i+1\frac{1}{n} \cdot p_{n - i + 1} である.

  • 11 人目が席 nn に座るとき

この場合,nn 人目が正しい席に座る確率は 1n⋅0\frac{1}{n} \cdot 0 である.

以上を合わせると,pnp_n は

pn=1n+∑i=2n−11n⋅pn−i+1(n≥2) p_n = \frac{1}{n} + \sum_{i = 2}^{n-1} \frac{1}{n} \cdot p_{n-i+1} \hspace{10pt}(n \geq 2)

を満たす.漸化式の ∑\sum において j=n−i+1j = n-i+1 とおいて分母を払うと,

npn=1+∑j=2n−1pj(n≥2)n p_n = 1 + \sum_{j=2}^{n-1}p_j\hspace{10pt}(n \geq 2)

となる.nn を n+1n + 1 で置き換えると

(n+1)pn+1=1+∑j=2npj(n+1≥2)(n+1) p_{n+1} = 1 + \sum_{j=2}^{n}p_j\hspace{10pt}(n + 1 \geq 2)

となるから,これらの式を引き算すると

(n+1)pn+1−npn=pn(n≥2)(n+1) p_{n+1} - n p_n = p_n \hspace{10pt}(n \geq 2)

となり,結局

pn+1=pn(n≥2)p_{n+1} = p_n \hspace{10pt}(n \geq 2)

となる.これと

p2=12 p_2 = \frac{1}{2}

より n≥2n \geq 2 に対し pn=12p_n = \frac{1}{2} だから,特に p100=12p_{100} = \frac{1}{2} である.

nn がいくらであっても確率が 12\frac{1}{2} になるのは面白いですね!

(2)

次に (2) です.(1) と違い,44 人目が自分の席に座れるかどうかは 33 人目までが座った時点でわかります.この程度であれば思い切って直接計算してみるというのも有効です.見逃しや重複がないように慎重に場合分けして計算しきる力が必要となります.

44 番目の人が自分の席に座れない確率を qq を計算しましょう.ここでは2通りの計算方法を紹介します.

第6問(2) 解法(A)

44 人目が自分の席に座れない確率を qq として,これを計算する.あり得る場合を 11 人目が座る席で場合分けして考える.

  • 11 人目が席 11 or 55 〜 200200 に座るとき

この場合 22,33,44 人目は自分の席に座れる.

  • 11 人目が席 22 に座るとき

22 人目が席 11 or 55 〜 200200 に座ると 33,44 人目は自分の席に座れる.

22 人目が席 33 に座るとき,33 人目は席 1,4,5,…2001, 4, 5, \dots 200 の中から選ぶ.よって 44 人目が自分の席に座れない確率は 1200⋅1199⋅1198\frac{1}{200} \cdot \frac{1}{199} \cdot \frac{1}{198} となる.

22 人目が席 44 に座るとき, 44 人目は自分の席に座れない.この確率は 1200⋅1199\frac{1}{200} \cdot \frac{1}{199} である.

  • 11 人目が席 33 に座るとき

22 人目は自分の席に座れる.33 人目は席 1,4,5,…2001, 4, 5, \dots 200 の中から選ぶ.よって 44 人目が自分の席に座れない確率は 1200⋅1198\frac{1}{200} \cdot \frac{1}{198} となる.

  • 11 人目が席 44 に座るとき

44 人目は自分の席に座れない.この確率は 1200\frac{1}{200} である.

以上を全て足し合わせると,

q=1200⋅1199⋅1198+1200⋅1199+1200⋅1198+1200=1200(1199⋅1198+1199+1198+1)=1200(1199+1)(1198+1)=1200⋅200199⋅199198=1198 \begin{aligned} q &= \frac{1}{200} \cdot \frac{1}{199} \cdot \frac{1}{198} + \frac{1}{200} \cdot \frac{1}{199} + \frac{1}{200} \cdot \frac{1}{198} + \frac{1}{200} \\ &= \frac{1}{200} \left(\frac{1}{199} \cdot \frac{1}{198} + \frac{1}{199} + \frac{1}{198} + 1\right) \\ &= \frac{1}{200}\left(\frac{1}{199} + 1\right)\left(\frac{1}{198} + 1\right) \\ &= \frac{1}{200} \cdot \frac{200}{199} \cdot \frac{199}{198} \\ &= \frac{1}{198} \end{aligned}

だから,求める値は 1−q=1971981 - q = \frac{197}{198} である.

第6問(2) 解法(B)

44 人目が自分の席に座れない確率を qq として,これを計算する.あり得る場合を席 44 に誰が座るかで場合分けして考える.

  • 11 人目が座る場合

この確率は 1200\frac{1}{200} である.

  • 22 人目が座る場合

この確率は,11 人目が席 22 を選んで 22 人目が席 44 を選ぶ確率だから,1200⋅1199\frac{1}{200} \cdot \frac{1}{199} である.

  • 33 人目が座る場合

この確率は,「11 人目が席 33 に座る」or「11 人目が席 22 に座り,22 人目が席 33 に座る」のどちらかが起こった上で 33 人目が席 44 を選ぶ確率だから,(1200+1200⋅1199)⋅1198\left(\frac{1}{200} + \frac{1}{200} \cdot \frac{1}{199} \right) \cdot \frac{1}{198} である.

以上を足し合わせて, q=1200+1200⋅1199+(1200+1200⋅1199)⋅1198=1198 \begin{aligned} q &= \frac{1}{200} + \frac{1}{200} \cdot \frac{1}{199} + \left(\frac{1}{200} + \frac{1}{200} \cdot \frac{1}{199} \right) \cdot \frac{1}{198}\\ &=\frac{1}{198} \end{aligned} となる.

よって求める値は 1−q=1971981 - q = \frac{197}{198} である.

(3)

最後の問題です.(1),(2) のやり方をヒントに考えていきましょう.nn も kk も定まっていないので,何かしらの漸化式を考えることになります.ここでは (2) の解法 (B) の考え方を使って,kk についての漸化式を立ててみましょう.

第6問 (3)

2≤k≤n2 \leq k \leq n とし,kk 人目が席 kk に座れない確率を qkq_k とする.この事象を席 kk に誰が座るかで場合分けして考える.

席 kk に jj 人目(1≤j≤k−11 \leq j \leq k-1)が座るとする.

  • j=1j = 1 のとき

11 番目の人は nn 個の座席から等確率でひとつを選ぶから,そのときに席 kk が選ばれる確率は 1n\frac{1}{n} である.

  • j>1j > 1 のとき

jj 人目が席 kk に座る確率は,席 jj が空いておらず,かつ残った n−(j−1)n - (j - 1) 個の席の中から席 kk が選ばれる確率である.

まず,jj 人目の番で席 jj が空いていない確率は qjq_j である.すると残った n−(j−1)n - (j - 1) 個の席の中に席 kk があるかどうかが問題となるが,実は後で示すように,jj 人目の番で席 jj が空いていないとき,残った n−(j−1)n - (j - 1) 個の席は席 1,j+1,j+2,…,n1, j+1, j+2, \dots, n である.(すると j<kj < k だから席 kk は残っている.)

よって jj 人目が席 kk に座る確率は

qj⋅1n−(j−1) q_j \cdot \frac{1}{n - (j - 1)} である.

以上より,2≤k≤n2 \leq k \leq n のとき

qk=1n+∑j=2k−1qj⋅1n−j+1 q_k = \frac{1}{n} + \sum_{j = 2}^{k - 1} q_j \cdot \frac{1}{n - j + 1}

が成り立つ.右辺の ∑\sum を 2≤j<k−12 \leq j < k - 1 と j=k−1j = k - 1 に分解することで,k>2k > 2 のとき

qk=1n+∑j=2k−2qj⋅1n−j+1+qk−1⋅1n−k+2=qk−1+qk−1⋅1n−k+2=qk−1⋅n−k+3n−k+2 \begin{aligned} q_k &= \frac{1}{n} + \sum_{j = 2}^{k - 2} q_j \cdot \frac{1}{n - j + 1} + q_{k - 1} \cdot \frac{1}{n - k + 2} \\ &= q_{k - 1} + q_{k - 1} \cdot \frac{1}{n - k + 2} \\ &= q_{k - 1} \cdot \frac{n - k + 3}{n - k + 2} \end{aligned} となる.q2=1nq_2 = \frac{1}{n} と合わせると

qk=1n−k+2 q_k = \frac{1}{n - k + 2}

と計算できるから,求める確率は 1−qk=n−k+1n−k+21 - q_k = \frac{n - k + 1}{n - k + 2} である.

解答で使った事実の証明

jj 人目の番で席 jj が埋まっているとき,空いている席が席 1,j+1,j+2,…,n1, j+1, j+2, \dots, n であることを示す.

席 jj が空いていないとすると,そこまでの「自分の席に座らなかった人の列」 1→l1→⋯→lr→j 1 \to l_1 \to \cdots \to l_r \to j を考えることができる.( 11 人目が席 l1l_1 に座り,l1l_1 人目が席 l2l_2 に座り,…\dots ,lrl_r 人目が席 jj に座るという意味.)

まず 22 から l1−1l_1 - 1 人目までは自分の席に座れるから,l2l_2 は l1<l2l_1 < l_2を満たす中から選ばれる.(空いている席は席 1,l1+1,l1+2,…,n1, l_1+1, l_1 + 2, \dots, n で,席 11 を選ぶとそこで「自分の席に座らなかった人の列」が終わってしまうから不適.)

すると l1+1l_1 + 1 から l2−1l_2 - 1 人目も自分の席に座れる.この議論を繰り返すと,1<l1<⋯<lr<j1 < l_1 < \cdots < l_r < j で,しかも 11 から j−1j - 1 人目までが座ったとき,空いている席は席 1,j+1,j+2,…,n1, j+1, j+2, \dots, n だとわかる.

(3)は問題の色々な性質を駆使する必要がある難問です.うまく (1),(2) の解き方を応用できるかが鍵となる上,途中では使いたい性質を自分で証明する必要があります.入試本番であれば回避するべき問題かもしれませんが,このように自力でうまい漸化式を立てる問題もある,ということは頭に入れておきましょう.

ちなみに,興味がある人は (2) の解法 (A) のやり方を使って (3) を解く方法を考えてみると面白いかもしれません.