100個人求職，公司要怎樣才能取到這100個人當中的最好的那個人的概率最大？

12-03

這其實是一概率題，曾經高三補課的時候數學老師說是大學高數的內容，但是我的大學並沒有學到這方面內容，想請教一下數學高手們這個題目的解答方法。
題目：
100個人求職，按編號面試，每個人面試完公司立刻決定要不要這個人，IF 要，後面的人全部淘汰。IF 不要則下一個面試者，公司不能回頭去選擇先前決定不要的人。

問題是：公司要怎樣才能取到這100個人當中的最好的那個人的概率最大
答案我記得是這樣的：取前30個（33個？35個？記不清了），挑這30個人里最好的，然後在剩下的70個裡依次按順序挑選，一旦發現有比那30個人當中最好的一個人好的人，就直接錄取。這樣能確保選到的人才在100個人當中是最好的的概率最大。

應該是拒掉前37個，在剩下里依次調，遇到比前37個都好的就錄取，不然就直到最後一個人。
再精確點就是總數的1/e個

這篇文章能幫到你
http://luo.bo/12357/

我來稍微嚴格地寫一下這個事情。現假設有前 $n$ 個正整數的一個隨機置換

${ x_1, cdots, x_n } = {1, cdots,n}$ ,

序列 $x_1, cdots, x_n$ 隨機性體現在所有 $x_k$ 的邊緣分布滿足

$P(x_k = j) = 1/n, qquad forall ,, 1 leq k,j leq n.$

進一步記

$M_k riangleq max_{i = 1, cdots, k} {x_i}$ ,

即 $M_k$ 表示前 $k$ 個數 $x_1, cdots, x_k$ 中的最大值。現令

$au_k = inf ,, { j|j > k, x_j > M_k }$ ,

換言之 $au_k$ 表示從第 $k+1$ 個數起，首次出現大於 $M_k$ 的數字的時刻。若不存在這樣的數(當且僅當 $n in {x_1, cdots, x_k}$ )，則補充定義 $au_k = infty$ 和 $x_{infty} = 0$ . 現在考慮事件

$W_k riangleq {x_{ au_k} = n}$ ,

亦即"第 $au_k$ 個數字是 $n$ "這個事件. 下面計算 $P(W_k)$ .

$egin{eqnarray} P(W_k) = sum_{j = k+1}^{n} P(x_j = n, M_{j-1} in {x_1, cdots, x_{k}}) \ = sum_{j = k+1}^{n} P(x_j = n) cdot P( M_{j-1} in {x_1, cdots, x_{k}}) \ = sum_{j = k+1}^{n} frac{1}{n} frac{k}{j-1} . end{eqnarray}$

當 $n$ 充分大時，上式近似為

$egin{eqnarray} P(W_k) = sum_{j = k+1}^{n} frac{1}{n} frac{k}{j-1} \ approx frac{k}{n}int_{k/n}^{1} frac{1}{x} dx \ = - frac{k}{n} logfrac{k}{n}. end{eqnarray}$

換元令 $x = frac{k}{n}$ , 當 $k in {1, cdots, n}$ 變化時相應的 $x in (0,1]$ . 於是

$max_{k in {1, cdots, n}} P(W_k) = max_{x in (0.1]} { - x log x }$ .

直接求導易得 $x_{opt}= 1/e$ , 即 $k_{opt} = n/e$ . 從而為了最大可能地選到 $n$ ，應該預先拒絕前 $1/e approx 36.8\%$ 的數字.

草草。

所謂炮灰理論

37法則。