close section ▶
一、介紹
單人彩球遊戲的玩法如下：先將黑、白、灰三種顏色的彩球共 $n$ 顆排成第一列, 稱為此遊戲的「題目」。 接下來對每一列重複以下的操作： 在第 $k$ 列的下方擺放第 $k+1$ 列, 使得第 $k+1$ 列的每顆球均位於第 $k$ 列的相鄰兩顆球之間的正下方 (因此第 $k+1$ 列會比第 $k$ 列少一顆球), 而且第 $k+1$ 列每顆彩球顏色的擺放規則為
若上方相鄰兩球同色, 則下方就擺放相同顏色的球；
若上方相鄰兩球異色, 則下方就擺放第三種顏色的球。
依此規則擺放彩球直到第 $n$ 列為止, 此時第 $n$ 列只剩一顆球, 我們將這顆球的顏色稱為此題的「解」。
例如：
第三種顏色的球 相同顏色的球
若第一列放的五顆球如下：
則第二列按照規則為
一直放到第五列
此時發現, 最後一顆球是「灰色」, 我們就稱此題的解為「灰色」。
游森棚教授
二、建立數學模型
若想要直接求出此遊戲的一般解, 而不想要一顆一顆地慢慢擺放彩球來求解的話, 首要步驟, 就是要將彩球顏色的擺放規則 (第一節第一段中的標楷體文字敘述) 做數學建模。 若能有較簡單的數學建模, 則就能有較容易的方式得到此遊戲的一般解。
為了能夠「計算」顏色, 我們將彩球的顏色以數字標號取代： 黑球的標號為 0, 白球的標號為 1, 灰球的標號為 2。 接下來我們便把彩球的顏色都直接以其標號取代。 我們先來看看彩球顏色的擺放規則以標號表示時有什麼特性。 設某一列相鄰兩彩球的標號依序為 $x$ 和 $y$, 而它們下方彩球的標號為 $z$。 由彩球顏色的擺放規則可知 $x,y,z$ 三數可能情形有： 全為 0；全為 1； 全為 2； 或 0, 1, 2 各出現一次。 因此有 $x+y+z=0$ 或 3 或 6, 故 $x+y+z$ 必為 3 的倍數。 由此特性, 我們便將彩球的標號 0, 1, 2 視為 ${\Bbb Z}_3$ 中的元素, 並利用 mod 3 的運算來簡化 $x$, $y$, $z$ 的關係式可得 $x+y+z\equiv 0$ (mod 3)。 所以 $z\equiv -(x+y)$ (mod 3), 也就是下方彩球的標號為上方相鄰兩彩球標號相加後變號再 mod 3。 接下來文中的計算均為在 ${\Bbb Z}_3$ 中的運算, 即 mod 3。 例如：兩白球下方的彩球標號為「$-(1+1)\equiv 1$ (mod 3)」, 即白色；黑灰兩球下方的彩球標號為「$-(0+2)\equiv 1$ (mod 3)」, 即白色。
將彩球顏色的擺放規則, 巧妙地轉換成數學運算後, 接下來就可以假設變數, 並推導出其通解了。 以第一列擺放五顆球為例, 假設其標號依序為「$a$, $b$, $c$, $d$, $e$」, 則第二列應為「$-(a+b),-(b+c),-(c+d),-(d+e)$」, 第三列應為「$(a+2b+c),(b+2c+d),(c+2d+e)$」, 第四列為「$-(a+3b+3c+d)$, $-(b+3c+3d+e)$」, 而最後的解答為「$a+4b+6c+4d+e$」
由上面的例子我們可以觀察到： 若將某列彩球的標號表示成第一列變數的線性組合, 則其係數都是二項式係數。 為了明確寫出下面的定理, 我們將第 $i$ 列第 $j$ 球的標號令為 $a_{i,j}\in {\Bbb Z}_3$, 其中 $i=1,2,\ldots,n$, $j=1,2,\ldots,n+1-i$, 則彩球顏色的擺放規則為 $a_{i,j}\equiv -(a_{i-1,j}+a_{i-1,j+1})$ (在 ${\Bbb Z}_3$ 中的運算)。
則每顆球的標號 $a_{i,j}$ 皆可以用第一列的球的標號來表示：
定理 1. $a_{i,j}\equiv (-1)^{i-1} \displaystyle\sum\limits_{k=0}^{i-1} \displaystyle{i-1 \choose k} a_{1,j+k}(\hbox{mod}\, 3).$
證明： 對 $i$ 做數學歸納法。
當 $i=1$ 時, 右式只有在 $k=0$ 時有值, 所以 $(-1)^{1-1} \displaystyle{1-1 \choose 0} a_{1,j+0}\equiv a_{1,j}$, 成立。
當 $i\gt 1$ 時 \begin{align*} a_{i,j}&\equiv -(a_{i-1,j}+a_{i-1,j+1})\\ &\equiv -\Big((-1)^{i-2} \sum_{k=0}^{i-2} {i-2\choose k} a_{1,j+k} +(-1)^{i-2}\sum_{k=0}^{i-2} {i-2\choose k} a_{1,j+k+1} \Big)\\ &\equiv -\Big((-1)^{i-2}\sum_{k=0}^{i-2} {i-2\choose k} a_{1,j+k}+(-1)^{i-2} \sum_{k=1}^{i-1}{i-2\choose k-1} a_{1,j+k} \Big)\\ &\equiv -\Bigg((-1)^{i-2} \sum_{k=0}^{i-1}\Big({i-2\choose k}+{i-2\choose k-1}\Big) a_{1,j+k}\Bigg)\\ &\equiv (-1)^{i-1} \sum_{k=0}^{i-1}{i-1\choose k} a_{1,j+k}.\tag*{$\Box$} \end{align*}
此定理比較直覺的想法, 就是把 $a_{i,j}$ 寫成 $a_{1,x}$ 的線性組合時, 其係數就是由第 1 列第 $x$ 球, 每步可往左下或右下歨, 最後走到第 $i$ 列第 $j$ 球的方法數, 再多乘個正負號, 亦即 $$a_{i,j}\equiv (-1)^{i-1} \sum_x \hbox{( 由第 1 列第 $x$ 球走到第 $i$ 列第 $j$ 球的方法數 )} a_{1,x}.$$
接下來我們來看個例子 :
例 2. 假設第一列依序放了「$101112022011$」。 請問第 $6$ 列第 $4$ 球標號 $a_{6,4}$ 為何 $?$
根據定理 1 得 $a_{6,4}\equiv (-1)^5 ( \underline{1} \times 1+ \underline{5} \times 1+ \underline{10} \times 2+ \underline{10} \times 0+ \underline{5} \times 2+ \underline{1}\times 2)$, 所以 $a_{6,4}\equiv -38\equiv 1$, 為白色球。
事實上, 我們可以用餘式定理, 先把係數 mod 3, 再計算, 會快一些。 $$a_{6,4}\equiv (-1)^5 ( \underline{1}\times 1+ \underline{2}\times 1+ \underline{1}\times 2+ \underline{1}\times 0+ \underline{2}\times 2+ \underline{1}\times 2)\equiv -2\equiv 1.$$
數論中有個盧卡斯定理, 是這樣講的：
定理[Lucas, 1878]： 假設 $p$ 為質數, 且非負整數 $m$, $n$ 的 $p$ 進位表示法分別為$\\ (\cdots m_k m_{k-1}\cdots m_1 m_0 )_p$ 與 $(\cdots n_k n_{k-1}\cdots n_1 n_0 )_p$, 則 $${m\choose n}\equiv\prod_{k\ge 0} {m_k\choose n_k}(\hbox{ mod}\, p).$$
根據盧卡斯定理, 我們可以推知, 若有任何一個 $n_k\gt m_k$, 則 ${m\choose n}$ 必為 $p$ 的倍數。 也因此, 我們可以用此性質來快速計算出某些彩球遊戲的解：
推論 3. 當 $i=3^t+1$ 時, 其中 $t\in {\Bbb N}$, 則 $a_{i,j}\equiv -(a_{1,j}+a_{1,i+j-1})$。
證明： 此時 $i-1$ 的三進位表示法為 $(1000\cdots 00)_3$ (即 1 後面有 $t$ 個 0), 根據盧卡斯定理, 只要 $k$ 不等於 $(100\cdots 00)_3$ 與 $(00\cdots 00)_3$, 則 ${i-1\choose k}\equiv 0$, 又 $i-1$ 必為奇數, 因此定理 1 中的 $$a_{i,j}\equiv (-1)^{i-1} \sum_{k=0}^{i-1} {i-1\choose k} a_{1,j+k}\equiv -(a_{1,j}+a_{1,i+j-1}).{\Box}$$
我們再來看個例子 :
例 4. 與例2 相同, 第一列依序放了「$101112022011$」。 請問第 $4$ 列第 $5$ 球標號 $a_{4,5}$ 為何 $?$ 請問第 $10$ 列第 $2$ 球標號 $a_{10,2}$ 為何 $?$
本來 $a_{4,5}\equiv (-1)^3 (1\times 1+3\times 2+3\times 0+1\times 2)\equiv 0$ 為黑色。 但由推論3 知, 中間的係數必為 3 的倍數, 故只需計算頭尾即可, $a_{4,5}\equiv -(1+2)\equiv 0$。 同樣的, $a_{10,2}\equiv -(a_{1,2}+a_{1,11})\equiv-(0+1)\equiv2$ 為灰色。
定理 5. 當 $i=s\cdot 3^t+1$ 時, 其中 $s,t\in {\Bbb N}$, 則 $$a_{i,j}\equiv (-1)^s \sum_{k=0}^s {s\choose k} a_{1,k\cdot 3^t+j}.$$
本定理一樣利用數學歸納法即可證明, 我們省略繁冗的過程, 直接看下面的例子：
例 6. 假設第一列依序放了「$1021120220101$」。 請問第 $13$ 列第 $1$ 球標號 $a_{13,1}$ 為何 $?$
因為 $13=4\times 3^1+1$, 所以 \begin{eqnarray*} a_{13,1}&\equiv& (-1)^4 ( \underline{1}\times a_{1,1}+ \underline{4}\times a_{1,4}+ \underline{6}\times a_{1,7}+ \underline{4}\times a_{1,10}+ \underline{1}\times a_{1,13})\\ &\equiv& (a_{1,1}+a_{1,4}+a_{1,10}+a_{1,13})\equiv 0 \end{eqnarray*} 為黑色。
例 7. 求 $a_{28,5}$ 的話, 因為 $28=27\times 3^0+1=9\times 3^1+1=3\times 3^2+1 =1\times 3^3+1$, 所以利用定理5, $s$ 與 $t$ 就有四種取法,
取 $(s,t)=(27,0)$ 時, 即為定理1, $a_{28,5}\equiv -(C_0^{27} a_{1,5}+C_1^{27} a_{1,6}+\cdots+C_{27}^{27} a_{1,32} )$。
取 $(s,t)=(9,1)$ 時, $a_{28,5}\equiv -(C_0^9 a_{1,5}+C_1^9 a_{1,8}+\cdots+C_9^9 a_{1,32})$。
取 $(s,t)=(3,2)$ 時, $a_{28,5}\equiv -(C_0^3 a_{1,5}+C_1^3 a_{1,14}+C_2^3 a_{1,23}+C_3^3 a_{1,32} )$。
取 $(s,t)=(1,3)$ 時, 即為推論3, $a_{28,5}\equiv -(C_0^1 a_{1,5}+C_1^1 a_{1,32} )$。
所以定理5 可以說是集大成, $s$ 取 $n-1$ 就是定理1, $s$ 取 1 就是推論3, 為了計算方便, s當然是越小越好, 計算的項數比較少 ($s+1$項)。
三、速算魔術
此遊戲若能夠速算, 即可成為一個數學魔術。
魔術師請觀眾隨意在第一列擺放三種顏色的球, 並告知其接下來每一列的擺法規則, 待觀眾知道規則後, 準備開始放時, 魔術師即可寫下最後一顆球的顏色「預言」。 過了許久, 等觀眾把最後一顆擺出來後, 魔術師才把剛剛寫好的預言拿出來對照, 果然沒錯！
方法是這樣的, 若觀眾在第一列擺的球數為 $n$, 設 $n-1$ 的 3 的次方的正因數中最大者為 $3^t$, 這樣的話 $n=s\cdot 3^t+1$ 的表示法中的 $s$ 最小。 若 $s$ 很小, 則利用定理5 即可很快地算出最後一顆球的標號； 若 $s$ 不夠小, 只好利用比 $n$ 小且型如 $s\cdot 3^t+1$ 的數, 多算幾次以求出最後一顆球的標號。
例 8. 假設觀眾第一列放了「$102112022010$」十二顆球。
第一種想法, 因第三列有 $12-2=10=1\times 3^2+1$ 顆球, 故先算第三列頭尾的球, 再算出答案。
第二種想法, 會快一些, 先算第 10 列的三顆球, 然後再算出答案。
讀者可以自己嘗試其它例子, 例如 11 顆球、 20 顆球, 馬上會發現, 不管流程怎麼分段, 若第一列用球數是最少的話, 球數都是相同的。 事實上, 還可以把用球數算出來。
定理 9. 若觀眾在第一列擺了 $n$ 顆球, 其中 $n-1=(\cdots n_k n_{k-1}\cdots n_2 n_1 n_0 )_3$, 則要計算出解的話, 第一列的用球數必為 $\prod\limits_{k\ge 0} (n_k+1)$ 顆球。
證明： 利用盧卡斯定理, 計算二項式係數不為 3 的倍數的數量即得。 $\Box$
例如觀眾若擺了 9 顆球的話, 因為 $8=(22)_3$, 由定理9 知必定會用到第一列的 $3\times 3=9$ 顆球, 所以第一列的每一顆都要被計算, 因此魔術師只能慢慢利用定理 1 來算了。此時該怎麼辦呢 ? 魔術師可以用一些言語上的誘導讓觀眾多放幾顆： 「最後, 你再選一顆, 插到到中間, 但在你還沒選擇插到哪個位置前, 我會先做個預言 $\cdots$」或是再選第二個觀眾上來多插一顆球到中間之類的。
當然魔術師也可以一開始就指定觀眾放特定顆數的球, 例如 10 顆、 19 顆 $\cdots$ 比較好算的數目, 但這樣就不能變太多次, 因為幾次之後, 觀眾就會想要放別種球數了。
另一種變型的版本如下：
魔術師請觀眾在紙上第一列隨意寫 6 個正整數, 而第二列的5個數, 每個都是用第一列相鄰的兩數相加, 一直寫到第 6 列, 剩下一個數。 魔術師會提早寫下「預言」, 內容是最後這個數除以 5 的餘數是多少 !
因為 5 是質數, 所以這個變型的版本, 一樣可以用定理5 改成 ${\Bbb Z}_5$ 來速算。 不過這個數字的版本, 容易被看出算法, 還是彩球的版本比較讓人驚艷, 畢竟它的數學建模不是這麼容易。
四、最少顆球決定盤面
原彩球遊戲的目的是要求出最下面一顆球的顏色, 現在我們改變一下遊戲目的： 能否選出若干顆球, 這些球的顏色任給, 都可以在不違背規則 (每顆球由上一列相鄰兩顆球的顏色決定)下, 把所有的球的顏色確定出來。
例 10. 以 $n=4$ 為例 $($第一列有 $4$ 顆球$)$,
若第一列的 $4$ 顆球任給顏色, 當然都可以把全部的 $10$ 顆球顏色求出。
若每一列的第一顆球顏色任給, 一樣也可以把 $10$ 顆球顏色都求出。
或是 $a_{1,1},a_{1,3},a_{2,2},a_{4,1}$ 這四顆球的顏色任給, 也都可以唯一決定所有球的顏色, 只是需要花一點時間嘗試。
那有沒有可能只選 $3$ 顆球, 其顏色任給, 都可以決定整個盤面呢 $?$ 答案是不可能的。 為什麼呢 $?$ 這就要用線性代數來回答這個問題了 $($以下的運算均為 ${\Bbb Z}_3$ 中的運算$)$。
依據「每顆球顏色由上一列相鄰兩顆球決定」的規則, 轉成數學模型, 即為 $$a_{i,j}=-(a_{i-1,j}+a_{i-1,j+1} )$$ 以 $n=4$ 為例, 可以列出下面的聯立方程組： $$ \left\{ \begin{array}{l} a_{2,1}=-(a_{1,1}+a_{1,2})\\ a_{2,2}=-(a_{1,2}+a_{1,3})\\ a_{2,3}=-(a_{1,3}+a_{1,4})\\ a_{3,1}=-(a_{2,1}+a_{2,2})\\ a_{3,2}=-(a_{2,2}+a_{2,3})\\ a_{4,1}=-(a_{3,1}+a_{3,2})\end{array}\right.\Rightarrow \left\{ \begin{array}{l} a_{1,1}+a_{1,2}+a_{2,1}=0\\ a_{1,2}+a_{1,3}+a_{2,2}=0\\ a_{1,3}+a_{1,4}+a_{2,3}=0\\ a_{2,1}+a_{2,2}+a_{3,1}=0\\ a_{2,2}+a_{2,3}+a_{3,2}=0\\ a_{3,1}+a_{3,2}+a_{4,1}=0.\end{array}\right.$$
此聯立方程組, 有 10 個未知數, 若只給定 3 個變數值的話, 也會剩下 7 個未知數, 而 6 條式子, 是不會有唯一解的。 依這個想法, 我們可以得到下面的定理：
定理 11. 第一列為 $n$ 顆球的盤面, 若選定其中 $k$ 顆球, 使得此 $k$ 顆球顏色任意給定, 都要能確定所有球的顏色的話, 則 $k$ 必為 $n$。
但是不是隨便選 $n$ 顆球都可以呢 ? 當然不是 ! 例如, 當 $n=4$ 時, 選定 $a_{1,1},a_{1,4},a_{2,2},a_{4,1}$ 這四顆球的話, 顏色給的不好, 就會無解。 下面這個狀況就是無解
那除了暴力法試之外, 有沒有好的方法可以判斷有沒有解呢 ? 當然有的 ! 把剛剛的聯立方程組, 寫成矩陣型式, 如下： $$\left[\begin{array}{cccccccccc} ~1~&~1~&~0~&~0~&~1~&~0~&~0~&~0~&~0~&~0~\\ 0&1&1&0&0&1&0&0&0&0\\ 0&0&1&1&0&0&1&0&0&0\\ 0&0&0&0&1&1&0&1&0&0\\ 0&0&0&0&0&1&1&0&1&0\\ 0&0&0&0&0&0&0&1&1&1 \end{array}\right] \left[\begin{array}{c} a_{1,1}\\ a_{1,2}\\ a_{1,3}\\ a_{1,4}\\ a_{2,1}\\ a_{2,2}\\ a_{2,3}\\ a_{3,1}\\ a_{3,2}\\ a_{4,1} \end{array}\right]= \left[\begin{array}{c} 0\\ 0\\ 0\\ 0\\ 0\\ 0 \end{array}\right]$$ 而 $a_{1,1},a_{1,4},a_{2,2},a_{4,1}$ 給定的話(變成常數), 就可以把它們移到等號右邊, 變成： $$\left[\begin{array}{cccccc} ~1~&~0~&~1~&~0~&~0~&~0~\\ 1&1&0&0&0&0\\ 0&1&0&1&0&0\\ 0&0&1&0&1&0\\ 0&0&0&1&0&1\\ 0&0&0&0&1&1\end{array}\right]\left[\begin{array}{c} a_{1,2}\\ a_{1,3}\\ a_{2,1}\\ a_{2,3}\\ a_{3,1}\\ a_{3,2}\end{array}\right]=\left[\begin{array}{c} -a_{1,1}\\ -a_{2,2}\\ -a_{1,4}\\ -a_{2,2}\\ -a_{2,2}\\ -a_{4,1}\end{array}\right]$$
此時左邊的係數矩陣, 即為原係數矩陣扣掉 $a_{1,1},a_{1,4},a_{2,2},a_{4,1}$ 對應的 $4$ 行, 而因為其行列式為 $0$ (在 ${\Bbb Z}_3$ 中), 所以右邊的常數向量就有辦法調整到讓此聯立方程組無解。
我們再來看一個例子：
例 12. 設 $n=3$, 其三個角落的球, 顏色任給, 是否都能決定出所有球的顏色呢 $?$
依前面的方式寫出聯立方程式的係數矩陣為 $\left[\begin{array}{cccccc} ~1~&~1~&~0~&~1~&~0~&~0~\\ 0&1&1&0&1&0\\ 0&0&0&1&1&1\end{array}\right]$, 扣除 $a_{1,1},a_{1,3}$ 與 $a_{3,1}$ 對應的行後, 為 $\left[\begin{array}{cccc}1&1&0\\ ~1~&~0~&~1~\\ 0&1&1\end{array}\right]$, 其行列式為 $-2\not=0$ $($在 ${\Bbb Z}_3$ 中$)$, 所以 $a_{1,1},a_{1,3},a_{3,1}$ 三球顏色任給, 皆能決定整個盤面。 這個結果其實不是那麼容易看出來。
再更進一步, 若選定的球超過 $n$ 顆是否有解 ? 選定的球少於 $n$ 顆的話, 必不能決定所有球的顏色, 但總共有幾組解呢? 這些全都可以在線性代數中找到解答, 我想就到此打住吧 !
五、結語
單人彩球遊戲, 把擺放的規則設計成數學運算後, 就可以推導出不少性質。 即使是推廣成 $p$ 種顏色的球, 也是大同小異, 不過若 $p$ 不是質數的話, 就不是所有的定理都能用 (因為盧卡斯定理條件不成立)。 另一方面, 也可以討論推廣成三維的情況, 例如第一層擺成三角形或正方形, 然後一層一層往上擺成三角垛或正方形垛, 推出剩最後一顆時的顏色。 也是會跟兩球間的最短路徑數有關, 不過麻煩的是, 運算三角垛的話, 可以用類似 $(x+y+z)$ 的運算決定上一層的球所代表的數, 但怎麼讓數字轉回顏色後合理化, 就留給有興趣的讀者思考了。
參考資料
---本文作者徐祥峻為國立臺灣師範大學數學系博士後研究員, 郭君逸任教國立臺灣師範大學數學系---