九宮格匡列機率討論

最近推出了新的隔離政策，班上只要有人確診，他位置附近的九宮格內的人都必須被匡列。雖然這個隔離方式本來就怪怪的，不過我們還是可以針對被隔離的機率做一些小小的計算！

為了計算方便，都是限制在正方形的座位排列下，對9人、16人、25人或36人的情況做討論，且每一個人確診機會是相同的。這篇文章總共分為三個部分，首先是在固定確診人數下，討論不同位置的隔離機率。接著是討論確診人數與全班都被隔離的機率關係。最後，要討論的是讓全班停課所需最少人數的期望值。

一、不同座位的隔離機率

問題描述：某班有36個同學，座位是6x6的方格排列，試問當班上有4個同學確診，不需要被隔離的機率有多少？

問題觀察與推導

一開始看到題目可能會遇到一個大問題，在不同座位的確診者被隔離的人數也就不同。以下圖為例，坐在角落只需要匡列三個人，而坐在靠邊以及中間的人若確診則需要匡列五人以及八人，換句話說，做靠邊或角落的人比起中間的人越不容易被匡列隔離。接下來針對不同位置分別進行討論。

座位在角落情況

我們將坐在角落而不被匡列的機率設為$P_c$。此人被匡列的情況可以分為三種，也就是他周圍三個位置分別有一、二或三人確診，針對這三種情形我們可以列出以下算式：

$P_c = 1 - \frac{C^3_1C^{32}_3+C^3_2C^{32}_2+C^3_3C^{32}_1}{C^{35}_4}\approx 0.6868$

從他隔壁的3個位置取一到三個位置作為確診者，剩下的確診者從 $36-4=32$ 個位置任選其中幾個。

座位靠邊、中間情況

這兩種情況的機率$P_e,P_m$也可以用一樣的方式算出來，但其實有點麻煩因為有四種情況要列出來。偶然發現，其實用反面作法還蠻麻煩的，用正面做其實快很多！只要附近的位置數量扣掉，讓剩下的位置安排確診者，取一次C就完成了！

$P_e = \frac{C^{30}_4}{C^{35}_4} \approx 0.5234$

中間$P_m$的情況：

$P_m = \frac{C^{27}_4}{C^{35}_4} \approx 0.3352$

有了$P_c,P_e,P_m$之後，對於原題隨機位置下的機率，由於每一個位置出現的機率相等，便可透過各個位置的數量進行加權平均，得到隨機情況下的機率。

$\begin{align}P &= \frac{1}{36}(4P_c+16P_e+16P_m)\\ &\approx 0.4579\end{align}$

程式機率計算

程式碼連結
 模擬結果連結

一開始在還沒有想出問題的解之前，想說先用程式暴力驗證看看機率為何。總共的組數是 $C^{36}_4 = 58905$ 種情況，透過枚舉每一種情況健康的人數，算出在一個人沒有確診情況下不被匡列隔離的機率。

隨機坐不被匡機率：0.457898 ,次數：58905

看到這個結果可以大概推知，當班上有四個人確診，則班上的人其實有超過一半的機會要被隔離。這就讓我進一步思考到，班上座位有些跟周圍接觸到的人較多、有些較少，那這些是否會影響到被匡列的機率？由於每一個人確診的機會是一樣的，因此就把情況分為三種，分別是角落、靠邊以及中間，而相同情況下接觸的人數是一樣多的，隨便取一個位置進行觀察即可。

由於要排除自己確診的情況，總共的組合數會是 $C^{35}_4 = 52360$，不被匡列的機率如下：

坐角落不被匡機率：0.686784 ,次數：52360
坐靠邊不被匡機率：0.523396 ,次數：52360
坐中間不被匡機率：0.335180 ,次數：52360

如上圖，分別挑位置是(1,1),(2,3),(2,4)的人進行觀察，不用匡列機率則是以健康人數（上圖H）除上非確診人數（上圖H+Q）。

二、確診人數與全班隔離機率

3x3排列情況
 4x4排列情況
 程式碼連結

轉換一下問題的面向，我們把確診者的數量當作其中一個變因，試著討論確診人數與全班隔離的機率關係。對於一個有$n$人的班級，總共的排列數為$2^n$，我們將全班都會被隔離的情況挑出來，統計其數量。

3x3排列情況

下圖橫坐標為確診人數，縱座標為對應的組數，灰色則是該確診人數的組合數。可以發現到，當人數增加，其全班隔離的組數呈現先增後減的趨勢，而對應到的全班被隔離的機率（紅與灰長度比）隨確診人數漸增。折線圖的部分則代表在相同確診人數下全班被隔離組數佔組合數的比例。

期望值：在全班被匡列的情況下，此情況的確診人數的期望值為：4.88249人

4x4排列情況

期望值：在全班被匡列的情況下，此情況的確診人數的期望值為：8.5333人

5x5排列情況

期望值：在全班被匡列的情況下，此情況的確診人數的期望值為：13.1412人

程式具體的實作細節是將每一種情況進行狀態壓縮，存在一個int裡面，然後對每一個bit進行枚舉。在人數為$n$人的情況下，複雜度為$2^n$。這樣的複雜度在枚舉36人的情況會需要10幾個小時才能跑完。嘗試使用dfs進行剪枝，減少實際判斷的次數，不過效果不盡理想，可能還是要針對複雜度的部分進行優化才行。

三、讓全班停課所需最少人數期望值

程式碼連結

第二部分是將所有可能造成全班被匡列的情況都找出來，但這並不是「讓全班停課所需最少人數的期望值」，因為它的前提被限制在所有人都全班都被匡列的前提之下，且會有很多情況是要被扣除掉的。要找出最少人數的期望值，我們將每一個位置的確診狀況進行遞迴，直到一種組合能以最少人數的情況下讓全班隔離。到了那種情況之後，接下來不管怎麼安排接下來的位置，也一定能讓全班被匡列。