可數性（countability）

大家知道，如果一個集的元素可以和正整數集 N 的元素一一對應的話，那麼這個集稱為可數的（countable）。例如：整數集 Z 是可數的，因為它可以和 N 作一一對應：

1←→0、2←→1、3←→ -1、4←→2、5←→ -2、6←→3、7←→ -3、……

換句話說，如果一個集的所有元素可以「順序列出來」，則它是可數的：

0、1、-1、2、-2、3、-3、……

以下是兩個「證明」，大家看看有甚麼問題：

(1) 0 和 1 之間的所有實數（不包括 0 和 1）是可數的

證明：我們只需把 0 和 1 之間的所有實數「順序列出來」即可：

0.1, 0.2, 0.3, ..., 0.9, 0.01, 0.02, ..., 0.99, 0.001, 0.002, ..., 0.999, 0.0001, ...

(2) 所有以整數為系數的多項式是不可數的

證明：假設所有以整數為系數的多項式是可數的，則存在一一對應

1 ←→ a₁₀ + a₁₁x + a₁₂x² + a₁₃x³ + ...
2 ←→ a₂₀ + a₂₁x + a₂₂x² + a₂₃x³ + ...
3 ←→ a₃₀ + a₃₁x + a₃₂x² + a₃₃x³ + ...
4 ←→ a₄₀ + a₄₁x + a₄₂x² + a₄₃x³ + ...
......

考慮 f(x) = (a₁₀+1) + (a₂₁+1)x + (a₃₂+1)x² + (a₄₃+1)x³ + ...，則顯然 f(x) 不等於以上任何一個多項式，這跟一一對應的意義矛盾，因此所有以整數為系數的多項式是不可數的。

One Line Solution?

最近在科大圖書館找一些關於Combinatorial Algorithms的書時，無意中見到兩本同系列的書，書名非常吸引。作者是A.M. Yaglom和I.M. Yaglom（兩兄弟？父子？），書名是"Challenging Mathematical Problems With Elementary Solutions"，有Volume 1和Volume 2。書內的Preface說，這本書是翻譯自俄羅斯一本著名的problem book，名叫"Non-Elementary Problems in an Elementary Exposition"。

這個時候，當然又是給大家想想書中問題的時間了。

如果大家有玩過國際象棋的話，一定知道有一種棋叫"bishops"，它只可以打斜行，但行多少格都可以。試證明在國際象棋的 8 x 8 棋盤內放下 k 隻 bishop（k可以是0；不放任何bishops在這裏被視為一種方法）而這些bishops互不攻擊的方法的數目是一個平方數。

English Version: A bishop can moves diagonally only in the chessboard; but the number of boxes it move is not restricted. Prove that on the 8 x 8 chessboard, the number of different arrangements of k bishops (k can be 0; not placing any bishop is also considered as a arrangement here) such that no bishop controls a square on which another lies.

Mission Impossible?

哈，今日又聽到一條看似"mission impossible"的問題。我想這題用英文會好理解一點：

There is a submarine which is located at some integer point on the real axis at the 0th second. It moves with uniform velocity k units / sec, where k is an integer (possibly negative). As the submarine is deep under the water, you cannot see it. Every second you are allowed to fire a missile at some integer point. Find a way to fire the missiles so that you are guaranteed to fire at the submarine.

帽子問題

最近玩了兩題「帽子問題」，跟大家分享一下：

1. 有 10 個人排了一條隊，每人頭上都有一頂黑色或者白色帽子。每個人只可以看到排自己前面的人所穿帽子的顏色，而且他們均不能看到自己帽子的顏色。
   
   現在有一個公証人，他會向每個人問一條問題：「你自己的帽子是甚麼顏色？」他會順序由排最後的人問到排最前的人。每個人只可以回答：「黑色」或「白色」，而每個人回答時，其他人都是可以聽到他的答案的。
   
   這 10 個人可以事先商量怎樣回答，以確保答對的次數最多。問：他們可以確保答對多少次？怎樣可以達到？
   
   
2. 監獄裏有 n 個囚犯。有一日，皇上要跟這 n 個囚犯玩一個遊戲。皇上會選出 n 種顏色。獄長會在每一個囚犯頭上戴上一頂帽子，每頂帽子的顏色是這 n 種顏色之一。帽子的顏色並無其他限制，所以可能每個囚犯的帽子顏色都相同，亦有可能每個囚犯的帽子顏色均不同的。
   
   每個囚犯都可以看到其他囚犯的帽子，唯獨是不可以看到自己的帽子。現在，囚犯們要同一時間向獄長交一張紙，上面寫上他們猜測自己帽子的顏色。當然，這樣子就是說囚犯們不會看到其他囚犯的猜測了。
   
   皇上說如果有任何一個囚犯答對了，就釋放所有囚犯；否則，全部囚犯都要處死。這些囚犯可以事先商量怎樣回答，以確保他們一定能夠被釋放？問：他們怎樣達到目的？

如果各位有其他類似的問題提供，可以留言跟大家分享哦~~

第七屆培正數學邀請賽

由香港培正中學主辦，培正教育中心和數學資料庫協辦的第七屆培正數學邀請賽的初賽和決賽已分別訂於 2008 年 1 月 26 日（星期六）下午和 2008 年 3 月 8 日（星期六）上午舉行。有意參賽的同學，請密切留意本網誌及比賽網頁的最新消息。

Let me Break The Ice

各位MD的朋友好！

「數學資料庫手記」誕生之前，有人問：「MD 已經有Forum ，討論可在Forum 進行。為何要開一個Blog? 」

我認為這個網誌不但為MD 提供多一條康莊大道與各界人士接觸，讓各位認識我們多一些；亦為MD members 提供一個 (相比Forum) 較 informal 的吹水平台，閒時發下奴騷。多謝阿Dick (Website Management Vice) 為MD 出主意，開了這個網誌。

這個網誌會有些什麼？由於MD members 各有千秋，且題材太廣，我也預計不到。可以透露：Gigi (Academic Vice) 提議，一些海外MD members 可把在外地修讀數學的經歷加入其中。此外、MD members 亦會在這裡談及於日常生活中涉及數學的趣事。詳情大家拭目以待吧！

雖然只有MD members 可以編輯這個網誌, 但我們歡迎各位留言。我希望所有與MD 有緣的人能見證「數學資料庫手記」的誕生, 更希望能在這個Blog、Forum 、MD Seminar 或其他有關數學的場合和大家見面！