46404 九九文教基金會的 2018 TRML 思考賽
九九文教基金會的 2018 TRML 思考賽
張鎮華, 　 2022年 12月(184) PDF

1. 古代人結繩記事

人類的計算行為比文字的發明更早, 計算之後就需要有記錄。 從史前時代開始, 人們就在木頭、 骨頭或石頭上使用計數的符號。 公元前 8000 年至前 3500 年之間, 蘇美爾人將各種形狀的粘土記號像珠子一樣串在一起, 用以保留數字的信息。 中國古代則是採用算籌來記數。羅馬帝國使用臘、紙草、和石頭上的割符, 大致上遵從希臘人將字母對應不同數的習慣。 印加帝國採用「奇普」 (quipu), 也就是一種打結的帶顏色的繩子來記數, 下圖就是一個範例。

2. 現代的位址計數系統

當一個族群的社會活動複雜到某種程度之後, 就需要比較精確地記錄數量和語言。 於是有一些古老文明就創造了文字來記錄語言, 其中記錄數量的文字, 便是數字。 各種數字系統發展到後來大多是採用進位制, 也就是有一個基數, 某個位址累積到這個基數, 就進位到在左邊的位址, 這種方法使得計算更容易而有效, 也因此, 很自然地被所有文化接納吸收。阿拉伯數字的「十進位記數系統」是現在世界各地共同使用的系統, 世界各地國民小學教導的數學內容, 有很大一部分就是為此奠定基礎。

除了十進位制度之外, 各種文明還有許多種不同的進位系統, 其中也有現在還常使用的系統, 例如時間和角度的六十進位制, 台灣民間常用的一斤為十六兩, 英制的十二進位制, 以及一些西方語言還可以看到痕跡的二十進位制。

二進位制則和電腦的發展有關。 計算數字既然是人類的需求, 發展快速計算的工具遂成為人們的渴望, 例如算盤、 計算鐘、 計算尺、 計算器、 電腦等的發明。 早期的電腦以十進位為基礎, 1940 年代 von Neumann 以不藏私的胸懷, 公布他設計的電腦架構, 建議採用二進位編碼、 儲存程序原理等, 各家競相採用, 使得電腦的建構快速發展, 如今已經成為人類生活不可或缺的工具。 二進位制相關的研究逐漸受到重視, 人們也開始累積出許多相關的知識。

本文要討論一個關於二進位制的題目, 是 2018 年 TRML 的思考賽試題, 很具挑戰性。 TRML 是九九文教基金會主辦的一個高中數學競賽, 下面先介紹這個基金會。 而這個題組的設計, 源自國際數學奧林匹亞競賽 (IMO) 1 1 International Mathematical Olympiad. 的一道試題, 我們也將趁機介紹 IMO, 以及我國參與情況。

3. 九九文教基金會

1998 年 12 月, 多位國內外知名大學教授及資深高中老師, 共同籌設成立「財團法人九九文教基金會」, 主要以辦理文教交流、文化教育學術專題研究、 培育獎助文教人才、推動各項文教公益活動為宗旨。

根據以上宗旨, 九九文教基金會主要活動有團隊競賽。 例如, 早期甄選、培訓、帶領台灣代表隊, 參加每年在美國舉辦的高中ARML 2 2 ARML (The American Regions Mathematics League) 是一個著名的美國高中數學團隊競賽, 每年於四個地點同步舉辦： 愛荷華大學、賓州州立大學、內華達大學拉斯維加斯分校、阿拉巴馬大學亨茨維爾分校, 過去還曾經包括聖荷西州立大學、羅格斯大學、杜克大學。 ARML 是一個極富盛名的數學競試, 堪稱世界級。 每一團隊包括 15 位學生, 來自美國各著名的高中。 參加的團隊踴躍, 以 2014 年為例, 約有 2000 位學生參加。 經由內華達大學拉斯維加斯分校的薛昭雄教授介紹, 何焱銘老師於 1998 年 6 月帶領台灣學生參加 ARML, 返台後開始籌組成立九九文教基金會。 1999 年開始, 由九九文教基金會負責甄選、培訓、帶團工作, 帶領台灣學生參加 ARML, 一直到 2009 年開始未再舉辦此項活動, 專心於 TRML 的業務。 數學競賽。 但是出國比賽畢竟只有少數人能參與, 為嘉惠台灣許多愛好數學的學生, 九九文教基金會效仿 ARML 的做法, 從 1999 年開始, 每年八月份第三個星期六、日, 在臺北舉辦台灣區高中 TRML 3 3 The Taiwan Regions Mathematics League. 數學競賽。 活動極盛時期, 某年參與隊伍曾達到 367 隊, 一隊 15 人, 總人數達到 5505 人 4 4 1999 年至 2021 年, TRML 舉辨過 23 屆, 總共有 5716 隊、 85740 人次參賽。 ； 美國 ARML 主席來參觀時, 瞠目結舌, 嘆為奇觀。 從 2005 年起, 為避免遠道學生舟車勞頓, 遂將競賽分臺北、臺中、高雄三區舉辦, 每年的總隊數也都是三百餘隊、 四千多人。 因為 TRML 的成功經驗, 應要求於 2003 年起, 每年十二月第三個星期六, 舉辦國中 JHMC 5 5 Junior High School Mathematics Competition. 數學競賽, 分臺北、新竹、臺中、臺南、高雄、花蓮六區舉行。

另外, 九九文教基會亦承辦, 全美中學數學分級能力測驗 (AMC8、 AMC10、 AMC12) 6 6 American Mathematics Competitions. 的臺灣區試務工作, 並分析結果提供相關單位參考。 自 2017 年起, 為契合臺灣自己的數學課程綱要, 主辦臺灣中小學數學能力檢定考試 (TMT8、 TMT10、 TMT11A、 TMT11B) 7 7 Taiwan Mathematics Test. 。

以上這些競賽、測驗、檢定考試的結果, 均已經被納入大學推甄的參考資料。

TRML 競賽分兩天舉行, 包含團體賽、思考賽、個人賽、接力賽等四項。

團體賽與思考賽均由全隊 15 人共同討論作答, 僅須交出一份答案卷。

個人賽則由每個人單獨作答, 其得分除了計入團隊總分外, 亦分別計算個人分數, 所以除了團體獎牌以外, 還有個人獎牌。 如果有多人同時達到個人賽的最高分, 為選出金牌獎得主, 這些人就要參加同分賽, 他們在頒獎的大舞臺同步解題, 最先 (快)得到正確答案的人勝出, 比賽常常十分緊張。

接力賽最為刺激, 所有團隊聚於頒獎大禮堂。 每隊的 15 人分 5 組, 每組 3 人。 比賽分 2 回合。 每一回合, 每一組中的三人都會拿到不同的題目, 第二位與第三位同學的試題中皆會有一未知數 $T$, 這個 $T$ 為前一位同學解出的答案, 因此理論上第二位 (第三位) 同學要等到前一位學生將答案傳給他後才能作答, 但有些人會先把 $T$ 當作變數算出答案, 等接到前一位同學傳來的答案, 再代入計算得到真正的結果。 整組答對與否由第三人的答案來決定。 考試會有兩次繳卷的機會, 第一次就繳卷且答對的組別分數較高； 考試時間到了之後, 所有答案卷就會被收回。 接著, 主席臺的主持人會宣布答案, 請答對的組別舉手, 此時歡呼聲由答對的各組傳出, 十分熱烈。

2020年至2022年之間因新冠肺炎 (COVID-19)疫情的影響, 競賽內容分團體賽、思考賽、個人賽等三項, 於一天內進行, 少了接力賽和同分賽的樂趣。

4. 國際數學奧林匹亞競賽

從 1904 年起, 國際奧林匹亞委員會開始主辦夏季奧林匹亞運動會 (Summer Olympic Games或Games of the Olympiad), 這是一個每四年舉辦一次的國際性運動盛會。

1934 年和 1935 年, 前蘇聯率先分別在其國內的列寧格勒和莫斯科舉辦中學數學競賽, 並且把這種數學競賽和體育競賽相提並論, 冠以「數學奧林匹亞」的名稱, 形象地揭示選手間智力較量的過程。 由此開始, 「奧林匹亞」被廣泛地應用在各種競賽的名稱中。

1959 年, 第一屆國際數學奧林匹亞 (International Mathematical Olympiad, 簡稱 IMO) 在東歐的羅馬尼亞舉行, 當時參賽的只有 7 個東歐國家。 自此以後, 除了 1980 年以外, IMO 每年舉辦從未中斷。 隨著 IMO 影響力的不斷擴大, 參賽的國家也不斷增多, 這幾年已經超過 100 個, 基本上包含了中學數學教育水準比較高的國家。 目前每個參賽國家都可以派出最多 6 位參賽選手、一名領隊、一名副領隊和觀察員。 參賽者必須在比賽時未滿 20 周歲, 最高學歷為中學, 不過每位選手參加 IMO 的次數沒有限制。

從 1983 年的第 24 屆開始, IMO 試卷由 6 道題目組成, 每題可得 7 分, 全卷滿分 42 分。 比賽分兩天進行, 每天參賽者有四個半小時來解決 3 道問題 (由上午 9 時到下午 1 時 30 分)。 通常每天的第一道題 (即第 1、 4 題) 最簡單, 第二道題 (即第 2、 5 題)難度中等, 第三道題 (即第 3、 6題) 最困難。 題目的範圍一般分為代數、幾何、數論和組合數學四大類。 要理解 IMO 題目的意思, 不需要超出公認的中學數學課程範圍的知識, 但是要解出題目卻需要創新的巧思, 這通常不是在中學數學課程能學到的, 但是又不屬於大學課程的知識。 一般來說, IMO 題目的難度較大, 靈活性強, 富於智巧。 要解決這些問題, 一般不需要參賽者具有高等數學知識 (例如微積分), 但需要參賽者有正確的思維方式, 良好的數學素養和基本功, 堅韌的毅力以及一定的創造性。 原則上, IMO 不鼓勵選手利用超出中學範疇的數學知識與工具解決問題 (但並沒有明確限制), 並會在確定題目時充分考量這點。

1991 年 2 月教育部接獲第 32 屆國際數學奧林匹亞主辦國瑞典邀請, 參與第32屆競賽之觀察國。 1992 年首次參加由俄羅斯主辦之第 33 屆競賽, 名列 17。 1993 年前往土耳其參加第 34 屆之競賽, 獲得 1 金、 4 銀、 1 銅, 名列第 5。 1998 年我國在台北舉辦第 39 屆國際數學奧林匹亞競賽, 因為籌辦周全, 深獲世界各國讚賞。

繼國際數學奧林匹亞競賽於 1959 年開始之後, 各種科學學科亦相繼開始舉辦相關學科的國際奧林匹亞競賽, 例如國際物理奧林匹亞 (IPhO) 於 1967 年開始、 國際化學奧林匹亞 (IChO) 於 1968 年開始、 國際資訊奧林匹亞 (IOI) 於 1989 年開始、國際生物奧林匹亞 (IBO) 於 1990 年開始、 國際哲學奧林匹亞 (IPO) 於 1993 年開始、國際天文奧林匹亞 (IAO) 於 1996 年開始、國際地理奧林匹亞 (IGeO) 於 1996 年開始、 國際語言學奧林匹亞 (IOL) 於 2003 年開始、國際國中科學奧林匹亞 (IJSO) 於 2004 年開始、國際地球科學奧林匹亞 (IESO) 於 2007 年開始、 國際天文和天體物理學奧林匹亞競賽 (IOAA) 於 2007 年開始。

5. 1994年第三十五屆國際數學奧林匹亞競試試題第3題

我們要討論的 TRML 思考賽題目源自 1994 年 IMO 第 3 題, 題目如下所述。 第 3 題就是第一天最難的一題。 這一年的 IMO 在香港舉行, 我國得到第 13 名。

3. 對於任意正整數 $k$, $f(k)$ 表示集合 $\{k+1,k+2,\ldots ,2k\}$ 內的每一個元素用二進位表示後恰有 3 個 1 的元素之個數。

(a) 試證明對於每一正整數 $m$, 至少存在一個正整數 $k$, 使得 $f(k)=m$。

(b) 試確定所有正整數 $m$： 對這樣的 $m$ 恰有一個數 $k$ 使得 $f(k)=m$。

參考解答： 為了方便, 用 $S(k)$ 表示集合 $\{k+1,k+2,\ldots ,2k\}$。 則 $f(k)$ 表示集合 $S(k)$ 內用二進位表示後恰有 3 個 1 的元素之個數。

(a) 首先 $f(4)=1$, 因為 $S(4)=\{5,6,7,8\}$, 而 $5=2^2+2^0$、 $6=2^2+2^1$、 $7=2^2+2^1+2^0$、 $8=2^3$, 所以 $S(4)$ 中只有 7 的二進位表示恰有 3 個 1。

其次, $S(k)$ 和 $S(k+1)$ 的差別是, $S(k)$ 有一個數 $k+1$ 不在 $S(k+1)$ 中, 而 $S(k+1)$ 有二個數 $2k+1,2k+2$ 不在 $S(k)$ 中。 因為 $2k+2$ 的二進位表示正好是 $k+1$ 的二進位表示的右邊加一個 0, 所以 $k+1$ 的二進位表示恰有 3 個 1、 若且唯若 $2k+2$ 的二進位表示恰有 3 個 1。 另一方面, $2k+1$ 的二進位表示可能恰有 3 個 1, 也可能不是。 歸結到

$$f(k)\le f(k+1)\le f(k)+1,$$

因此, 當 $k$ 的值由 $4, 5, 6,\ldots $ 往上增加時, $f(k)$ 的值就會由 $f(4)=1$ 開始, 有時保持不變, 有時增加 1, 產生所有可能的正整數 $1, 2, 3,\ldots$。 也就是, 對於所有正整數 $m$, 恰有一個正整數 $k$ 使得 $f(k)=m$。

(b) 如果 $m$ 滿足恰有一個數 $k$ 使得 $f(k)=m$, 則由前面的討論可以知道 $f(k-1)\lt f(k)\lt f(k+1)$ 且 $2k-1$ 和 $2k+1$ 的二進位表示都恰有 3 個 1。

此時 $2k$ 及 $k$ 的二進位表示都恰有 2 個 1, 所以 $k=2^r+2^s$ 其中 $r\gt s\ge 0$。 又因為 $2k+1=2^{r+1}+2^{s+1}+2^0$ 及 $2k-1=2^{r+1}+(2^{s+1}-2)+2^0$, 所以只能有 $s=1$、 $2^{s+1}-2=2^1$。 因為 $k+1=2^r+2^1+2^0$、 $2k=2^{r+1}+2^2$, 所以 $S(k)$ 的元素的二進位表示可能有 $r+1$ 位或 $r+2$ 位； 其中恰有 3 個 1 的第一種情況有 ${r \choose 2}$ 個, 形如 $2^r+2^i+2^j$ 中 $r\gt i\gt j\ge 0$； 第二種情況則只有一個 $2^r+2^1+2^0$。 綜合而言, $m={r \choose 2}+1$ 其中 $r\ge 2$。

$\Box$

這是一道有趣而具挑戰的題目。 我們於是想要了解更一般的情況, 例如, 如果把「二進位表示後恰有 3 個 1 的元素之個數」換成「二進位表示後恰有 $i$ 個 1 的元素之個數」, 那會是什麼情況呢？ 又如果把「二進位」換成其他進位制, 會有何變化？ 這就是 2018 TRML 思考賽的源頭。

6. 九九文教基金會的 2018 TRML 思考賽

2018 年 TRML 思考賽把 1994 年 IMO 第 3 題往前推進。 因為 TRML 的對象不都是像 IMO 參賽者那樣特別聰明的小孩, 所以雖然把問題更一般化, 但卻不能出得過難, 而且要有引導過程, 以便在一般學生的能力範圍內, 既能引起他們的興趣, 也能有引領他們思考的機會。 在這兩方面的考量下, 題目如下, 共有 2 頁, 包括一些實驗數據, 提供學生觀察的機會。 要說明的是, TRML 的 $f_3 (k)$ 和 IMO 的 $f(k)$ 略有不同, 但其大方向的性質一樣。 我們的調整是為了推導的方便。

TRML 思考賽-2018

思考賽共 12 題, 每題均為 6 分。 答題時必須寫明計算或證明過程, 為得到滿分, 答題方式必須合理, 層次清楚簡明。 前面小題縱使未被證出, 也可被引用來解後面小題；但反之後面小題的結果, 未正確證明之前不可用來解前面小題。 繳交的答案紙每張至多一小題, 且必須在每張答案紙上方標明題號且依序排列。 每張紙上只寫一面, 不要寫兩面。

准考編號已由大會直接印於答案紙上, 在繳交的答案卷上, 不可用其他方式表明隊伍的身份。

一個正整數 $n$ 可以唯一寫成 $n=a_r2^r+a_{r-1}w^{r-1}+\cdots+a_12^1+a_02^0$、 其中各 $a_j=\{0,1\}$ 而 $a_r=1$, 稱 $(a_ra_{r-1}\ldots a_1a_0)_2$ 是 $n$ 的二進位表示法； 0 的二進位表示法是 $(0)_2$。 用 $b(n)$ 表示 $n$ 的二進位表示法中 1 的個數； 例如, 因為 $23=1\cdot 2^4+0\cdot 2^3+1\cdot 2^2+1\cdot 2^1+1\cdot 2^0=(10111)_2$, 所以 $b(23)=4$； 再如, 因為 $0=(0)_2$, 所以 $b(n)=0$。 對於非負整數 $i$ 和 $m$, 令

\begin{align*} \hbox{集合}\, F_i(m)\!=\!\{n:m\!\le\! n\!\le\! 2m\!-\!1, b(n)\!=\!i\}\hbox{、而其大小 (元素個數)為}\ f_i(m)\!=\!|F_i(m)|\hbox{。} \end{align*}

由定義, 對任意非負整數 $i$ 和 $m$ 有 $f_i(0)=f_0(m)=0$。 因為 $1=(1)_2$、 $2=(10)_2$、 $3=(11)_2$、 $4=(100)_2$、 $5=(101)_2$, 所以 $b(1)=b_(2)=b(4)=1$、 $b(3)=b(5)=2$, 遂有 $F_1(1)=\{1\}$、 $F_1(2)=\{2\}$、 $F_2(2)=\{3\}$、 $F_1(3)=\{4\}$、 $F_2(3)=\{3,5\}$, 以及 $f_1(1)=f_1(2)=f_2(3)=1$、 $f_2(1)=0$、 $f_2(2)=1$、 $f_2(3)=2$。 請參考下頁一些 $f_i(m)$ 的值, 或許有助於看出一些題目的答案。

1. 將 39 寫成二進位表示法, 並求 $b(39)$ 之值。 需如同上述說明一樣地顯示計算過程。

2. 試求集合 $F_2 (10)$ 並說明其大小 $f_2(10)=4$。需如同上述說明一樣地顯示計算過程。

3. 試求集合 $F_1(107)$ 及其大小 $f_1(107)$ 之值。 需顯示計算過程。

4. 是否存在一個正整數 $m$ 使得 $f_1(m)=107$。 需說明理由。

5. 試求集合 $F_3(2^6)$ 及其大小 $f_3(2^6)$ 之值, 需顯示計算過程。

6. 對所有非負整數 $i$ 和 $r$, 請說明 $f_i(2^r)=C_{i-1}^r$。並求 $f_i(2^r+1)$, 需顯示計算過程。

7. 對所有非負整數 $i$ 和 $m$, 試證明 $f_i(m)\le f_i(m+1)\le f_i(m)+1$。

8. 對所有正整數 $m$, 試求 $f_2(m)$ 之值。 需顯示計算過程。

9. 是否存在一正整數 $m$ 使得 $f_3(m)=107$？ 需說明理由。

10. 對所有正整數 $i$ 和非負整數 $m$, 試證明 $f_i(2m)=f_{i-1}(m)+f_i(m)$。

11. 對所有正整數 $i$ 和非負整數 $m$, 試證明 $f_i(2m+1)=f_{i-1}(m)+f_i(m)+\delta_{i-1,b(m)}$, 其中, 當 $i-1\not=b(m)$ 時 $\delta_{i-1,b(m)}=0$,當 $i-1=b(m)$ 時 $\delta_{i-1,b(m)}=1$。

12. 當 $r\!\ge\! 2$ 時, 試決定最小的$m_r$及最大的 $m'_r$ 使得 $f_3(m_r)\!=\!f_3(2^r)\!=\!f_3(m'_r)$。 需說明理由。

$f_i (m)$$i=0$$i=1$$i=2$$i=3$$i=4$$i=5$$i=6$
$m=\phantom{0}0=(000000)_2$0000000
$m=\phantom{0}1=(000001)_2$0100000
$m=\phantom{0}2=(000010)_2$0110000
$m=\phantom{0}3=(000011)_2$0120000
$m=\phantom{0}4=(000100)_2$0121000
$m=\phantom{0}5=(000101)_2$0131000
$m=\phantom{0}6=(000110)_2$0132000
$m=\phantom{0}7=(000111)_2$0133000
$m=\phantom{0}8=(001000)_2$0133100
$m=\phantom{0}9=(001001)_2$0143100
$m=10=(001010)_2$0144100
$m=11=(001011)_2$0145100
$m=12=(001100)_2$0145200
$m=13=(001101)_2$0146200
$m=14=(001110)_2$0146300
$m=15=(001111)_2$0146400
$m=16=(010000)_2$0146410
$m=17=(010001)_2$0156410
$m=18=(010010)_2$0157410
$m=19=(010011)_2$0158410
$m=20=(010100)_2$0158510
$m=21=(010101)_2$0159510
$m=22=(010110)_2$0159610
$m=23=(010111)_2$0159710
$m=24=(011000)_2$0159720
$m=25=(011001)_2$01510720
$m=26=(011010)_2$01510820
$m=27=(011011)_2$01510920
$m=28=(011100)_2$01510930
$m=29=(011101)_2$015101030
$m=30=(011110)_2$015101040
$m=31=(011111)_2$015101050
$m=32=(100000)_2$015101051
$m=33=(100001)_2$016101051
$m=34=(100010)_2$016111051
$m=35=(100011)_2$016121051

註：請觀察此表, 或許有助於看出一些題目的答案。

雖然我們的目標是要引導學生求出一般的 $f_i (m)$, 但誠如前面所說, TRML 是要引導一般學生思考, 希望能引起他們的興趣, 不是要出難題為難學生, 所以會有第 1 題、 第 2 題那樣的「送分題」。

試題中第 7 題的性質, 在 IMO 的解題 (a) 是一個關鍵。 第 11 題和第 12 題的遞迴關係, 是要引導通往一般解的道路。 但是因為考試時間的限制, 題組的設計止於 $f_3 (m)$。 出題的用意及最後期盼是, 有興趣的學生, 競賽結束之後, 有機會自己挑戰自己, 試著算出 $f_i (m)$ 的一般解。

本文並不打算公布 $f_i (m)$ 答案, 而是要向有興趣的讀者挑戰, 這個答案到底為何？ 甚至, 如果把問題推到一般的進位, 又會如何？

本文作者為臺灣大學數學系名譽教授