概率證明

有些時候，我們可以利用概率的性質來證明一些組合題。即使題目本身看來和概率毫不相干，但加入了概率的考慮往往可以讓我們得出一個簡潔的證明。以下提供一個例子。

問題：

某學校響應微調政策，開辦的 n 個科目均設中文班和英文班。每位同學均可自由選讀不同的科目，數量不限，但同一科目不可同時報讀中文班和英文班。已知對任意兩個科目，均存在一名學生以不同語文同時修讀兩科。若每科最多有 10 名學生修讀，求 n 的最大可能值。

大家看下去前，不妨先停下來自己動動腦筋。

解答：

n 的最大可能值是 1024。

我們首先注意到 n=1024 是可能的：如果全校有 10 位學生，每人均報讀全部 1024 個科目，且學生 i 報讀第 j 個科目的中文班當且僅當 j 的二進制表示中右方數起的第 i 個位是 1（否則報讀第 j 個科目的英文班），則不難檢查得知這符合題中的條件。

以下證明 n 不可大於 1024。假設學生入學時會被隨機編成「中文人」或「英文人」。設 E_i 表示事件「第 i 個科目的學生全部選讀了對應自己身份的語文班」，則由於每科最多有 10 名學生修讀，故 P(E_i) ≧ 1/2¹⁰ = 1/1024。再者，由「對任意兩個科目，均存在一名學生以不同語文同時修讀兩科」可知 E₁、E₂、…、E_n 是互斥事件，故此

1 ≧ P(E₁∪E₂∪…∪E_n) = P(E₁) + P(E₂) + ... + P(E_n) ≧ n/1024，

從而必有 n≦1024。

這個帶點神秘感的概率題解，某程度上其實對應一些數算的技巧，再用概率加以包裝。概率證明還可以處理一些更複雜的情況，例如可以使用 Lovasz local lemma 來處理一些難以準確計算的概率，有興趣的讀者可點擊上方的連結細看。順帶一提，證明以上定理的 Lovasz 曾在國際數學奧林匹克（IMO）奪得三金一銀，而他的兒子至今亦已在 IMO 奪得一金一銀！