swk's log - ランダムアルバイトクイズ

* ランダムアルバイトクイズ [misc]

• 問題編: http://www.hyuki.com/d/200510.html#i20051016205402
• 解答編: http://www.hyuki.com/d/200510.html#i20051019091930

というわけで送ってみた解答を晒してみる．

---

S 名採用の場合，まず最初の S 人は待機してもらいます．

さて，これまでに S+k-1 人 (k は 1 以上の整数) の応募者が訪れていたとします．もうこれ以上応募者は来ないかも知れないので，チャンスが公平であるためには，この時点で待機している S 人は，S/(S+k-1) の確率で生き残って来たことにならなければなりません．k = 1 のときは明らかにこれは満たされます．

いま S+k 人目が新たにやって来たときに，既に待機している S 人とこの新たな応募者を合わせた S+1 人から 1 人を選んで拒否します．このとき S+k 人目の応募者が拒否される確率を p として，既に待機している S 人のそれぞれが拒否される確率を (1-p)/S とします (合計 1 になります)．そうすると，S+k 人目が生き残る確率は 1-p で，既に待機している S 人のそれぞれがこの時点まで生き残る確率は S/(S+k-1) * {1 - (1-p)/S} になります．この両者が一致していないといけないので，

 1 - p = S/(S+k-1) * {1 - (1-p)/S}

を解いて p = k/(S+k) となります．この時点までで，すべての人は確率 S/(S+k) で採用されるチャンスを与えられたことになります．

よって答えは，

問題1: 可能である．問題2の答えで S = 5 とする．

問題2: 最初の S 人は待機してもらう．S+k 人目 (k は 1 以上の整数) が来たときに，既に待機している S 人とこの新たな応募者を合わせた S+1 人から 1 人を選んで拒否する．このとき選ばれる確率は，新たな応募者は k/(S+k) とし，既に待機している S 人のそれぞれは 1/(S+k) とする．

となります．

---

実はこの答えは，一度送った後に結城さんから曖昧さを指摘され，訂正したものです．最初の曖昧な答えはこうでした．

問題2: 最初の S 人は待機してもらう．S+k 人目 (k は 1 以上の整数) が来たときに，その人を確率 k/(S+k) で，既に待機している S 人のそれぞれを 1/(S+k) でランダムに選んで拒否する．

これだと，各時点で常に 1 人を選んで拒否するとは必ずしも読み取れないんですね．うーん，曖昧でない文章を書くのは難しい．