數學傳播

我們在學習自然科學(例如物理和化學)時, 伴隨的總有實驗課, 但是在學習數學時, 從來不曾聽說有實驗這門課。 我向來主張數學要有實驗, 二十年前在交通大學應數系任教時, 就曾經嚐試開過一門數學實驗的課, 認為數學可以借助實驗尋求定理, 而做實驗的工具除了傳統的紙筆之外, 電腦是一種很有效的工具。 我的這個想法可以回溯到三十年前的經驗, 那時候我剛從金門退伍, 在劉豐哲老師的幫忙下, 到中央研究院數學所當助理。

中研院真是一個讀書的好地方, 環境清幽、圖書豐富。 有一天我翻到德國人Harborth的一篇文章, 它主要是解決Steinhaus提出來的一個問題, 我有關數學實驗的經驗就是從這裡開始的。

波蘭數學家Steinhaus響應當時數學家貢獻高中數學教育的熱心, 於1963年寫了一本百題初等數學的書, 書中附有詳細解答。 除了這一百則有解答的題目之外, 這本書也列了十二個未解的題目, 其中的第一則就是我們現在要討論的主題。

下圖含有14個正號及14個負號, 它們滿足一個性質: 兩個相同符號的下方有一個正號、 兩個相異符號的下方有一個負號。

$+$ $+$ $-$ $+$ $-$ $+$ $+$
$+$ $-$ $-$ $-$ $-$ $+$
$-$ $+$ $+$ $+$ $-$
$-$ $+$ $+$ $-$
$-$ $+$ $-$
$-$ $-$
$+$

如果第一列有 $n$ 個符號, 則可以用上述規則建出有 $n(n+1)/2$ 個符號的倒三角形。 當 $n=3, 4, 7, 8, 11, 12,\ldots$ 的時候 $n(n+1)/2$ 為偶數, Steinhaus有興趣的是, 對這些 $n$, 能不能造出正號和負號個數相同的三角形。他給出了如下 $n=12$ 及 $n=20$ 的答案, 將這兩個三角形的第一列去掉, 就得到 $n=11$ 及 $n=19$ 的答案。

$-$ $+$ $+$ $-$ $-$ $+$ $-$ $-$ $+$ $+$ $+$ $-$
$-$ $+$ $-$ $+$ $-$ $-$ $+$ $-$ $+$ $+$ $-$
$-$ $-$ $-$ $-$ $+$ $-$ $-$ $-$ $+$ $-$
$+$ $+$ $+$ $-$ $-$ $+$ $+$ $-$ $-$
$+$ $+$ $-$ $+$ $-$ $+$ $-$ $+$
$+$ $-$ $-$ $-$ $-$ $-$ $-$
$-$ $+$ $+$ $+$ $+$ $+$
$-$ $+$ $+$ $+$ $+$
$-$ $+$ $+$ $+$
$-$ $+$ $+$
$-$ $+$
$-$

$+$ $+$ $+$ $+$ $-$ $-$ $+$ $-$ $-$ $-$ $+$ $+$ $+$ $+$ $-$ $-$ $-$ $-$ $-$ $+$
$+$ $+$ $+$ $-$ $+$ $-$ $-$ $+$ $+$ $-$ $+$ $+$ $+$ $-$ $+$ $+$ $+$ $+$ $-$
$+$ $+$ $-$ $-$ $-$ $+$ $-$ $+$ $-$ $-$ $+$ $+$ $-$ $-$ $+$ $+$ $+$ $-$
$+$ $-$ $+$ $+$ $-$ $-$ $-$ $-$ $+$ $-$ $+$ $-$ $+$ $-$ $+$ $+$ $-$
$-$ $-$ $+$ $-$ $+$ $+$ $+$ $-$ $-$ $-$ $-$ $-$ $-$ $-$ $+$ $-$
$+$ $-$ $-$ $-$ $+$ $+$ $-$ $+$ $+$ $+$ $+$ $+$ $+$ $-$ $-$
$-$ $+$ $+$ $-$ $+$ $-$ $-$ $+$ $+$ $+$ $+$ $+$ $-$ $+$
$-$ $+$ $-$ $-$ $-$ $+$ $-$ $+$ $+$ $+$ $+$ $-$ $-$
$-$ $-$ $+$ $+$ $-$ $-$ $-$ $+$ $+$ $+$ $-$ $+$
$+$ $-$ $+$ $-$ $+$ $+$ $-$ $+$ $+$ $-$ $-$
$-$ $-$ $-$ $-$ $+$ $-$ $-$ $+$ $-$ $+$
$+$ $+$ $+$ $-$ $-$ $+$ $-$ $-$ $-$
$+$ $+$ $-$ $+$ $-$ $-$ $+$ $+$
$+$ $-$ $-$ $-$ $+$ $-$ $+$
$-$ $+$ $+$ $-$ $-$ $-$
$-$ $+$ $-$ $+$ $+$
$-$ $-$ $-$ $+$
$+$ $+$ $-$
$+$ $-$
$-$

Harborth的論文完整的證出來, 當 $n=0$ 或 3 (mod 4) 時, 含有一半正號及一半負號的三角形確實存在。我的故事就是從讀了這一篇文章開始。 當時我給了自己一個更一般的問題: 給定正整數 $n$, 在所有 $2^{n}$ 個 $n$ 階Steinhaus三角形中, 正號的個數的可能值有那些?

為了方便, 我用0和1分別代表正號和負號, 則Steinhaus原來 $n=7$ 時的答案可以變成

$0$ $0$ $1$ $0$ $1$ $0$ $0$
$0$ $1$ $1$ $1$ $1$ $0$
$1$ $0$ $0$ $0$ $1$
$1$ $0$ $0$ $1$
$1$ $0$ $1$
$1$ $1$
$0$

如果我們規定 $\{0,1\}$ 上的加法為: $0+0=1+1=0$ 及 $0+1=1+0=1$, 則每一個不在第一列的位置的數等於其上方兩個數的和。 因為三角形可以完全被它的第一列 $a_{1}a_{2}\ldots a_{n}$ 決定, 我們用 $T(a_{1}a_{2}\ldots a_{n})$ 代表這個三角形, 而用 $\#T(a_{1}a_{2}\ldots a_{n})$ 表示這個三角形中1的個數。 在這樣的符號下, 我想要求的是 $$ S(n) = \{\#T(a_{1}a_{2}\ldots a_{n}) : \hbox{ 各個 } a_{i} \hbox{ 為0或1 }\}. $$

有了問題, 我就著手去計算, 很容易可以算出前幾個 $S(n)$, 例如: \begin{eqnarray*} S(1) &=& \{0, 1\}, \\ S(2) &=& \{0, 2\}, \\ S(3) &=& \{0, 3, 4\}, \\ S(4) &=& \{0, 4, 5, 6, 7\}, \\ S(5) &=& \{0, 5, 6, 7, 8, 9, 10\}. \end{eqnarray*} 但是當 $n$ 越來越大時, $2^{n}$ 快速增大, 一個不小心, 只要有一點小地方出差錯, 整個 $S(n)$ 就有問題。於是我就想到用電腦來幫忙計算。

那個年代的電腦並不像現在這麼普及, 速度也不如現在的快, 記憶容量相對很小。 我學電腦是大學二年級的事情, 我大學考進中央大學物理系, 第二年轉數學系, 但還是常常回「娘家」找物理系的同學。 那時候中央大學並沒有電腦, 物理系請了附近電信研究所的一位研究人員, 每週一次的一個晚上來系上三小時課, 教導電腦程式, 我就隨著他們去學。 那時候學的是IBM 1130的FORTRAN, 顧名思義FORTRAN就是FORmula TRANslation, 一行一行看起來就像數學式子, 一點也不難。 因為中央大學沒有電腦, 我們寫程式只能寫在coding sheet上, 老師將它收回, 請人幫忙打成卡片、上機操作、在報表紙上印出答案, 我們得到報表紙, 如果有錯, 在上面改一改, 再請老師帶回去改卡片重跑程式。一學期下來, 只做了兩道程式習題。 這樣的學習實在心有不甘, 暑假時就到臺大電機系辦的暑期電腦班上課, 學了不少東西, 更重要的是, 可以自己去打卡片, 用老師發的control card　去上機, 一兩天就可以看到答案。 除了班上的習題, 還自己寫了不少數學相關程式, 玩得不亦樂乎。 我大四的時候考上臺大數學研究所及交大計算機研究所, 由於不能決定要讀什麼, 而且也想早點出國念書,所以就決定先去當兵, 也由於這層原因, 對電腦的熱愛一直平行於對數學的喜歡。

話說回來, 當時在中研院數學所並沒有什麼人用電腦, 唯一的一臺PDP8在現在看來是老古董, 這一點從開機的方法就看得出來。 首先, 將電源打開, 在電腦上用手按一連串的鍵, 取出一卷打孔的紙帶系統程式, 電腦讀入之後才會開機。

雖然這臺老古董電腦跟現在的電腦遠不能比, 但是在當時卻是數學所唯一的寶貝, 我就想用它來實現我計算 $S(n)$ 的美夢。總算它比我用手去算好太多了。 不過算來算去, 到了 $n=12$ 就是當時我能做的極限, 雖然可以看出一些現象, 但還是不夠。 我把這個煩惱向華洋博士訴苦, 他說在臺北市區的大陸大樓有一臺CDC的大電腦, 就帶我去卡油用看看。

我把程式交給CDC的工程師帶進去跑, 過了一陣子, 他們跑出來問我是不是程式寫錯了, 怎麼跑了一千多秒還未停。我的程式當然不會停, 因為我是讓 $n$ 一直往上加, 盡量的去算, 這一次, 他們幫我算到 $n=20$ 就把程式停下來。 (在撰寫本文的同時, 我再寫了一次程式, 在臺大數學系的電腦系統, 很輕易的就跑到 $n=25$ 的結果, 今日電腦的進步實非昔比。) 以下就是那時CDC幫忙印出來的結果。

CDC的電腦幫忙算出來的這些資料, 呈現了許多規則, 讓我挑幾個來說一說。

首先, $\#T_{n}(\overline 0)=0$, 其中 $n$ 用來表示第一列的長度, $\overline 0$ 是循環節為0的意思。 其次, $\#T_{n}(\overline 1)=\#T_{n}(1\overline 0)=n$。 因此, $S(n)$ 含有0和 $n$, 這是比較容易看出來的。 比較特別的是0和 $n$ 之間的其他正整數都不在 $S(n)$ 中。 直觀來說, 有一個1就會和旁邊的0產生另一個1, 進而繼續產生下一個1 $\ldots$, 所以, 有1就最少有 $n$ 個1是可以預期的。 事實上, 相信了這樣的結論, 利用數學歸納法就可以證明:

定理1. 若 $\#T_{n}\gt 0$, 則 $\#T_{n}\ge n$。 進一步, $\#T_{n}=n$ 的充要條件是 $T_{n}=T_{n}(\overline 1)$、 $T_{n}(1\overline 0)$、 $T_{n}(\overline {0}1)$、 或 $T_{3}(010)$。

$S(n)$的最小元素為0, 再來就是 $n$, 接下來的第三個是什麼? 這在略大一點的 $n$ 就可看出一個端倪, 似乎是再增加 $n/2$ 左右。 事實上, 確實有 \begin{eqnarray*} && \#T_{n}(\overline {01}) = \#T_{n}(01\overline 0) = n-1 + \lfloor n/2\rfloor, \\ && \#T_{n}(\overline {10}) = \#T_{n}(11\overline 0) = n-1 + \lceil n/2\rceil. \end{eqnarray*} 複雜一點的推演可以得到:

定理2. 若 $\#T_{n}\gt n\ge 4$, 則 $\#T_{n}\ge n-1+\lfloor n/2 \rfloor$。 進一步, $\#T_{n}=n-1+\lfloor n/2 \rfloor$ 若且唯若 $T_{n}=T_{n}(\overline {0}1)$、 $T_{n}(01\overline {0})$、 $T_{n}(\overline {10})$ 而 $n$ 為偶數、 $T_{n}(11\overline {0})$ 而 $n$ 為偶數、 $T_{n}(\overline {0}11)$ 而 $n$ 為偶數、 $T_{6}(001100)$、 $T_{6}(001000)$、 或 $T_{7}(0001000)$。

接下來的一些數和下面這些例子有關。 為了方便, 我們定義;當 $n\equiv i\,(\hbox{mod} 4)$ 時 $f(i,n)$ $=1$, 否則 $f(i,n)=0$。 \begin{eqnarray*} \#T_{n}(\overline {1100}) &=& \#T_{n}(101\overline {0}) = 2n - 2 - f(0, n), \\ \#T_{n}(\overline {0110}) &=& \#T_{n}(011\overline {0}) = 2n - 2 - f(1, n), \\ \#T_{n}(\overline {1001}) &=& \#T_{n}(111\overline {0}) = 2n - 2 - f(3, n), \\ \#T_{n}(\overline {0011}) &=& \#T_{n}(001\overline {0}) = 2n - 3 - f(2, n), \\ \#T_{n}(0\overline {1}) &=& \#T_{n}(1\overline {0}1) = 2n - 2, \\ \#T_{n}(0\overline {01}) &=& \#T_{n}(00\overline {1}) = 2n - 5 + \lceil n/2 \rceil, \\ \#T_{n}(1\overline {10}) &=& \#T_{n}(10\overline {1}) = 2n - 3 + \lfloor n/2 \rfloor, \\ \#T_{n}(\overline {011}) &=& \lfloor (n^{2}+n)/3 \rfloor, \\ \#T_{n}(\overline {110}) &=& \#T_{n}(\overline {101}) = \lfloor (n^{2}+n+1)/3 \rfloor. \end{eqnarray*}

從實驗出來的數據, 大概指向, $S(n)$ 從0開始, 跳到 $n$, 再跳到大約 $3n/2$ 附近, 再跳到 $2n$ 附近。 而從最大的值來看, 一致指向 $\lfloor (n^{2}+n+1)/3 \rfloor$, 這大約是0和1總個數的三分之二。 這三分之二約略可以由相鄰兩個1的下方要有一個0看出來, 但是仔細的證明是須要的。

另外一個有趣的資訊是, 在 $n=6$ 和14時 $S(n)$ 只含偶數, 看起來這應該也不是單一現象, 可以期待的是 $n=2^{k}-2$ 時 $S(n)$ 只含偶數。

以上種種, 後來我曾寫了一篇文章叫Binary triangles, 替我的數學實驗做了一個小總結。 這也是我日後一直深信「數學需要實驗, 而電腦是極有效的數學實驗工具」的起源。

以上講來, 有如白髮宮女話當年, 而當年其實並沒有把 $S(n)$ 完全說清楚, 還留下大一段尾巴。

事隔三十年, 現在看到電腦能幫我們做的事情越來越多。 而我自己最初寄情於數學與電腦, 最後念的是介於中間的運籌學(Operations Research), 論文寫的是圖論演算法, 做的是跨領域的研究, 一直留在數學系工作, 但也和資訊系許多做理論計算機科學的同仁熟識, 幫忙資訊系指導過一些研究生。

偶爾, 心中還是會閃過一個念頭, 希望有朝一日, 我們的高中生可以有一堂課是用電腦當工具來做數學實驗。 聽說, 新的高中課程綱要將加入資訊課, 一則以喜, 一則還是不滿意。 喜的是, 這麼重要的工具終於可以堂堂進入高中課程; 不滿意的是, 資訊課據說被歸入「生活類」, 個人衷心的希望電腦不要只是被用來聊天、打電動的家電用品, 這樣實在太委曲它了。 盼望我們的數學老師和資訊老師能合作, 互相幫忙、各蒙其利。

---本文作者任教於臺灣大學數學系---