用遞歸關係玩「開口中」

在 2002 年播映的《吾係獎門人》中有一個環節叫「吾係開口中」。因為「開口中」簡單易玩，而且緊張刺激，所以在很多場合中都有人玩這個遊戲。現在給大家想一個問題。如果只有兩個人玩「開口中」，我們應該怎樣選擇數字才能令勝出的概率增加？先選或後選數字比較有利？

在清楚說明這個問題前，我們先介紹這個遊戲的玩法：

1. 選定一個區間的整數（例如 1 至 100），再由一位公正人選定其中一個數字作為「壞數」；
2. 二人輪流從區間中選取一個數字。若某選中壞數，則對方勝出遊戲，遊戲結束。否則，選中的數字會將整個區間分成兩份，其中一份包含壞數。對方再選數字的區間將會變為那個包含壞數的區間。

以下是一個例子：

假設壞數是 45。若第一名玩家（先手）選取 25，則第二名玩家（後手）可選取的區間是 26 至 100。若後手選 90，則先手再選的區間是 26 至 89。這個遊戲一直玩下去，直至某人選中 45。

1 至 100 這個區間太大了，現在我們先討論一些較小的情形。（注：在以後的討論，我們假設公正人選壞數是隨機的，亦即每個數是壞數的概率相等。）

1. 若區間有 1 個數（1），明顯地1就是壞數，因此先手勝出的概率是 0。

2. 若區間有 2 個數（1 和 2），先手選中壞數的概率是 。若他選不中壞數，則後手會只有 1 個選擇，必輸無疑。因此，先手勝出的概率是。

3. 若區間有 3 個數（1、2 和 3），先手選任何一個數時，選中壞數的概率都是。若他選 1 而沒有輸，則後手回到情況 B （一個有兩個數的區間），在這個情況下，後手勝出的概率是。因此，他選 1 而勝出的概率是。若他選 2 而沒有輸，則壞數是 1 或 3。若壞數是 1，後手會回到情況 A，勝出的概率是 0。若壞數是 3，後手亦會回到情況 A，勝出的概率亦是 0。因此，先手選 2 而勝出的概率是。明顯地，選3的情況和選 1 類似，勝出的概率是。所以，先手的最佳策略是選 2，此時他勝出的概率是。

在上述的討論中，我們可以看到解決有 3 個數的情況時，我們需要運用在區間較小的情況的結果（即情況 A 和 B）。因此，我們可以想像當區間愈來愈大時，求最佳策略時也應該需要考慮類似的情況。這即是數學中的遞歸關係。

現在我們定義以下幾項：

當某區間有 n 個數時（設它們為 1、2、……、n），先手選取 k 時最後勝出的概率是 P(n, k)。同時，定義 [1]，即先手在這種情況可獲得最大的勝出概率。

例如，從上面的結果可知下表：

表 1：一些初步結果

我們希望算出每個 P(n, k) 與 P_m(m < n) 之間的關係。

設區間有 n 個數 1、2、……、n。若先手選取 k ，他立即輸掉的概率是。假設他不立即輸掉，則有 的概率令後手可選的範圍變為1、2、3……k–1，共 k–1 個數；有 的概率令後手可選的範圍變為 k+1、k+2、k+3……n，共 n–k 個數；在第一種情況，後手勝的概率是 P(k– 1)，即先手勝的概率是 1 – P(k – 1)。此時，先手勝出的概率是 。

相似地，在第二種情況，先手勝出的概率是 。因此，我們有 [2]。利用表 1，我們可以推算下面整個表 2：

		Pn

表 2：根據方程 1 和 2 計算出來的 P (n, k) 和 P_n

雖然表 2 只列舉了 n 不大於 13 的情況，但我們容易看到表中的值都有一個 4 行出現一次的規律。

證明方法亦不難，此處從略。從表 2，我們看到以下的情況︰

• 當 n º 0 (mod 4) 時， k º 2 或 3 (mod 4) 時可令 P(n, k) 的值最大，此時 。

• 當 n º 1 (mod 4) 時，所有 P (n, k) 的值都相等，此時 。

• 當 n º 2 (mod 4) 時， k º 1 或 2 (mod 4) 時可令 P (n, k) 的值最大，此時 。

• 當 n º 3 (mod 4) 時， k º 2 (mod 4) 時可令 P (n, k) 的值最大，此時 。

因此，若我們可以選擇先後，我們應作出下列選擇：

• 當 n º 1 (mod 4)，選後手；

• 當 n º 3 (mod 4)，選先手；

• 當 n 是偶數，選先或後都一樣。

設可選的區間長度為 n。

• 當 n º 0 (mod 4)，選第 4t +2 或 4t +3 個數；

• 當 n º 1 (mod 4)，任選；

• 當 n º 2 (mod 4)，選第 4t +1 或 4t +2 個數；

• 當 n º 3 (mod 4)，選第 4t +2 個數。

（t 是任何非負整數）

我們可從上表看到一個很有趣的結果，除非可選的數只剩 1 個（此時必輸無疑），否則永遠選第 2 個數便可以獲得較大的得勝機會率了。