ランダム・アルバイト・クイズ - しがないプログラマの日記

結城さんのところでクイズ([結] 2005年10月 - 結城浩の日記)が出題されていたので解等を考えてみました。問題はリンク先を見てください。
この問題は「順番に来る人の中から1人を等確立で選ぶ」問題の一般化のようです。そして1人を選ぶ場合の答えは、

最初の人は待機してもらう
2人目は1/2の確立で待機してもらい、待機の場合は1人目は拒否とする
3人目は1/3の確立で待機してもらい、待機の場合は待機していた人は拒否とする
…
n人目は1/nの確立で待機とし、待機の場合は待機していた人は拒否とする

となります。このようにすると全ての人が1/nで選ばれることになります。
何故なら、n人目が $\frac{1}{n}$ で選ばれているのは自明。n-1人目は、 $\frac{1}{n-1}$ で選ばれるけれどn人目が待機となると拒否されるので結果、 $\frac{1}{n-1}\times\frac{n-1}{n} = \frac{1}{n}$ となります。n-2人目は同様にそれ以降の人が待機となると拒否されるので、 $\frac{1}{n-2}\times\frac{n-2}{n-1}\times\frac{n-1}{n} = \frac{1}{n}$ 。同様に1人目まで全て $\frac{1}{n}$ の確立になります。

さて、それを踏まえて上記の問題を考えると以下のような方法で良いようです。つまり「順番に来る人の中からS名を等確立で選ぶ」問題の解等は、

最初のS人は待機してもらう
S+1人目はS/(S+1)の確立で待機してもらい、待機を選択した場合は現在待機している人の中からランダムで一人を拒否する
S+2人目はS/(S+2)の確立で待機してもらい、待機を選択した場合は現在待機している人の中からランダムで一人を拒否する
…
n人目はS/nの確立で待機してもらい、待機を選択した場合は現在待機している人の中からランダムで一人を拒否する

とすることで、全ての人をS/nの確立で選ぶことができます。ただし、Sは1以上の整数、nはS以上の整数です。
証明は上記と同様ですが、n-1人目が $\frac{S}{n}$ となるのはまず自分が待機となる可能性が $\frac{S}{n-1}$ でその後の人によって拒否されない可能性は、n人目が選ばれてかつ拒否される1人に選ばれる可能性以外なので $1-\frac{S}{n}\times\frac{1}{S} = \frac{n-1}{n}$ 。よって $\frac{S}{n-1}\times\frac{n-1}{n} = \frac{S}{n}$ となる。あとは同様に全ての人の選ばれる確立は $\frac{S}{n}$ となります。