數學資料庫五歲了!!!

不經不覺，數學資料庫已經五歲了！
MD是一個以推廣數學為宗旨的網站，慶祝生日也當然要與數學拉上關係。我們很榮幸邀得香港中文大學的張婉琳小姐主持於三月十五日主持了一個學術講座，向我們的會員為「An introduction to Strong Conical Hull Intersection Property」這個題目作介紹，大家都獲益不少。
聽畢講座，也是時候輕鬆一下吧。我們到了一間位於旺角的樓上咖啡店舉行會員聚會，在歡笑聲中度過了愉快的一晚。

張小姐正為我們講解

大家都很專心呢!


MD人才濟濟! 1,2,3... 笑~


小心危樓啊

選擇公理

小弟第一次在這個blog貼文，由於小弟還是一位中學生(也是一隻「數海中的迷途小羔羊」)，如果有錯請各位不吝更正

最近在和其他人閒談時，明白了選擇公理(Axiom of Choice, AC)為甚麼不能用數學歸納法(Mathematical Induction)去證明，特意在這兒貼出來和各位像我一樣的「數海中的迷途小羔羊」分享。 :P

首先，讓我大概說一下甚麼是選擇公理，選擇公理的正式說法是：

設X是非空集合的集合。則我們可以從X中的每個集合中選擇一個元素

簡單一點來說，如果你手上有一堆集合，而且你肯定每一個集合都包含至少一個元素，那麼你一定可以在每一個集合抽一個元素出來，而不用知道每個集合的其他資訊。

說到這裏，大家可能已經在抱怨：這不是很明顯嗎？如果你有幾個籃子，每籃內都至少有一隻雞蛋，我們當然可以在每一個籃子抽一隻雞蛋吧！但是數學中一切命題都需要證明，這個也不應例外。現在大家又可能想出了以下這個證明：

1.設P(n)為命題“在n個非空集合中可以在每個集合中抽一個元素出來”；
2.考慮P(1)，我們可以在那一個非空集合中任意抽一個元素出來，故P(1)成立；
3.假設P(k)對於一些自然數k成立，考慮k+1個非空集合，由歸納假設知我們可以在頭k個集合中抽一個元素出來，而我們又可以在第k+1個中任意抽一個元素出來，故P(k+1)成立；
4.由數學歸納法原理知P(n)對一切自然數成立；
5.證明完畢。

這個也是我初次聽到選擇公理時想到的「證明」，然而，以上的「證明」有兩個大漏洞，第一個是：甚麼叫「任意抽一個元素出來」；第二個是：對一切自然數n證明了選擇公理，代表選擇公理對於一切情況成立嗎？


先說前者，「任意」這個字用於集合論之類的數學基礎時是十分含糊的，數學上不存在一個明顯的函數f(X)，可以在任何一個非空集合X中準確地抽出一個元素。例如定義f(X) = (X中最小的元素)吧，讓我們考慮X’為0至1中所有實數但不包括0和1，容易看到X’中不存在最小的元素，f(X’)沒有定義！又或者考慮一下「古今中外所有的流浪貓」或是「世界上所有曾經/現在/將會看這篇文章的人」之類的集合，你便明白是否存在所謂的選擇函數，並不是一件容易證明的事。

再說後者，使用以上的數學歸納法時，我們假設了可以把一大堆集合排成一列，或至少貼上1,2,3,…的編號。然而，我們知道自然數是一個可數(countable)的集合，但如果我們遇上一堆數目是不可數(uncountable)的集合時，數學歸納法的正確性是值得商榷的。可惜的是，這樣的一堆集合是存在的，例如把每一個正實數x對應一個集合{-x,x}並把所有集合組成一個新的集合，康托(G . Cantor)證明了，以上集合的數目是多於自然數的，即是把它們逐一加上唯一的正整數編號是不可能的。

事實上，在二十世紀中期，科恩(P . Cohen)用一種叫力迫法(forcing)的技巧，證明了選擇公理是不能用策梅羅-弗蘭克爾集合論(ZF，現代數學的基礎之一)內其他公理證明；但又由於選擇公理的表達非常明顯，很多數學證明是在它成立的前提下做的，所以我們唯有把它當成一條公理使用。

說回來，如果選擇公理已經成為公理，又是如此明顯，為甚麼我們還要花時間討論這條「公理」的正確性呢？一個很重要的原因，是如果選擇公理成立，會推出一些看似瘋狂的結果，幾個例子包括：

1. 巴拿赫-塔斯基悖論：存在一個方法，可以將一個三維實心球分成有限個部分，然後通過旋轉和平移，重新組合為兩個半徑和原來相同的完整的球；
2. 塔斯基分割圓問題：存在一個方法，可以將平面上的一個圓分割成有限多塊，然後通過平移，重新拼合成面積相同的正方形；
3. 在以下情況中，存在一個策略令只有有限個犯人不被釋放:

無窮個犯人面向數軸的正方向依次就座，第i個犯人坐在數軸上座標為i的地方，他可以看見所有座標大於i的囚犯頭頂上的帽子。每個囚犯都戴上了黑色或白色的帽子，然後每個犯人依次猜測自己頭上的帽子顏色，猜對了的予以釋放。犯人們可以事先商量，而且他們都知道自己的座位編號，但犯人們不能聽到其他人的猜測；同時，我們假設每個犯人都是聰明和有無窮記憶力的。

時間所限，有關第三個例子中的策略，我留待稍後才再討論。

升 300 點

今天恆生指數升了 300 點。本來這沒甚麼特別，不過細看之下，今天收市指數報 21384.61，昨天收市是 21084.61，上升了剛好 300.00！這當然是一個巧合，但這個巧合有多巧合呢？讓我們從數學角度分析一下。

我們希望求得這樣的情況（變幅是 100.00 的整數倍）平均多久出現一次。我們注意到，變幅的最後四位數字有 10000 個可能，分別是 00.00、00.01、…、99.99，而這 10000 個可能出現的機會大致相同（實際上是有出入的，例如如果市況牛皮而每日上落經常少於 100 點的話，那麼出現 99.99 的機會顯然較小），因此平均來說每 10000 個交易日才會出現今天的情況一次！以每年 250 個交易日（52 星期，每星期 5 日，再減去一些假期）計算，也就是說今天的情況平均是 40 年一遇的！

當然，世界上有很多不同的股市指數，因此要遇上這樣的情況大概也不用等 40 年。不過如果只計恆生指數的話，今天的情況大家在一生之中大概不會遇上很多遍呢！

循環論證 (I) --- 圓周公式

這是 ami 第一篇在手記放的貼子，題目早於一個月前決定，今天比較空閒終於有機會貼上來。

在教會教一班中學生數學時，其中有一人 X 問道以下一道問題：

X : 給出一個圓形，圓周為 ，圓面積的公式 能夠運用積分的方法來證明。

X : 那麼，請問圓形的圓周 可否運用類近的積分算式去「證明」呢？

附註：

X 提問時，特別強調證明一詞。

對定義熟悉的讀者，應該明白背後的原因吧。

與此同時，有另一位曾經修讀純數的人給出以下證明：

設 為給出圓形的圓周，設圓的圓心為 ，所以圓的方程為。

Let be the circumference of the given circle, suppose the circle center at origin, so the equation of circle is .

考慮圓形在第一象限：

Consider the first quadrant:

由弧長公式及對稱性可知 ：

By arc length integral and symmetry:

約簡後得出:

After simplification :

所以

Therefore :

究竟在「證明」中有什麼錯誤呢？

由於時間所限，留待下一篇才解答吧。

---

For reference:
Definition of Pi
Arc length forumla

造馬

歐聯八強抽籤結果鬧出造馬疑雲（可參考這篇報導），有網友「未卜先知」，在抽籤前個多小時先行公佈「內定抽籤結果」（阿仙奴對利物浦、曼聯對羅馬、車路士對費倫巴治、巴塞隆拿對史浩克 04），最終竟與真正的結果不謀而合。歐洲足協否認造馬指控，指有關事件純屬巧合。以上報導中指猜中抽籤結果的機會是 28 分之 1（There is a one in 28 chance of correctly guessing the Champions League draw at this stage.），可是那是不正確的。

如何計算 8 隊分成 4 對的可能性數目呢？其中一個方法是先抽 2 隊成對，共有 C(8,2) = 28 種可能；然後從餘下 6 隊中再抽兩隊成對，有 15 種可能；再從餘下 4 隊中抽兩隊成對，有 6 種可能；最後剩下的 2 隊成對。這樣便有 28 x 15 x 6 = 2520 個可能，但由於 4 對的次序不拘，因此每種抽籤結果我們都數了 4! = 24 次，從而抽籤結果只有 2520/24 = 105 個不同的可能。換句話說，猜中抽籤結果的機會應是 105 分之 1。

另一種數算的方法是先隨便選一隊（例如是英文字母序最先的一隊），然後選那隊的對手，這樣有 7 個可能；然後從餘下 6 隊中再選英文字母序最先的一隊，那麼這隊的對手便有 5 個可能；再之後餘下 4 隊中英文字母序最先的一隊的對手有 3 個可能；最後剩下的 2 隊對賽。由此可見，抽籤結果共有 7 x 5 x 3 = 105 個不同的可能。

從第二種方法可知，把 2n 隊分成 n 對對賽的方法共有

1 x 3 x 5 x ... x (2n-1) = (2n-1)!! 種

這裡 k!! 是個「double factorial number」（見註）。而比較兩種數算方法，我們亦可得到等式

C(2,2) x C(4,2) x ... x C(2n,2) = n! (2n-1)!!

這種「算兩次（double counting）」的方法在組合數學裡是很常用的，可以證明很多奇妙的等式或不等式。

---

註：有關「double factorial」的資料，可參考這裡。如果只考慮奇數的 double factorial，即 1!!, 3!!, 5!!, ...，也就是把 2n 人分成 n 對的方法數目，也可參考 The Online Encyclopedia of Integer Sequences 的 A001147。順帶一提，這個「百科全書」很有用，大家可以輸入一串整數（例如：1, 1, 2, 3, 5, 8），然後系統便會搜尋包含這些連續項的數列。

MD Academic Seminar Mar 2008

繼去年十二月廿三日數學資料庫在香港大學舉辦academic seminar後，在接下來的三月十五日，我們在香港城市大學再舉辦academic seminar。詳情如下：

日期：2008 年 3 月 15 日（星期六）
時間：下午 3 時 至 下午 4 時
地點：香港城市大學 P 4902 室
講者：張婉琳小姐（香港中文大學）

講題：An introduction to Strong Conical Hull Intersection Property

簡介：

Strong Conical Hull Intersection Property (strong CHIP in short) is a geometric concept introduced in 1990’s for studying constrained convex optimization problems. In the seminar, a short account of its historical background, its mathematical formulation and its significance in recent researches on optimization will be given.

No specific prerequisites will be needed for the seminar.

REFERENCES:
1.
Deutsch, F. (1998): The role of the strong conical hull intersection property in convex optimization and approximation. In: Chui, Schumaker, eds., Approximation Theory IX, Vanderbilt University Press, Nashville, TN.
2.
Heinz H. Bauschke, Jonathan M. Borwein, Wu Li (1999): Strong conical hull intersection property, bounded linear regularity, Jameson's property (G), and error bounds in convex optimization. Mathematical Programming 86, 135-160
3.
Deutsch, F., Li, W., Ward, J.D. (1997): A dual approach to constrained interpolation from a convex subset of Hilbert space. J. Approx. Theory 90, 385-414

猜包揼

[這是網友singmay向數學資料庫手記提供的文章。]

我們常常要將一群 2n 個人分成兩個 n 人小組，一個常用的方法是「猜包揼」。用簡單的組合知識可以知道每次「猜包揼」成功分組的概率為 C(2n,n) / 2^(2n) ，例如要將12人隨機分成兩組進行排球比賽，用「猜包揼」的方法每次成功的概率是 231/1024 ，另外一個講法是所需要的次數的期望值為 1024 / 231 = 4.4329 。當n很大的時候，成功的概率會越來越少。一個有趣的事實是所需次數的期望值隨著 n 趨向無限而趨向於 sqrt(n * pi) [1]。人太多的時候這可以很花時間，所以這時很多人會用「數1、2」的方法代替，但大家也知道「數1、2」不是一個很隨機的方法，因為通常大家所在的位置並不是完全隨機的，有沒有辨法保持分組方法的隨機性 [2] 而增加分組方法的效率呢？


其中一個方法是在 2n 個人中預先選定一人離開，跟著用「猜包揼」將剩下的2n-1人分成 n 人及 n-1 人兩組，然後將預先選定的那個人分配入有 n-1 人那一組；由對稱性不難知道這個方法沒有損失隨機性，而每次成功分組的概率則會大大增加，例如當 n=6 時，新的方法的成功概率為 231/512 。細心的讀者會發現這個概率是原先的兩倍，而所需要的次數的期望值則是原來的一半。這並不是巧合。事實上無論 n 是多少，新的方法每次的成功概率皆為原來的兩倍，這可以從恆等式 C(2n-1,n-1) + C(2n-1,n) = C(2n,n) 直接看出來 [3] ，有興趣的朋友不防自己證明作為練習。

在實際應用的時候，由於解釋這個方法要花一點時間，本人慣用的做法是自己不出手顯示「包」或「揼」，當其他人分開為 n 人及 n-1 人兩組後自己便加入有 n-1 人的那一組。如果當中有一些是數學人，他們很快會明白本人的意圖，也理解這個方法也是完全隨機的；但如果當中大部份也不是數學人，他們便會說一句「你做乜嘢唔出呀？玩嘢咩！」與其嘗試解釋這個方法為何可行，不如從頭再猜一次，結果反而浪費了時間。

註：
[1] 這點可以用Stirling’s formula證明。Stirling’s formula是 n! 的近似公式，有興趣的朋友可以在這裡找到一篇很好的介紹：
http://episte.math.ntu.edu.tw/articles/mm/mm_17_2_05/index.html

[2] 這裡隨機的嚴格定義是所有可能組合出現的概率也相等。

[3] 另外一個有趣的解釋是預先被選的那人出「包」或「揼」已沒有所謂，所以成功機會剛好是兩倍。

---

數學資料庫所作的補充：第一次有網友向我們提供文章作刊登，本會成員都很高興。希望這個先例可以令更多網友提供關於數學的文章作刊登，令手記成為大家交流數學的一個平台吧！

[以下是 marco_dick 的補充。]

關於上文註[2]所講的「所有可能組合出現的概率也相等」，部分讀者可能不明白，所以在此舉一個不是所有可能組合出現概率相等的例子。

設有 2n 個人，若我們先抽出兩人 A 和 B，然後讓餘下的 2n-2 人以 singmay 在文章第一段所講的方法分成兩個 n-1 人的組別，再隨機讓 A 和 B 每個人加入其中一組，那麼每次可成功分組的機會率會由 C(2n,n) / 2^(2n) 增加至 C(2n-2,n-1) / 2^(2n-2) 。

但是，這種分組方法是會令 A 和 B不可能在同一組；換句話說，所有 A 和 B 同組的組合出現的概率是 0，而A 和 B不同組的組合出現的概率則不是 0，所以這個分組方法違背了「所有可能組合出現的概率也相等」這個原則。

不過這種分組方法在現實中是有用的。例如，當 A 和 B 是仇家時……又例如，10個人分兩組打籃球，但當中只有2個人適合打中鋒（Center），那就必需將他們分開在不同的組。

另外，在每四年一屆的足球世界杯，大會每設出8隊「種子隊」，每隊「種子隊」在分組賽中不會同組，也是「不是所有可能組合出現的概率也相等」的一個例子。