阿里的一道筆試題，如何建模？

01-21

20個人參加面試，每個人隨機抽取20道題，請問試題庫最少有多少道題？才能滿足20人中任意兩人相同的題目&<=3的概率&>=95%。
不知道如何抽象出模型。

是所有人重複還是兩兩重複不超過啊，不過也無所謂了，記住，古典概率問題都是計數問題，只要關心分子是多少、分母是多少。分母顯然是C(N, 20)^20。分子是符合條件的選法總數，按兩兩不超過3來算，一道題最多被兩人選，窮舉重複了的題目的數量，範圍從0到30，則不重複題目的數量是400-2k，合計400道題隨機分成20組，再用容斥原理扣掉一道題的兩次重複分給了同一個人的情況，最後求總和。

令 $N$ 為題庫容量， $A_i$ 為第 $i$ 位面試者抽到的題目的集合，其中 $i = 1, ldots, 20$ 。據題意，

$egin{align*} 1 - alpha le Pleft(cap_{i eq j} left{leftvert A_i cap A_j ightvert le 3 ight} ight) \ = Pleft(cap_{i < j} left{leftvert A_i cap A_j ightvert le 3 ight} ight) \ = 1 - Pleft(cup_{i < j} left{leftvert A_i cap A_j ightvertge 4 ight} ight) \ = 1 - sum_{i < j} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) + oleft(sum_{i < j} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) ight) end{align*}$

因此，我們考慮

$sum_{i < j} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) = alpha (= 0.05)$

即

$Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) = frac{2 alpha}{20 cdot 19}$

按定義直接求：

$egin{align*} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) = sum_{k = 4}^{20} Pleft(left{leftvert A_i cap A_j ightvert = k ight} ight) \ = sum_{k = 4}^{20} frac{inom{N}{20 - k quad k quad 20 - k quad N - 40 + k}}{inom{N}{20} inom{N}{20}} \ = sum_{k = 4}^{20} frac{20! 20! (N - 20)! (N - 20)!}{k! (20 - k)! (20 - k)! (N - 40 + k)! N!} \ = sum_{k = 4}^{20} k! left[inom{20}{k} ight]^2 frac{overbrace{(N - 20) cdots (N - 40 + k + 1)}^{20 - k}}{underbrace{N cdots (N - 20 + 1)}_{20}} \ = 4! left[inom{20}{4} ight]^2 frac{1}{N^4} + Oleft(frac{1}{N^5} ight) \ = frac{563376600}{N^4} + Oleft(frac{1}{N^5} ight) end{align*}$

按照這個近似，可以得到

$N_4 = 1210$ （即 @高天「二階近似」下的答案）

更高階的近似：

接下來考慮保留 $frac{1}{N^5}$ 階項，此時容易被忽略的一點是，這時候不光要對上式進行（泰勒）近似，還要檢查之前展開式中 $oleft(sum_{i < j} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) ight)$ （即交叉項）的貢獻：

$egin{align*} quad Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) \ = sum_{k = 4}^{20} k! left[inom{20}{k} ight]^2 frac{overbrace{(N - 20) cdots (N - 40 + k + 1)}^{20 - k}}{underbrace{N cdots (N - 20 + 1)}_{20}} \ = 4! left[inom{20}{4} ight]^2 left(1 + frac{1}{N} + cdots + frac{19}{N} - frac{20}{N} - cdots - frac{35}{N} ight) frac{1}{N^4} + 5! left[inom{20}{5} ight]^2 frac{1}{N^5} + Oleft(frac{1}{N^6} ight) \ = 4! left[inom{20}{4} ight]^2 frac{1}{N^4} + left{- 250 cdot 4! left[inom{20}{4} ight]^2 + 5! left[inom{20}{5} ight]^2 ight} frac{1}{N^5} + Oleft(frac{1}{N^6} ight) \ = frac{563376600}{N^4} - frac{111999268080}{N^5} + Oleft(frac{1}{N^6} ight) end{align*}$

$egin{align*} quad oleft(sum_{i < j} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) ight) \ = frac{1}{2} sum_{i < j, i$

因此不須多慮交叉項的貢獻。在新的近似下，可以得到

$N_5 = 1154$ （和 @符笛的二分法搜索的模擬結果1147已經很接近了）

由於 $oleft(sum_{i < j} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) ight)$ 的貢獻是 $frac{1}{N^8}$ 的量級，對 $Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight)$ 一直展開到 $frac{1}{N^7}$ 階近似都可以不予以考慮。事實上，當 $k > 5$ 時，與其做（泰勒）近似展開，倒不如用程序直接計算 $k! left[inom{20}{k} ight]^2 frac{overbrace{(N - 20) cdots (N - 40 + k + 1)}^{20 - k}}{underbrace{N cdots (N - 20 + 1)}_{20}}$ 的值（結果會有區別，但是誤差量級是相同的）。用該方法得到更高階的近似結果如下：

$egin{align*} N_4$

如果要計算 $N_8$ ，按照前述，必須考慮 $oleft(sum_{i < j} Pleft(left{leftvert A_i cap A_j ightvertge 4 ight} ight) ight)$ 的貢獻，計算結果為：

$N_8$ （幾乎等於 @符笛的二分法搜索的模擬結果1147）

與 $N_7$ 有一些差異，說明 $N$ 的大小還不足以忽略 $left{leftvert A_i cap A_j ightvertge 4 ight}$ 的交集們的貢獻。

---------------------------------------------------------------------------------------------------------------------------------

感謝 @子元幫我指出錯誤。

之前看的題目理解有問題，下面把數據稍作修改，方法完全沒有變，只是之前認為題目說的是相同題目&<=2的概率。

==========================================================================

這道題如果是阿里來出，你用古典概型去算準確值，不論你算得對不對，基本穩穩地掛了。

你要記住，你是一個工程師，不是一個數學家。工程師要去簡化問題，縮小模型，用最快的速度得出比較精確的答案。阿里出了一個這麼複雜的題不是考你概率論基礎呢，是看你對數據的概念和理解，哪些可以不要，哪些必須要。

因此我的解法是這樣的：

設題庫數量為N

先計算兩個人重複4道題的概率。如果一個人已經有了20道題，那另外一個人抽一道題和他重疊的概率是20/N。這個人抽20道題有至少4道和他重疊的概率大約是C(20, 4)*(20/N)^4。這裡我沒考慮抽到的題不會再出現，也沒考慮剩下16道題的情況，這些在「題庫遠大於20道」的情況下近似成立。

再考慮一共有20個人，兩兩一組有C(20, 2)=190種可能性。在「兩個人之間重複」這個事情發生概率很小的情況下，190種組合里出現至少一個的概率大約是190*一種組合出現的概率。

因此我們得到等式：190*C(20, 4)*(20/N)^4=5%，解出N大約是1310。

代入N=1310，進行模擬模擬，得到模擬值大約是3%，誤差40%，雖然是同一個數量級，但是差距還是比較大。所以我們回頭看一下，上面哪裡是我們捨棄的比較大的部分。

之前說，抽20道題至少有4道和他重疊的概率大約是C(20,4)*(20/N)^4，這裡沒有考慮到抽到的題不會再出現。而在需求重疊題目越多的時候，這個因素會變得越明顯。因此我們把這裡改成考慮要四道不同的題目，於是就變成了C(20,4)*(20/N)*(19/N)*(18/N)*(17/N)。

再把這個數據代回我們的等式，可以得到新的N=1209。把1209進行模擬模擬，發現模擬值被提升到了4%左右，誤差在20%，這個已經非常可以接受了。

工程師有時候就是一個這樣的反饋系統，在你忽略的內容太多的時候，就要重新撿起來一些，在這個過程中成長，然後在以後對系統進行分析的時候可以更精準。

居其位，謀其政。在你面試的時候一定要想清楚，面試官在考你什麼，你應該展示的是什麼。他要是問你中國移動有多少用戶，難道你去人家資料庫一個一個翻電話本么？

為什麼我算了幾次都是269呢，還不知道哪裡錯了

comp的結果就是269最接近0.95了

——————————————————————————————————————————————————————————————————————————————————————

感謝matrix幫我看了，我終於明白我哪裡錯了。我理解成了「任意兩人相同的題目&<=3的概率&>=95%」，其他所有人都理解為「20人里任意每兩人相同的題目都都都&<=3的概率&>=95%」。果然是我的語文沒學好嘛？按照這個意思改了一下，可是這樣子x就要好大好大才行，我讓x=100000,正好一天一夜(我好認wu真liao)，結果1146，估計是湊巧到這裡了，x不夠大，所以沒有收斂吧....

再次感謝 @Matrix

這個題除了算起來麻煩點意外沒啥難的吧。設 $A_{ij}$ 表示i和j重複的題目數小於等於3的概率，顯然所有的 $A_{ij}$ 相互獨立並且有概率

$p=frac{1}{C^{20}_n}sumlimits_{k=0}^3C_{20}^kC_{n-20}^{20-k}$

於是所求的n應該滿足 $p^{190}geq0.95$ 於是解之（上Mathematica）的n的最小值1151。

為了驗證上述方法，Matlab寫個隨機模擬

function p=kaoshimoni(N) p=0; for i=1:1000 s=zeros(20,20); for k=1:20 t=randperm(N); s(k,:)=t(1:20); end flag=0; for k1=1:20 s1=s(k1,:); for k2=(k1+1):20 s2=s(k2,:); if length(unique([s1 s2]))&<37 flag=1; break end end if flag==1 p=p+1; break; end end end p=1-p/1000; end

這裡樣本量為1000，從n=50開始，50為步長到2000為止模擬得到的概率形如：

概率的理論值和實際值對比如下：

足以說明所有問題。給我Mathematica和Matlab，這題五分鐘之內肯定做得完。

呃。。模擬了一下差不多1100吧，，為什麼都說要3000多。。

import random


for x in range(1100, 5000):

    count = 0

    for q in range(0, 1000):

        l = []

        for t in range(0, 20):

            l.append(random.sample(range(0, x), 20))
        for a in range(0, 20):

            f = False

            for s in range(a + 1, 20):

                if len(set(l[a])  set(l[s])) &> 3:

                    f = True

                    break

            if f:

                count += 1

                break

if count / 1000 &< 0.05: print(count / 1000, x) exit() print(x, count / 1000)

我覺得，用代碼暴力模擬整個抽籤的過程就可以。

代碼如下

可以再寫個程序用2分法找N的值，偷懶不寫了

另，我這個版本2000次算概率時候要跑兩秒，大概是對比不同時候檢測了190個LIST對，不知道有沒有更好的數學上的驗證方式，希望有大神解答。

20人中給定2個人有超過3題類似的概率可以由公式（C(N,20)-C(20,0)*C(N-20,20)-C(20,1)*C(N-20,19)-C(20,2)*C(N-20,18)-C(20，3)*C(N-20,17)）/C(N,20) 準確列出。而兩個人的選擇共有C(20,2)=190種給定組合，題目要求的是這190種可能的並集，先不考慮有2個以上人重複的話，就把上述公式乘190&>=0.05，得到最小解為1158，給定2人重複的概率為0.000263，3人或以上發生重複的概率至少是這個數字的平方，太小了，確實可以忽略，估計準確數字應該比1158略小。

==========================================================================

如果僅考慮容斥原理的第一個重複項，即2組4人重複的情況，用C(20,2)*C(18,2)*上面算的2個人重複概率（.000263）的平方(在這兒忽略了更複雜的2組3人的情況）,用Excel可以算出N&>=1146 。

看到95.......難倒....不是求Confidence interval ?

我只想問這道題馬雲做得出來的么？

算一算就知道了

最後答案收斂在1146

所以所謂的近似解真的只是數量級相同而已

代碼如下，忽略魔數和命名吧