2008年3月28日 星期五

The Mysterious Fish Number - 153

John 21:11 Simon Peter climbed aboard and dragged the net ashore. It was full of large fish, 153, but even with so many the net was not torn.

The above scripture is taken from the famous bible story "Jesus and the Miraculous Catch of Fish". Having read the scripture, you may wonder why the number of fish was counted and recorded with such a precision. Indeed, scholars throughout history have argued that 153 has a far deeper meaning!

Mathematically, 153 is a wonderful number.

(A) In the binary system, 153 is written as 10011001, which is a symmetric figure.

(B) 153 is a triangular number (1+2+3+...+16+17 = 153).

(C) 153 is the sum of the first 5 factorials (1!+2!+3!+4!+5! = 153).

(D) 153 is the sum of the cube of each of its digits (1^3+5^3+3^3 = 153).

Here comes the grand finale!

(E) Start with any multiple of 3. By repeatedly summing up the cube of each digit, you will always end up with 153 eventually.

Example 1: Take 66.

6^3+6^3 = 432
4^3+3^3+2^3 = 99
9^3+9^3 = 1458
1^3+4^3+5^3+8^3 = 702
7^3+0^3+2^3 = 351
3^3+5^3+1^3 = 153

Example 2: Take 2001.

2^3+0^3+0^3+1^3 = 9
9^3 = 729
7^3+2^3+9^3 = 1080
1^3+0^3+8^3+0^3 = 513
5^3+1^3+3^3 = 153

Do you know why?

Grothendieck's 80th birthday

Today's the 80th birthday of Alexander Grothendieck. He is usually considered one of the greatest mathematicians of the 20th century. It's hardly an exaggeration that almost all modern algebraic geometers are influenced by his work (in particular, his famous EGA and SGA books). He is also quite a remarkable character: he withdrew from mathematics at the age of 42, and in 1991, he even left his home and disappeared. He is now said to live in southern France or Andorra and to entertain no visitors. Though he has been inactive in mathematics for many years, he remains one of the greatest and most influential mathematicians of modern times. Find out more about him in the following wiki article!

2008年3月27日 星期四



1) 現在有 n 個金幣,已知其中一個是假的,而假的金幣重量與真的金幣不同,但我們不肯定是輕了還是重了。現在給你一個天秤,你每次可以在天秤的兩邊放一些金幣看看哪邊較重,還是兩邊重量一樣。問:

a) 若 n = 5,最少要秤多少次?
b) 若 n = 12,最少要秤多少次?

2) 情況跟第一題一樣,但今次有另外一個已被確定為真的金幣存在。當 n = 5 時,最少要秤多少次?



2008年3月24日 星期一

Pi day

It has been a while now since March 14 - the pi day, but do you know how professors and students at Princeton University celebrates this math day? Here they go: they had a pi recitation competition and a pie eating contest on 3/14 1:59pm! (recall pi = 3.14159... and some graduate students there can remember up to a 100 digits!)

Find out also how the Indiana House of Representatives passed a bill proposing three formal - and inaccurate - definitions of pi, namely 3.2, 3.23 and four (!), and how a graduate student here made a skirt with the digits of pi sewn on it every year, just to celebrate this special day for mathematicians.

Have your pi and eat it too!

By Josephine Wolff
Senior Writer
Published: Friday, March 14th, 2008 on the Daily Princetonian

Applied math professor Ingrid Daubechies first learned about pi as a young child, when her father told her to go around the house and measure the circumference and diameter of every circle she could find.

“It made an incredibly strong impression on me,” Daubechies said. “I remember my father let me touch [the] circles I would otherwise never have been allowed to, like the precious china plates hanging on our wall. I got to take them down and measure them. My mother was very worried.”

Today is a day of celebration for Daubechies and her colleagues and students in Fine Hall, and not just because it’s the last day of midterms. March 14 is celebrated in math classes across the country to honor the number pi — 3/14 mirrors the first three digits of pi, 3.14.

Pi Day is a time of rejoicing — a time for pie-eating contests, pi-digit-recitation competitions, pi-themed clothing, pi jokes (What do you get when you divide the circumference of the sun by its diameter? Pi in the sky!) and other forms of unabashed nerdiness.

“What’s fun about pi is that everyone knows the number,” Daubechies said. “We all see it in elementary school. People feel they have an appreciation for what it means.”

Pi and popular culture

Popular television shows, like “The Simpsons” and “Star Trek,” have helped spread pi’s appeal to mainstream audiences.

In perhaps its most heroic role, pi saves the USS Enterprise starship in the “Star Trek” episode “Wolf in the Fold,” when the evil Redjac takes over the computer running the ship.

Spock tells the computer to “compute to the last digit the value of pi,” destroying the computer with this impossible demand and thereby freeing the ship.

In an episode of “The Simpsons,” “Lisa’s Sax,” two school girls play a patty-cake-style hand game while chanting: “Cross my heart and hope to die, Here’s the digits that make pi: 3.1415926535897932384...”

In another “Simpsons” episode, “Marge in Chains,” Kwik-E-Mart proprietor Apu testifies that he can recite pi to 40,000 decimal places. “The last digit is one!” Apu says, correctly.

“Mmmm, pie,” Homer says.

In preparation for the episode, “Simpsons” writers wrote to NASA asking for the 40,000th digit of pi, and NASA responded by sending back a printout of the first 40,000 digits.

One trillion digits!

Forty thousand may seem like a lot of digits, and in fact, 40 decimal digits are all that we really need for practical calculations, Daubechies said.

She referenced a 1996 article about pi, in which lead author David Bailey, the chief technologist at the Lawrence Berkeley National Laboratory, wrote that the “value of pi to 40 digits would be more than enough to compute the circumference of the Milky Way galaxy to an error less than the size of a proton.”

The first 40,000 digits, however, are barely the tip of the computational iceberg that has helped researchers calculate more than one trillion digits of pi in the past few decades. Yasumasa Kanada at the University of Tokyo has computed more than 6.4 billion digits and currently holds the world record.

Not everyone, however, has been eager to see pi grow so long.

In 1897, the Indiana House of Representatives passed a bill proposing three formal — and inaccurate — definitions of pi. The bill was based on the work of a Dr. Goodwin, who fancied himself an amateur mathematician and claimed he had definitively computed three official values for pi: 3.2, 3.23 and four. Goodwin also copyrighted his ideas and announced that he would allow only schools in Indiana to teach them for free and that everyone else in the country would have to pay him a royalty if they wished to teach or use these “facts.”

The bill was approved by the Senate Education Committee, but Purdue mathematician C.A. Waldo put an end to it before it could be passed into law.

Perhaps the most famous truncation of pi is in the “Second Book of Chronicles.” King Solomon is constructing the Temple of Jerusalem, and he builds a tub of “ten cubits from brim to brim, round in compass, and five cubits the height thereof; and a line of thirty cubits did compass it round about” (1 Kings 7:23). In other words, the circular tub has a diameter of 10 cubits and a circumference of 30 cubits, in which case pi would equal exactly three.

The rabbi Nehemiah, in 150 AD, pointed out that while the diameter of the tub had been measured from the outer rim of the thick stone, the circumference measure was taken along the inner circle, and it was this discrepancy that accounted for the inaccurate portrayal of pi.

A brief history of a lengthy number

The first of pi’s trillion calculated digits date back to the ancient Egyptians and Babylonians, who used 3.16 and 3.125, respectively, as rough estimates of pi.

Mathematicians across the globe have been computing more and more accurate estimates of pi for centuries since, but it was a set of mid-20th-century advances in computing that allowed for the discovery of billions and billions of digits.

John von Neumann, one of the first faculty members at the Institute for Advanced Study in Princeton, played a crucial role in designing ENIAC, the first electronic computer, which in 1949 more than doubled the number of known digits by correctly calculating 2,037 of them.

Today, calculating long values of pi is a common method for testing new computer chips, Daubechies said. A great deal also remains unknown about pi, she added, most notably the question of whether its decimal expansion is normal, that is, whether each digit occurs with relatively equal random frequency in pi.

Irrational holiday

Lillian Pierce ’02 GS said she usually celebrates Pi Day at 3:14 p.m. in 314 Fine Hall or the common room next to it. In the annual pi-reciting and pie-eating contests held in Fine, Pierce added, the physics team usually beats the math team at eating.

“Pi itself is one of the fundamental constants of mathematics. So you could say that it is very important. But it’s also very beautiful,” Pierce said. “Pi Day is a great way for mathematicians to poke fun at themselves. If everyone else is always poking fun at us, it’s only fair we should have a turn too.”

The first Pi Day celebration at Princeton took place in 1988, said Yang Mou ’10, president of the undergraduate math club. This year’s celebration is today at 1:59 p.m. in the Fine Hall common room.

Pierce also makes a pi dress every year for the occasion. In the past, she has embroidered roughly 50 digits of pi around the hem of a dress. This year, however, she is going for “sheer quantity of digits.” If she uses small enough numbers, she estimates, she may be able to fit as many as 1,000 digits around a skirt.

Pierce, like Daubechies, first discovered the joys of pi as a girl when she read a 1992 New Yorker article about pi by Richard Preston.

“I’d always liked numbers, but reading about this many numbers all strung out in an infinitely long, beautiful sequence was incredibly inspiring,” Pierce said.

2008年3月23日 星期日



2005 年:3 月 27 日
2006 年:4 月 16 日
2007 年:4 月 8 日
2008 年:3 月 23 日
2009 年:4 月 12 日
2010 年:4 月 4 日
2011 年:4 月 24 日


根據定義,復活節是每年「3 月 21 日或以後的首個月圓(農曆十四或十五)後的首個星期日」。有關這樣的定義的說法很多,一般指 3 月 21 日是春分(值得注意,春分的日子年年不同,會有前後一天的差距,閏年時春分通常在 3 月 20 日,今年就是一個例子),春分後日長夜短,配合月圓美好的意義。而根據聖經記載,耶穌是在星期日復活的,因此復活節選定為春分起首個月圓後的首個星期日。

在這定義之下,如果 3 月 21 日是星期六兼月圓日,3 月 22 日便是復活節,這也是最早可以出現復活節的日子。上一次出現在 3 月 22 日的復活節在 1818 年,下一次則要到 2285 年。今年的復活節在 3 月 23 日,是第二最早的日子,下一次要到 2160 年才會出現。

復活節最遲在哪一天出現呢?理論上,由於月亮繞地球公轉的周期約為 29.5 天,因此如果 3 月 20 日出現月圓的話,那麼下一次月圓最遲要 30 天後,即 4 月 19 日才出現。如果 4 月 19 日是星期日,那麼便要到 4 月 26 日才是復活節。但基於非常複雜的原因(主要是教會自己定義了月亮周期,而非實質觀察月亮的軌跡),復活節最遲會在 4 月 25 日出現。這個「最遲的復活節」對上一次出現是在 1943 年,下一次則在 2038 年。而 2011 年則會出現「第二遲的復活節」。

每年復活節的日期是有周期性的,每 5700000 年 (!!) 便會重覆一次。在每 5700000 年中,4 月 19 日復活節的次數特別多,約 220000 次。而 3 月 28 日至 4 月 18 日和 4 月 20 日出現復活節的次數相若,平均約 188000 次。其他日子出現的次數則較少,其中 3 月 22 日只有約 29000 次,4 月 25 日則只有約 40000 次。

2008年3月21日 星期五


MD是一個以推廣數學為宗旨的網站,慶祝生日也當然要與數學拉上關係。我們很榮幸邀得香港中文大學的張婉琳小姐主持於三月十五日主持了一個學術講座,向我們的會員為「An introduction to Strong Conical Hull Intersection Property」這個題目作介紹,大家都獲益不少。



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


2008年3月20日 星期四



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






先說前者,「任意」這個字用於集合論之類的數學基礎時是十分含糊的,數學上不存在一個明顯的函數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. 在以下情況中,存在一個策略令只有有限個犯人不被釋放:



2008年3月18日 星期二

升 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 年。不過如果只計恆生指數的話,今天的情況大家在一生之中大概不會遇上很多遍呢!

2008年3月17日 星期一

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

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

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

X : 給出一個圓形,圓周為 r,圓面積的公式 \pi r^2能夠運用積分的方法來證明。

X : 那麼,請問圓形的圓周 2\pi r 可否運用類近的積分算式去「證明」呢?


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



L 為給出圓形的圓周,設圓的圓心為 \left(0,0\right),所以圓的方程為x^2+y^2=r^2

Let L be the circumference of the given circle, suppose the circle center at origin, so the equation of circle is x^2+y^2=r^2.


Consider the first quadrant:


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

By arc length integral and symmetry:



After simplification :



Therefore :

L=4r\left[\sin^{-1}\frac{x}{r}\right]_{0}^{r}=4r\left[\frac{\pi}{2}-0\right]=2\pi r



For reference:
Definition of Pi
Arc length forumla

2008年3月16日 星期日


歐聯八強抽籤結果鬧出造馬疑雲(可參考這篇報導),有網友「未卜先知」,在抽籤前個多小時先行公佈「內定抽籤結果」(阿仙奴對利物浦、曼聯對羅馬、車路士對費倫巴治、巴塞隆拿對史浩克 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 SequencesA001147。順帶一提,這個「百科全書」很有用,大家可以輸入一串整數(例如:1, 1, 2, 3, 5, 8),然後系統便會搜尋包含這些連續項的數列。

2008年3月10日 星期一

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.

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.
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
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

2008年3月6日 星期四



我們常常要將一群 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! 的近似公式,有興趣的朋友可以在這裡找到一篇很好的介紹:

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

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


[以下是 marco_dick 的補充。]


設有 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),那就必需將他們分開在不同的組。