談韓信點兵問題-蔡聰明-(1)

查看文章

談韓信點兵問題-蔡聰明-(1)

2008-06-09 21:31

觀察、試誤與系統列表

數學的解題，包括問題、答案、求得答案的思路過程,以及過程中所結晶出來的普遍概念、方法和數學理論。只有答案與計算技巧的堆積無法顯現數學的妙趣。

在《孫子算經》裡（共三卷，據推測約成書於西元400年左右），下卷的第26題，就是鼎鼎有名的「孫子問題」：

今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？

將它翻譯成白話：這裡有一堆東西，不知道有幾個；三個三個去數它們，剩餘二個；五個五個去數它們，剩餘三個；七個七個去數它們，剩餘二個；問這堆東西有幾個？精簡一點來說：有一個數，用 3 除之餘 2；用 5 除之餘 3；用 7 除之餘 2；試求此數。

用現代的記號來表達：假設待求數為 x，則孫子問題就是求解方程式：

$\begin{displaymath} \left \{ \begin{array}{l} x=2 \pmod{3} \\ x=3 \pmod{5} \\ x=2 \pmod{7} \end{array}\right. \end{displaymath}$

其中 $a = b \pmod{n}$ 表示 a-b 可被 n 整除。

這個問題俗稱為「韓信點兵」（又叫做「秦王暗點兵」、「鬼谷算」、「隔牆算」、「剪管術」、「神奇妙算」、「大衍求一術」等等），它屬於數論 (Number theory) 中的「不定方程問題」(Indeterminate equations)。

孫子給出答案：

答曰：二十三

事實上，這是最小的正整數解答。他又說出計算技巧：

術曰：三三數之剩二，置一百四十；五五數之剩三，置六十三；七七之數剩二，置三十。并之得二百三十三。以二百一十減之，即得。凡三三數之剩一，則置七十；五五數之剩一，則置二十一；七七數之剩一，則置十五。一百六以上，以一百五減之，即得。

這段話翻譯成數學式就是：

$\begin{eqnarray*} x &=& 2 \times 70 +3\times 21 + 2\times 15-2\times 105 \\ &=& 140+63+30-210 \\ &=& 23 \end{eqnarray*}$

此數是最小的正整數解。

為了突顯 70、21、15、105 這些數目，明朝的程大位在《算法統宗》（1592年）中，把它們及解答編成歌訣：

三人同行七十稀，五樹梅花廿一枝，
七子團圓正半月，除百零五便得知。

另外，在宋代已有人編成這樣的四句詩：

三歲孩兒七十稀，五留廿一事尤奇，
七度上元重相會，寒食清明便可知。

這些都流傳很廣。「上元」是指正月十五日，即元宵節，暗指「15」；而「寒食」是節令名，從冬至到清明，間隔105日，這段期間叫做「寒食」，故「寒食」暗指「105」。

本文我們要來探索韓信點兵問題的各種解法，它們的思路過程與背後所涉及的數學概念和方法。

觀察、試誤與系統列表

按思考的常理，面對一個問題，最先想到的辦法就是觀察、試誤 (trial and error)、投石問路、收集資訊，再經系統化處理，這往往就能夠解決一個問題；即使不能解決，對該問題也有了相當的理解，方便於往後的研究或吸收新知。

首先考慮被 3 除之餘 2 的問題。正整數可被 3 整除的有 3,6,9,12, $\cdots\cdots$ ，所以被 3 除之餘 2 的正整數有 2,5,8,11,14, $\cdots\cdots$ 。其次，被 5 除之餘 3 的正整數有 3,8,13,18, $\cdots\cdots$ 。最後，被 7 除之餘 2 的正整數有 2,9,16,23, $\cdots\cdots$ 。將其系統地列成表一，以利觀察與比較。

表一

被3除之餘2 2,5,8,11,14,17,20,23,26 $\cdots\cdots$

被5除之餘3 3,8,13,18,23,28,33,38,43 $\cdots\cdots$

被7除之餘2 2,9,16,23,30,37,44,51,58 $\cdots\cdots$

我們馬上可從表一看出23是最小的正整數解。

有一位四年級的小學生，他耐心地繼續計算下去，得到第二個答案是128，第三個答案是233，接著又歸納出一條規律；從23開始，逐次加105都是答案（這是磨練四則運算的好機會）。從而，他知道孫子問題有無窮多個解答。不過，小學生還沒有能力把所有的解答寫成一般公式：

$\begin{displaymath} x=23+105\cdot n , \quad n \in \mathbf{N}_0 %%\eqno{(1)} \end{displaymath}$

(1)

其中， $\mathbf{N}_0 = \{0,1,2,3,\cdots\cdots\}$ 。

根據機率論，一隻猴子在打字機前隨機地打字，終究會打出莎士比亞全集，其機率為 1。這是試誤法中，最令人驚奇的一個例子。人為萬物之靈，使用試誤法當然更高明、更有效。總之，我們可以（且必須）從錯誤中學習。

分析與綜合

根據笛卡兒（Descartes, 1596～1650）的解題方法論：面對一個難題，儘可能把它分解成許多部分，然後由最簡單、最容易下手的地方開始，一步一步地拾級而上，直到原來的難題解決。換言之，你問我一個問題，我就自問更多相關的問題，由簡易至複雜，舖成一條探索之路。

現在我們考慮比孫子問題更一般的問題：

問題1. 試求出滿足下式之整數 x：

$\begin{displaymath} \left \{ \begin{array}{cc} x=3q_1+r_1,&0 \leq r_1< 3 \\ x=5... ...eq r_2< 5 \\ x=7q_3+r_3,&0 \leq r_3< 7 \\ \end{array}\right. \end{displaymath}$

(2)

孫子問題是 r₁=2，r₂=3，r₃=2 的特例：

$\begin{displaymath} \left \{ \begin{array}{c} x=3q_1+ 2\\ x=5q_2+ 3\\ x=7q_3+ 2\\ \end{array}\right. \end{displaymath}$

(3)

為了求解這個特例，我們進一步考慮一連串更簡單的特例。基本上，這有兩個方向：剩餘為 0 或只有單獨一個方程式。

單獨一個方程式

欲求

x=3q₁+2

(4)

的整數解 x，顯然解答的全體為

$\begin{displaymath} S=\{\cdots,-7,-4,-1,2,5,\cdots\} \end{displaymath}$

這些解答可以寫成一個通式：

$\begin{displaymath} x=3n+2, \quad n\in \mathbf{Z} \end{displaymath}$

(5)

其中 Z 表示整數集。事實上，(5)式只是(4)的重述。

進一步，通解公式(5)也可以寫成

$\begin{displaymath} x=3n+5, \quad n\in \mathbf{Z} \end{displaymath}$

或

$\begin{displaymath} x=3n+(-4), \quad n \in \mathbf{Z} \end{displaymath}$

等等。換言之，通解公式可以表成 x=3n, $n \in \mathbf{Z}$ ，與 x=2（或 x=5，或 x=-4 等等）這兩部分之和。前一部分是 x=3q₁ 之通解，後一部分是 x=3q₁+2 的任何一個解答（叫做特解）。

這告訴我們，欲求 x=3q₁+2 之通解，可以分成兩個簡單的步驟：先求 x=3q₁ 的通解，再求 x=3q₁+2 的任何一個特解，最後將兩者加起來就是 x=3q₁+2 的通解公式。

這對於兩個方程式的情形也成立嗎？這是否為一般的模式 (pattern)？下述我們將看出，這是肯定的。

兩個方程式

其次，考慮

$\begin{displaymath} \left \{ \begin{array}{c} x=3q_1+2 \\ x=5q_2+3 \end{array}\right. \end{displaymath}$

(6)

的整數解 x。為此，我們考慮更簡單的齊方程式問題：

$\begin{displaymath} \left \{ \begin{array}{c} x=3q_1+0\\ x=5q_2+0 \end{array}\right. \end{displaymath}$

(7)

這表示 x 可以同時被 3、5 整除，即 x 是 3、5 的公倍數。因為這兩個數互質，所以 3 x 5=15 是它們的最小公倍數。從而，

$\begin{displaymath} x=15\cdot n, \quad n \in \mathbf{Z} \end{displaymath}$

(8)

是(7)式的齊次方程之通解公式。

如何求得(6)式的一個特解？這可以採用試誤法，也可以系統地來做。今依後者，考慮比(7)式稍微進一步的問題：

$\begin{displaymath} \left \{ \begin{array}{c} x=3q_1+1\\ x=5q_2+0 \end{array}\right. \end{displaymath}$

(9)

這是要在 5 的倍數中

$\begin{displaymath} \cdots -10,-5,0,5,10,15,\cdots \end{displaymath}$

找被 3 除餘 1 者。由於我們只要找一個特解，故不妨選取 x=10。從而

$\begin{displaymath} \left \{ \matrix{ x=3q_1+2 \cr x=5q_2+0 \cr } \right. \end{displaymath}$

(10)

的一個特解為 x=2 x 10。同理，我們找到

$\begin{displaymath} \left \{ \matrix{ x=3q_1+0 \cr x=5q_2+1 \cr } \right. \end{displaymath}$

(11)

的一個特解 x=6，於是 x=3 x 6 為

$\begin{displaymath} \left \{ \matrix{ x=3q_1+0 \cr x=5q_2+3 \cr } \right. \end{displaymath}$

(12)

的一個特解。因此

x=2 x 10+3 x 6

(13)

為(6)式的一個特解。

將(8)式與(13)式相加，得到

$\begin{displaymath} x=2\times10+3\times6+15\cdot n, \quad n\in \mathbf{Z} \end{displaymath}$

(14)

這是(6)式的通解公式（窮盡了所有解答）嗎？

答案是肯定的，我們證明如下：根據上述的建構，顯然(14)式為(6)的解答。反過來，設 A 為(6)式的任意解答，則 A-2 x 10-3 x 6 為(7)式的解答，而(7) 式的解答形如 $15\cdot n$ ，因此 $A-2\times 10-3 \times 6=15 \cdot n$ ，亦即 A 可表成

$\begin{displaymath} A=2\times 10+3\times 6+10\cdot n, \quad n\in\mathbf{Z} \end{displaymath}$

換言之，(6)式的任意解答皆可表成(14)之形，所以(14)式為(6)式之通解公式。

孫子問題

現在我們再往前一步，來到孫子問題，即(3)式之求解。仿上述辦法，先解齊次方程：

$\begin{displaymath} \left \{ \begin{array}{l} x=3q_1+0\\ x=5q_2+0\\ x=7q_3+0 \end{array}\right. \end{displaymath}$

得到通解公式為

$\begin{displaymath} x = 3 \times 5\times 7\times n = 105 \cdot n, \quad n \in \mathbf{Z} \end{displaymath}$

(15)

其次，我們分別找

$\begin{eqnarray*} \left \{ \begin{array}{l} x=3q_1+1\\ x=5q_2+0\\ x=7q_3+0 \en... ...{array}{l} x=3q_1+0 \\ x=5q_2+0 \\ x=7q_3+1 \end{array}\right. \end{eqnarray*}$

之特解，得到 x=70,x=21,x=15。從而

x=2 x 70 +3 x 21+2 x 15

(16)

為孫子問題（即(3)式）的一個特解。

將(15)式與(16)式相加起來，得到

$\begin{displaymath} x=2\times 70 +3\times 21+2\times 15+105\cdot n , \quad n\in \mathbf{Z} \end{displaymath}$

(17)

我們仿上述很容易可以證明，(17)式就是孫子問題的通解公式。特別地，當 n=-2 時，x=23 為最小正整數解。

类别：数学问题 | 添加到搜藏 | 浏览() | 评论 (0)