January 9, 2010

工作自然不必多说,工作之余抓住同事弄点Brain Tester当然也是很有趣味的一件事情:-)

1、A有51枚硬币,B有50枚硬币,两人同时扔硬币,比谁正面朝上的硬币,问A胜的概率是多少?(这道题我问了好多人了,很有喜感的哈:-) 难也不难,但有点意思。

2、有三个柱子A、B、C,A柱子上有N个盘子编号1到N,现在目标是把A上的盘子移到C上,但只能把每个柱子最上方的盘子从A移到B的最上方,或者从B移到A的最上方,试问最后C上的盘子排列共有多少种情况?

3、8*8的棋盘,把黑白格打乱,但仍然满足每行每列都有4个白格,4个黑格。把1~64从左上到右下依次填到格子里。试证明黑格的数的和=白格数的和。

4、我有两个小孩,现在告诉你其中有一个是女儿,当你看到我的女儿时,另一个在房间里的小孩也是女孩的概率是多少?(题目说的真清楚。。。基本非常简单了。。)

哈,给大家点思考的空间哈。。

解答

1. 假设A只有50枚硬币,B也有50枚硬币A获胜的概率是p的话,那么A有51枚的时候:
P{iswin(A)==Ture}=0.5*p+0.5*(1-2*p)=0.5.
没错。。一般的A有K+1枚,B有K枚。A赢的概率还是0.5,增加了K只是增加了打平的p从而减小了B赢的概率。

2.此题就是Catalan 序列,这个就是问出栈序列的所有的排列。不知道的移步Google下 “Catalan 序列”。

3. 这个题也不难,Suppose 每个格子都是1,那么显然相等。那么先每行加0,8,16,24,。。。56, 再每列加0,1,2,3,4,。。7. 那么这个就转换成1-64了。那么加的过程中显然是不影响黑白的格子的和的差异的(注意到每行每列的黑白格子数目相等)。

4. 这个有点tricky,貌似网路上有人写的很模糊,哈哈,不模糊大家都肯定不会错的。话多也不如看下算式。。。
P{x=1 and y=1| x=1 or y=1} = P{x=1 and y=1}/{x=1 or y=1} = 0.25/0.75=1/3

WorldQuant 对本文有贡献,邵鸟对文字亦有部分贡献。哈哈,仅供娱乐。。

Tags: ,,.
June 19, 2009

--1--

  一個數學家就是一台把咖啡轉化為數學定理的機器。–P. Erdos

Erdos(1913-1996)是當代最偉大的數學家之一,他一生中同485位合作者發表過1475篇數學論文,涉及數學的許多領域。下面的這些故事主 要來自他的傳記《數字情種》,當然也有一些從別處搜集來的故事。

  前面所引的那段話暗示了一天工作19個小時以上(在古稀之年依然如此)的Erdos對興奮劑的依賴。1979年,他的朋友 GrahamErdos打賭,只要他一個月之內不服用安非他明,Graham就輸給他500美元。Erdos成功地贏得了這次打賭,但他對Graham 說:你幫我證明了我不是一個癮君子,但在這段時間內我一無所成。我早晨起來就盯著一張白紙發呆,毫無主意,跟普通人沒有什麼區別。你因此使數學的發展滯後了一個月。所以他隨後便重新開始服用興奮劑。 


--2--

SF創造我們就是為了拿我們的痛苦取樂,我們死得愈早,他的計畫就愈早落空。–Erdos

Erdos有一套他自己的語言。比如說,他稱上帝為“SF”Supreme Fascist,最大的法西斯份子),因為他總是折磨Erdos,藏起他的眼鏡,偷走他的匈牙利護照,甚至把持著各種古怪的數學問題的解答不讓他發現。 Erdos並不敬畏上帝,死亡對於Erdos的唯一意義就是使他無法再進行數學研究,所以他經常說:在墳墓裡有的是時間休息。

Erdos從事數學研究的方式很獨特。他總是遊歷於世界各地的大學和研究所,登門拜訪那裡的數學家,向對方宣佈:我的頭腦敞開著。然後他們便開始討論 數學問題,一連持續幾天,直到雙方都厭倦了為止。他從不在一個城市裡連續呆上一個月,他的座右銘是:另一個屋頂,另一個證明。(Another roof, another proof.


--3--

出生的不幸是什麼時候降臨在你頭上的?–Erdos 常用的問候語

除了SF之外,Erdos還有很多獨特的術語。他稱小孩為ε,稱孫輩為ε^2,稱橋牌打得不好的人為o(x),稱女人為主人,男人為奴隸,結婚為被俘虜了,離婚為自由了,音樂為雜訊,酒精為毒藥,進行一次數學講座為佈道,非數學家為不值一提的人,美國“Sam”,蘇聯為 “Joe”

Martin Gardner第一次見到他的時候,他問Gardner你是什麼時候到的?“Gardner連忙看表,這時Graham小聲告訴他,對於Erdos來 說,這句話的意思是:你是什麼時候出生的?


--4--

一個數學家必須是在每個星期都有一些新的研究工作才成為數學家。–Erdos

Erdos見到他的同行時,總喜歡問:你昨天有什麼新的發現?可事實上並不是每個數學家都能像他那樣每年發表50多篇論文!

一次,他在巴黎演講後,一位法國數學家問他關於某位有爵士頭銜的英國數學家的近況。他回答:”這個可憐的傢伙兩年前就已死去了。”另外一位法國數學家卻 說:”不可能,上個月我還在羅馬見過他。”Erdos答:”你應該明白我的意思,我是指他這兩年沒有搞出什麼新東西來。

Erdos的術語裡,“死了”是指這個人不再進行數學研究離開了才是真正的生理學意義上的死亡。

--5--

我只要拿張紙,坐下,就能思考。–Erdos

在很多張Erdos的照片上,他都是低著頭的。這種姿勢很容易讓人以為是在打盹,但Erdos聲稱他是在思考問題。

1939年,Erdos曾聽過M.KacPrinceton研究所做的一個報告。事後Kac這樣回憶道:在我報告的大部分時間內,他都快要睡著了。報 告的內容跟他的興趣毫不沾邊。在將近結尾時我大致說了一下我在素因數方面遇到的困難。一提起數論,Erdos馬上就精神起來,讓我再解釋一下到底困難在 哪。不到幾分鐘,報告還沒有結束,Erdos就打斷我的講話並宣佈問題解決了!

注:Mark Kac,波蘭裔美籍數學家,主要研究概率論與數學物理,有以他名字命名的Feynman-Kac公式。

--6--

  匈牙利人的問題在於,每次戰爭我們都站錯了隊。–Erdos

Erdos1913326日出生於布達佩斯的一個匈牙利化了的猶太人家庭。匈牙利和猶太,這兩個來自東方的古老的民族,曾經孕育了無數的偉人。八十 三年後,當Erdos與世長辭時,Gordon Raisbeck在給Erdos的表妹的弔唁信中寫道:

  你聽說過兩個哲學家討論存在地外生命之可能性的典故嗎?其中一人說,如果外星人存在,那麼他們的智力水準就有可能超過我們人類,因此我們可以預期他們已經訪問地球了。但他又說:但他們有沒有留下什麼痕跡呢?另外一位哲學家俯身過來時對他耳語道:噓!這裡我們自稱匈牙利人。正是有了像Erdos這樣傑出的人,才成就了這樣的典故。


--7--

我告訴我母親,如果你用100減去250,你便得到-150.–Erdos回憶他4歲時的經歷

如果說這個世界上真的有天才,那Erdos無疑是其中之一。在蹣跚學步時,他就研究日曆,計算母親還有多久才能放假回家。(那時他父親在戰爭中被俄國人俘虜,母親在學校教書,他是由一名家庭女教師撫養。)3歲時,他便能心算3位數的乘法,4歲時便發現了負數。同樣在4歲時,他就算出一些諸如乘火車去太 陽需多長時間之類荒唐可笑的問題來做遊戲。他問她母親的朋友們多大,然後立即心算出她們已經活了多少秒。

在上高中之前,他母親一直不讓他上學,因為害怕他會得傳染病。

他的英語是跟他父親學的,他父親在集中營裡為了打發時間,便用一本書自學了英語。所以Erdos的英語發音一直很糟糕,因為他的父親從來沒有聽過地道 的英語。


--8--

這世上有這麼多的醜惡現象,我都不敢說,假如上帝存在的話,是不是也是聖潔的。–Erdos

1919年,Miklós Horthy在匈牙利建立了歐洲第一個法西斯政權,並發起了一場血腥的排猶運動。幾萬猶太人被迫離開匈牙利,其中包括E.Teller,J.von Neumann, L.Szilard, E.Wigner. 這四個人都去了當時的科學聖地德國,若干年後,他們又都逃到了美國,並參與了曼哈頓工程。

Erdos一家並沒有離開。那時猶太人經常在光天化日之下遭到毆打甚至屠殺,(Wigner就曾遭暴徒襲擊,)Erdos的母親曾對Erdos說:你知 道現在猶太人實在是太難了,我們是不是要去洗禮?六歲的Erdos回答道:那好,你可以做你想做的,可我還會和原來一樣。

這就是Erdos,從不會放棄自己原則的Erdos.

綜觀Erdos的一生,他藐視任何法西斯權威,無論是武裝暴徒,還是不學無術的大學官僚、美國移民局官員、匈牙利秘密員警、FBI、洛杉磯交警,甚至上 帝。

注:Edward Teller,著名物理學家,被稱為氫彈之父

John von Neumann20世紀最偉大的數學家之一,在純粹數學和應用數學的許多領域中都有著無與倫比的貢獻。僅電子電腦之父這一稱謂便足以使他流芳百 世。

Leo Szilard,著名物理學家、生物學家,核鏈式反應的提出者及專利擁有者。193982日,在他和WignerTeller的建議下, Einstein給羅斯福總統寫信,呼籲美國搶在納粹德國之前研製成原子彈,事實上,那封著名信件就是Szilard起草的。

Eugene Wigner20世紀最重要的理論物理學家之一,獲1963Nobel物理獎。 他還是Dirac的大舅子。


--9--

我不明白為什麼我們初次見面時他會那樣說的全是數的平方和各種各樣的證明。在我漸漸瞭解他之後,我發現他並不是那種喜歡過分張揚的人。……所以我真的 不能解釋為什麼他總是在說他所知道的所有證法。–A.VázsonyiErdos的回憶

1930年,17歲的Erdos第一次見到14歲的Vázsonyi時,前者對後者說的第一句話是:

給我舉出一個4位數。

Vázsonyi答道:“2,532.”

它的平方是6,411,024. 對不起,我老了,否則我會立即告訴你它的立方。

Erdos又問道:你知道畢達哥拉斯定理的多少種證法?

“1種。“Vázsonyi說。

我知道37種。你知道位於一條直線上的點不能構成可數集合嗎?繼而Erdos給出了一種證明方法,然後他說他必須跑了。

六十七年後,Vázsonyi仍然清晰地記得當時的情形:

Erdos說他必須時,他像只大猴子一樣駝著背,側著身子,搖擺著雙臂,沿著街一溜兒小跑,引得行人時時回頭觀望。……當他年紀稍大之後,他的 步態不太像猴了,但仍有些奇怪。他老是走得很快,甚至發展到會向一面牆直沖過去,然後突然止步,猛然掉頭,再往回跑。有一次他沒能止住腳步,一下子撞到牆上,弄傷了自己。


--10--

如果你是一隻耗子,你就知道了。–Erdos這樣解釋他把一隻小貓稱為法西斯的原因

儘管受到各種反猶法律的限制,Erdos還是得以在17歲那年進入布達佩斯的Pázmány Péter大學學習。他經常與他的朋友們在公園或廣場裡討論數學問題和時事。

當時的法律禁止群眾聚會,經常會有員警過來盤問他們。他們感覺密探無所不在,不能夠暢所欲言。所以從那時起,Erdos開始使用一些自己獨有的隱語。他用長波人來代表共產主義者,因為紅色光的波長較長;相應地,用短波人來代表法西斯主義者。

政治並不能干擾Erdos和他的朋友們對數學的興趣。Vázsonyi回憶說:他(Erdos)沉浸在素數的世界裡,素數是他的一切,他與素數之間似乎有著某種奇妙的密切關係。大學一年級時,Erdos便證明了Bertrand猜想:n2n之間總存在一個素數,其中n是大於1的整數。這個猜想 最初是在1848年由Chebyshev證明的,但Erdos的證明比Chebyshev的要簡單得多。

20歲時,Erdos便宣稱要用古希臘時期流傳下來的Eratosthenes篩法來給出素數定理的初等證明,若干年後他果然做到了。這是後話。

注:Joseph Louis Francois Bertrand19世紀法國數學家,在數論、概率論、幾何、微分方程等領域均有貢獻。

Pafnuty Lvovitch Chebyshev19世紀俄國數學家,在數學許多領域有開創性工作,是俄國數學的奠基人。

Eratosthenes,與Archimedes同時代的學者,曾任亞歷山大圖書館館長。

--11--

我是猶太人,而匈牙利當時是個半法西斯國家。–Erdos談及他離開匈牙利的原因

早在12歲的時候,Erdos就清楚地知道,由於政治上的原因,他遲早得離開匈牙利。1934年,他獲得了博士學位,隨後便到英國的Manchester 大學進行他的博士後研究。

Erdos抵達英國的第二天,發生了兩件對於他來說頗不尋常的事情,其中一件是這樣的:

Erdos以前從來沒有給麵包片抹過黃油,在家裡都是他母親或傭人給他抹的。他回憶道:我清楚地記得,那一次我剛去英國學習,茶點的時候上了麵包。要是 承認自己從來沒有抹過黃油,那太讓我難堪了,於是我就試了試。還不是太難。

就在10年前,當他11歲的時候,他第一次給自己系了鞋帶。

--12--

最好的數學既是美的,同時又是嚴肅的。–G.H.Hardy

Erdos抵達英國的第二天,還發生了另外一件事,可能對他的影響更大,那就是他遇見了那個時代最為純粹的數學家–Godfrey Harold Hardy.

數學家有很多種類型,像Erdos這樣的可謂鳳毛麟角。(不過好象公眾心目中的數學家都是Erdos這樣子的。)Hardy可謂是跟Erdos截然相反的一類數學家。

Erdos每天工作19個小時,Hardy的生活則有規律得多:他每天只花4個小時(上午9點到下午1點)用於數學研究,下午打板球和網球,晚上與 B.Russell,C.P.Snow, G.E.Moore, A.N.Whitehead, J.M.Keynes, G.M.Trevelyan, E.M.Forster, L.Strachey, L.Woolf人熱烈交談。

Erdos只對數學感興趣,Hardy的興趣則廣泛得多。有一年,他在給朋友的明信片裡談了他新年的6項打算:“1.證明Riemann假設;2.不能讓 211隊在奧威爾舉辦的板球決賽階段第四局比賽中出局;3.找到足以讓公眾信服的證明上帝不存在的論據;4.成為登上珠穆朗瑪峰的第一人;5.成為蘇聯、 大不列顛及德意志聯合王國的首任總統;6.謀殺Mussolini.”

Erdos是天生的流浪者,Hardy則憎惡旅行,尤其是害怕坐船。如果Hardy不得不乘船出海,他就會給朋友寄一張明信片,宣稱自己已經證明了 Riemann假設。他認為這樣一來上帝就不會讓他在旅途中死去,因為上帝–他”個人的敵人”–是不會讓他享有證明Riemann假設的榮譽的。

Erdos其貌不揚,看上去還有些神經質,Hardy則是出了名的美男子,十足的紳士。

當然,他們也有一些共同點,比如說他們兩人都不太喜歡上帝。Hardy拒絕涉足任何帶有崇拜色彩的地方,為了遷就他,劍橋大學特意在校規里加了一條,使他 “可以豁免某些職責,不參加禮拜。”他們兩人也都終身未婚。他們都喜歡與人合作:Hardy與Little-wood及Ramanujan的合作至今仍被人津津樂道,Erdos則有多達485名合作者。

他們兩人更重要的共同點是:他們都是純而又純的數學家,而且也都是第一流的數學家。

注:Godfrey Harold Hardy,劍橋分析學派後期的領袖人物,主要研究調和分析與解析數論。

Bertrand Russell20世紀最著名、最重要、最卓越的思想家之一,曾獲1950Nobel文學獎。

Charles Percy Snow,英國小說家、物理學家和政府官員,曾任劍橋大學行政領導人。

George Edward Moore,英國實在論哲學家,著有《倫理學原理》、《哲學研究》等。

Alfred North Whitehead,英國數學家、哲學家,著有《數學原理》(與Russell合著)、《過程與實在》、《觀念的歷險》等。

John Meynard Keynes,有史以來最偉大的經濟學家之一。

George Macaulay Trevelyan,英國自由主義歷史學家,曾任劍橋大學三一學院院長。

Edward Morgan Forster,英國小說家、散文家、社會和文學評論家,著有小說《霍華茲恩德》、《印度之行》等。

Lytton Strachey,英國傳記作家、批評家,著有《維多利亞女王時代名人傳》等。

Leonard Woolf,英國文學家、出版家、政界人士、記者和國際主義者,他還是Virginia Woolf的丈夫。

Georg Friedrich Bernhard Riemann19世紀德國數學家,在數學的許多領域內均有天才的開拓性工作,對20世紀數學的發展有著難以估量的深遠影響。

John Edensor Littlewood,英國數學家,與Hardy密切合作達35年,共同撰寫了100篇論文。

Srinivasa Aaiyangar Ramanujan,天才的印度數學家,對無窮級數和數論有著驚人的直覺。

--13--

明年哥廷根見!–Erdos理想中的猶太人祝酒辭

到英國後,Erdos開始了他的流浪生涯。他頻繁來往於英國的各個大學之間,從沒有連續七天呆在同一個城市。那時候世界數學的中心是哥廷根大學,儘管希特勒的興起已使哥廷根開始衰落。Erdos一直想去哥廷根,但作為猶太人的他始終沒有達成這個心願。

他每年要回布達佩斯三次,看望雙親和老朋友。有一次,在他回家期間,Vázsuoni正研究一個圖論問題,並找到了這個問題的必要條件。他回憶道:”我幾 乎天天與Erdos見面。但我犯了一個致命的錯誤–我在電話裡把自己的發現告訴了他。我稱這個錯誤是致命的,是因為他在20分鐘後就回電告訴了我證明充分性的方法。’該死的,’我想,’現在我只好和他合作寫這篇論文了。’這個著名的Erdos數’1′究竟給我帶來了什麼,我幾乎一無所知。

“Erdos數”是數學界流傳的一個典故。即給每一個數學家賦予一個Erdos數:Erdos本人的Erdos數是0;曾與Erdos合作發表過文章的人 的Erdos數是1;沒有與Erdos合作發表過文章,但與Erdos數為1的人合作過的是2;……自然,不屬於以上任何一類的就是∞.

--14--

Wir Mathematiker sind alle ein biβchen meschugge. (我們數學家都有些瘋狂。)–E.Landau曾對Erdos說的一句話

在常人眼裡,數學家往往是些怪人。其實數學家多半還是很正常的,只是當他們思考起數學問題時,腦海裡就容不得別的東西了。

Harold Davenport的妻子Anne Davenport回憶說:有一次在三一學院,我想大概是在30年代,Erdos和我丈夫在一個公共場所思考了一個多小時而彼此一言不發。最後, Harold說:這不是0,而是1′,這才打破了長時間的沉寂。然後就是如釋重負、一片歡欣了。他們周圍的人都以為他們瘋了。的確,他們是瘋了。

注:Edmund Landau,德國數學家,主要研究數論與複變函數,曾在柏林大學和哥廷根大學任教授。Erdos沒去過哥廷根,Landau卻訪問過劍橋,他們可能就是 在劍橋見面的。據說Landau懷疑Littlewood這個人的存在性,所以專程去英國看了一下。這個故事還有另外一種版本,說Wiener在訪問劍橋 時遇見了Littlewood,便說:哈!原來還真有你這麼一個人!我還以為LittlewoodHardy發表那些寫得不太好的文章時所用的化名 呢!“Wiener對這個笑話感到非常苦惱,專門在自傳裡辟了謠。

Harold Davenport, 劍橋學派的數論專家,曾任倫敦數學會主席,有各種論著196種。

--15--

人們研究你是因為你是一個數學家,而不是因為你研究Leibniz.–ErdosGodel如是說

193893日發生了捷克事件。那天Erdos正在布達佩斯,他當晚便匆匆趕回英國,幾周後又去了美國,到位於Princeton的高等研究所(Institute for Advanced Study)工作。

高等研究所是30年代初由Bamberger兄妹捐資興建的,首任所長為教育家Abraham Flexner. 這個研究所聘請的第一批研究員是:Alexander, Einstein, Morse, Veblen, von Neumann, Weyl.

Oppenheimer曾稱高等研究所是一座瘋人院,許多年以後他自己成為這家瘋人院的院長。在這裡,Erdos肯定算不上是天才,但卻仍然顯得很怪 異,因為一年半以後他就因為過於“uncouth and unconventional”而被解聘了。不過天真的Erdos卻把在研究所的這段日子稱為他在數學上最有成果的時期。

當時的高等研究所擁有世界上最出色的一批數學家,比如說Godel. 那時候Godel的興趣已經轉向了形而上學,所以Erdos常與他吵得不可開交。

注:Gottfried Wilhelm Leibniz17世紀德國百科全書式的學者,微積分的創始人之一。

Kurt Godel,奧地利裔美籍數學家、邏輯學家。

James Waddell Alexander,美國拓撲學家。

Harold Marston Morse,美國數學家,Morse理論的創立者。

Oswald Veblen,美國幾何學家和拓撲學家。

Claude Hugo Hermann WeylHilbert的得意門生,20世紀最偉大的數學家之一。

Robert Oppenheimer,美國物理學家,曼哈頓計畫的主持人,被稱為原子彈之父


--16--

我知道Einstein絕不信奉人格化的上帝,因為我問過他。–Erdos

如同那個時代曾待在Princeton的其他人一樣,Erdos曾有幸與Einstein交往。有一次在Einstein家吃午飯時,Erdos把自己最 鍾愛的素數理論講給Einstein聽。Einstein對這一理論的評價很高,但他對細節並不感興趣。

他們兩人主要討論的話題還是政治。Erdos一向很關心政治,經常就世界政治和人類的普遍問題發表一些悲觀言論。

原子彈的問世使Einstein再次成為世界關注的焦點,儘管沒有Einstein也能造出原子彈。Erdos曾問Einstein“40年前你想 到過你的質能方程會在你的有生之年得到應用嗎?“Einstein說:我沒料到。我曾想也許最終會得到應用,但沒料到會那麼快。

其實像Einstein或者Erdos這樣的科學家並不很關心自己的理論能否得到應用。一個極端的例子是Erdos曾經拜訪過的Hardy,他就宣稱最好 的理論是毫無用處的,比如數論和相對論,–不幸的是他舉的這兩個例子都錯了。

--17--

他在Princeton的大街上走來走去,揮舞著雙手,旁若無人地比劃著。–Louise StrausErdos的回憶

Einstein相比,他的數學助手Ernst StrausErdos之間有著更多的共同語言。每當他在自己的宿舍裡住膩的時候,他就跑到Straus的家裡呆上若干天。

那時Straus夫婦經常在半夜裡聽到一聲巨響,那是Erdos在開窗戶,他從沒想到應該輕輕地把窗戶放下。他不會使用淋浴器,不會把水龍頭關上。他 到公用電話亭裡徹夜不停地往裡面塞硬幣,給世界各地的數學家打電話,宣稱自己在Straus家裡,然後和他們討論問題。他還邀請附近的一些朋友到這裡來, 不管主人是否同意。

許多年以後,Straus說:“Einstein曾對我說過……對於一個科學家而言,首要任務是解決核心問題,而不為其他問題所動–無論那些問題多難,多麼具有誘惑力。Erdos完全違背了Einstein的這一番話,但他卻取得了成功。他幾乎癡迷於他所遇到的每一個難題,並成功解決了其中的大部分。

--18--

你應該找一份實際的正經工作。–HalmosErdos的勸告

P.R.Halmos曾記載過ErdosPrinceton時的另一個故事。Hurewicz曾經提出過這樣一個問題:Hilbert空間中有理點集合 的維數是多少?Erdos聽到這個問題後,便問”Hilbert空間”和”維數”各是什麼意思。有人把定義告訴他,很快Erdos便得出了答案。這是 Erdos對一個他幾乎一無所知的領域作出的貢獻!

注:Paul Richard Halmos,匈牙利裔美籍數學家,Springer-Verlag出版社主編。著有《測度論》等。

Witold Hurewicz,波蘭裔美籍數學家,維數理論和同倫論的開創者。

David Hilbert,德國人,歷史上最有影響的數學家之一。他使哥廷根成為當時世界上數學家朝拜的聖地。

--19--

Erdos在任何時刻都集中精神思考。–S.M.Ulam

那時候Erdos手頭很拮据,只能靠大學發給他的訪問津貼度日。被高等研究所解聘後,他一度失去了生活來源,幸好Ulam向他伸出了援助之手。Ulam Erdos在劍橋結識的朋友,當他得知Erdos的窘境後,便邀請Erdos到他工作的Wisconsin-Madison大學來訪問。

許多年以後,Ulam在他的自傳中回憶道:“Erdos身材中等偏下,極度的神經質,他幾乎總是上竄下跳,或者揮舞著他的雙臂。他的眼神表明他總是在 思考著數學問題,只有在他就一些還模糊不清的世界時事政治和人類的普遍問題發表相當悲觀的言論時才會被打斷。如果他突然產生了一個有意思的想法,就會一下子跳起來,揮舞雙臂,然後再坐下來。

注:Stanislaw Marcin Ulam,波蘭裔美籍數學家。早年研究拓撲,後因參與曼哈頓工程,興趣遂轉向應用數學。他是Monte Carlo方法的創始人之一。

--20--

(Erdos)具有神秘的技能,可以運用最深奧、抽象的數學工具來預測原子彈的反應。–Ulam

1943年,UlamLos Alamos參與原子彈的研製。他極力勸說Erdos也加入他們的行列,Erdos本人也很願意為消滅法西斯而出力。於是Erdos給他的同胞 E.Teller寫信,申請加入曼哈頓工程。但Erdos在信中特別強調他戰後要回匈牙利,所以理所當然地被取消了資格。

Erdos就是總喜歡和權威對著幹,而且根本不遵守各種保密規則。他還給在Los AlamosP.Lax寄了一張明信片:親愛的Peter,我的間諜告訴我Sam正在造原子彈,告訴我,這是真的嗎?

還有一次,Erdos和包括Lax在內的幾個匈牙利人一起吃晚飯。席間他們一直用匈牙利語交談,Erdos卻突然用英語大聲問:原子彈的研製進展如何?

注:Peter Lax,匈牙利裔美籍猶太數學家,主要研究泛函分析、偏微分方程和應用數學。曾任美國數學會主席、美國原子能委員會計算和應用數學中心主任、紐約大學 Courant數學研究所所長、紐約大學Courant數學和計算實驗室主任。1987年獲Wolf獎。他還是北京大學榮譽研究博士。

--21--

數學家能在沒有粉筆、紙或筆的情況下工作,他可能在走路、吃飯甚至談天時繼續思考。–Ulam

其實Erdos無論如何都不可能被接納到曼哈頓工程中的,因為他在FBI早已有了案底。1941年,他還在Princeton的時候,有一次與兩名 Princeton的學生,加久穀靜雄和A.H.Stone,一起去Chicago參加一個會議,途經長島,便下來看看海景。他們在一個無線電發射塔可能是一個秘密的軍用雷達附近拍照,被警衛發現。警衛報警稱“3個日本人在這裡鬼鬼祟祟地拍照,於是員警四處搜捕,終於在路上截獲了他們。

FBI的調查人員問他們為什麼沒有看到“NO TRESPASSING”的標牌,Erdos說:我正在思考問題。“”思考些什麼?“”數學。

當晚,他們的身份被確認,於是得到釋放。但此事已經被FBI記錄在案,並對Erdos產生了不利的影響,這是後話。

--22--

他的到來極大地豐富了我們的業餘生活。一位Purdue大學老師對Erdos的回憶

類似的一件事情發生在1943年。那年ErdosPurdue大學找了一份非全日性工作,總算擺脫了四處舉債的日子。

Purdue時,他不分晝夜地散步。有一次,他半夜三更在外面溜達,被員警叫住了。他沒帶任何證件,員警便問:你在幹嗎?“”我在思考問題。“”思考 什麼?“”數學。於是他們滿腹狐疑地放他走了。

Purdue位於一個與世隔絕的小鎮,人們的娛樂活動很少。Purdue的老師們每週都要聚會一次,進行一些非正式的演講和討論。有一次演講人沒有到,又沒有準備別的節目,Erdos便自告奮勇,上臺演講。他不借助任何稿子,做了一個引人入勝的關於蜜蜂的色視覺方面的近期研究進展狀況的報告。台下的人都大感驚訝,因為從沒想到只癡迷於數學的Erdos還會關注這類東西。

--23--

納粹殺害了我母親的4個兄妹。–Erdos

戰爭期間Erdos一直得不到家人的訊息,很掛念他們。19458月,他終於收到了消息。他母親仍然健在,但他父親已死于心臟病。

蘇軍佔領匈牙利後,紅色 植 代替了白色恐怖。紅軍士兵在街上隨意抓人,大批匈牙利人被送往古拉格群島,其中絕大多數再也沒有回來。

Turán就曾經有過一段危險的經歷。當時他在布達佩斯被一個蘇聯巡邏兵攔住去路,被要求出示證件。可Turán剛逃過納粹的搜捕,身上沒有任何證件。情 急之下,他拿出一本1935年出版的《托木斯克數學力學研究所通報》,上面有他和Erdos合著的一篇論文。這本戰前的蘇聯雜誌顯然贏得了士兵的好感,於 是他被放行了。後來Turán遇見Erdos時,感慨地說:”沒想到數論還有這樣的妙用!

注:Paul Turán,匈牙利數學家,主要研究數論和圖論。( chocolate語:Turan定理)

--24--

他(Ulam)真的很幸運,並沒有遭受年邁體衰和老年癡呆這兩大惡魔的折磨,他在依然還能求證、還能猜想的時候猝死於心臟病,死時沒有痛苦,沒有恐懼。- -Erdos

如果你是一位才華橫溢的數學家,如果你不幸得了腦炎,如果在你做完腦部手術、恢復清醒之後,醫生問你這樣一個問題:“813的和是多少?你的感覺會是 怎樣的?

這就是Ulam1945年冬天的遭遇。也許他會從此喪失對自己數學能力的信心,如果他在走出醫院的時候沒有遇見Erdos. 那天,當Ulam在妻子的攙扶下離開醫院時,突然看見Erdos神氣活現地出現在他們的面前。

“Stan!我還以為你已經死了,正準備替你寫訃告,還打算獨自完成咱們合寫的論文。

Erdos手提一個小箱子,裡面裝著他的全部財產,顯然是無處可去,於是Ulam便邀請他去自己的家。在乘車回家的路上,Erdos纏著Ulam討論數學 問題,根本不讓Ulam休息。一到家,Erdos就要Ulam同他下棋。Ulam起初對於下棋感到很緊張,惟恐自己已經把規則忘記了。當他贏了第一盤之 後,又懷疑是Erdos故意讓他的。Erdos要求下第二盤,結果Ulam又贏了。這時Erdos說:到此為止吧,我累了。“Ulam才發現原來 Erdos是認真的。

Erdos在Ulam家裡住了兩周,不停地與Ulam討論數學問題。在Ulam做手術後,Erdos是第一個把他當作數學家而不是白癡或者准白癡看待的人。

--25--

死亡從40歲開始。–Erdos

1948年冬,Erdos回到布達佩斯,看望了他的母親和一些老朋友。但很快史達林就開展了一次筆跡審查活動,大肆封鎖邊界、圍捕公民,Erdos不得不 再次逃離匈牙利。隨後幾年內,他往返於美國和英國之間,居無定所。

那時Erdos已經開始在信件裡不停地抱怨自己已經老了,他還經常對人說,上帝已有一隻手搭在了他的肩膀上。有人問他:“Paul,如果你才40歲時就感 覺如此之糟,當你50歲時又會如何?他立即悲哀地說:更糟。

科學家的創造年華通常是很短暫的,所以學術機構中都設有終身職位,以保證科學家的生活。Erdos的朋友們勸他儘快找一份終生職位,他們說:”Paul, 你那走江湖數學家的生涯還要維持多久?”他竟回答:”起碼40年。”他甚至拒絕了一些大學的終身職位的邀請。

--26--

數學是科學的女王,數論是數學的女王。–C.F.Gauss

大約在1792年,15歲的Gauss經過深入的分析和例證,猜想素數在自然數中的的分佈密度應該是1/log(x),因而,他提出這樣的公式:π(x) Li(x) , x → +∞
∞ 1
其中π(x)表示不超過x的素數的個數,Li(x)∫ — dt
2 log(t)

Gauss曾經寫信給當時世界上一些著名的數學家,向他們請教這個問題,但沒人能給出證明。

差不多在同一時候,Legendre通過數值計算,於1808年提出了這樣一個經驗公式:

x
π(x)~ ——– , 當 x → +∞
log(x)
1.08366

容易看到,GaussLegendre提出的漸進公式是等階的,實際上都等同於猜想
x
π(x)
, 當 x → +∞
log(x)
(不過Gauss的猜想更加深刻和精確。)

這就是19世紀最著名的數學難題:素數定理。這個猜想是非常令人驚異的,因為素數在自然數中的分佈可以說相當雜亂無章,但它竟然還能用這樣簡單的公式 來描述!

Gauss的一生中,肯定曾花費了不少時間和精力來思考這個從少年時便開始困惑他的難題,但我們沒有Gauss關於這個問題的研究記錄,所以也無法知道 他在這個問題上究竟走了多遠,不過十有八九是他並沒有解決這個猜想。

注:Carl Friedrich Gauss,主要生活在19世紀的德國數學家。他通常被認為是歷史上最偉大的三位數學家之一,另外兩個是ArchimedesNewton.

Adrien-Marie Legendre,活躍於大革命前後的法國數學家,在數學的許多方面都作出了重要貢獻。

--27--

高等算術(即數論–編者注)中一些最美麗的定理具有這樣的特性:它們極易從經驗事實中歸納出來,但其證明卻隱藏得極深,只有高人一等的研究者才能把它們 挖掘出來。正是出於此種原因,賦予高等算術以神奇魅力,使之成為第一流數學家們最喜愛的科學。至於它遠遠淩駕於數學其他各分支之上的無限豐富性,那就更不必提了。–C.F.Gauss

首先對素數定理的研究作出了重要貢獻的是Chebyshev. 他證明了存在兩個正常數C_1C_2 ,使不等式
x x
C_1—
π(x)C_2—
log(x) log(x)
對充分大的x成立,並且相當精確地定出了C_1C_2的數值。他還證明了
π(x)log(x)
__ π(x)log(x)
lim —–
1lim —–
 ̄ ̄ x x
x→∞ x→∞
也就是說,如果π(x)log(x)/x 的極限存在,則必定是1. 這些無疑都是很重要的進展,但不幸的是,用Chebyshev的方法無法證明最後的結果。

1859年,Riemann發表了題為論不超過一個給定值的素數個數的論文,這是他唯一一篇關於數論的論文。在這篇僅8頁的論文裡面,Riemann 首次深刻而系統地研究了ζ函數
∞ 1
ζ(s)=Σ –
n=1 n^s
的性質。並且指出,素數的分佈與ζ函數,特別是ζ函數的零點的性質有著密切的聯繫。在這篇文章裡,他還提出六個關於ζ函數的猜想,其中一個就是著名的 Riemann假設:ζ(s)的所有非平凡零點都位於直線 Re(s)=1/2 上。

Riemann的這篇論文為素數分佈理論的研究指明了方向,以後這方面所有的進展都是從他的思想中得來的。

1896年,兩位年輕的數學家Hadamardde la Vallée Poussin按照Riemann的思路,各自獨立地利用高深的整函數理論證明了素數定理,從而解決了這個有一個世紀歷史的難題。後來Landau, Hardy-Littlewood等人利用函數論的知識給出了素數定理的新證明。

以上各人的證明都需要利用ζ函數以及一些較深的分析工具。後來Wiener用實分析的方法證明了素數定理等價於“ζ函數的零點不在直線 Re(s)=1 。這就更讓人相信,素數定理的證明必然要用到ζ函數以及高深的分析工具。

1921年,G.H.Hardy就曾經說過這樣一段話:斷言一個數學定理不能用某種方法證明,這可能顯得過於輕率;但有一件事(素數 定理沒有初等證明) 卻是清楚的。如果有誰能給出素數定理的初等證明,那麼他就將表明,我們過去關於數學中何謂’深刻’、何謂’膚淺’的看法都是錯誤的。那時我們就不得不把書 本都拋在一邊,重寫整個理論。

Hardy逝世於1947年,他萬萬沒有想到,就在他去世的兩年後,兩位年輕的數學家就推翻了他以及整個數學界的斷言,用完全”初等”的方法給出了素數定 理的證明,進而導致了整個素數理論的重寫。

注:Jacques Salomon Hadamard,法國數學家,在數學的許多方面均有貢獻,被譽為Poincaré之後少有的多面手。

Charles Jean Gustave Nicolas Baron de la Vallée Poussin ,比利時數學家,他是國際數學聯盟(IMU)首任主席。

Norbert Wiener,美國數學家、哲學家,控制論的創立者,在調和分析、數學物理、概率論、泛函分析、非線性數學、生理學等許多方面都有巨大貢獻。1964年獲 美國國家科學獎章。


--28--

我很同情非數學家,我覺得他們失去了一種最激動人心的、豐富的智力活動的回報。–Selberg

1949年,兩位年輕的數學家,31歲的Selberg35歲的Erdos分別獨立地證明了素數定理。與以往的證明不同的是,他們的證明沒有用到ζ函 數,而且除了極限、e^xlog(x)的簡單性質外,沒有用到任何高等數學的知識,甚至連微分和積分都沒有用到!可以說,他們給出的是一個完全初等的證明,這一結果轟動了整個數學界。
(後來有人用 1 + x/1! + x^2/2! + … + x^N/N! 代替 e^x
Σ 1/n 代替log(x)nx
給出了一個連超越函數都不需要用的初等證明。)

Erdos的一生中,儘管發表了1475篇論文,但圖元數定理的初等證明這樣具有劃時代意義的成果卻很少。但Erdos對這件事卻避而不談,因為在這件 事上頗有爭議。

當時Selberg發現了一個恒等式,他把這個恒等式告訴了Erdos. 然後他們兩人分別獨立地用這個恒等式給出了素數定理的初等證明。他們本來商量好在同一本雜誌上一起發表文章,講述各自的工作。Erdos便到處給數學家發 信,宣稱他和Selberg已經給出了素數定理的初等證明。但有一次,Selberg碰上一位陌生的數學家,對方開口就說:你知道嗎?Erdos和誰來著?用初等方法證明了素數定理。“Selberg傷透了心,便搶先發表了論文,並因此享有該成果的大部分權益。Selberg也從此與 Erdos反目。

在數學家中,優先權的爭論並不少見,最著名的就是NewtonLeibniz關於微積分發明權的爭論。但Erdos卻具有罕見的坦蕩 胸懷,他願意與別人 分享他的數學思想,他的目的並不是要第一個去證明某個問題,而只是使這個問題得到解決不管是不是他解決的。所以Erdos才能有創紀錄的485名合作 者。但我們不能指責Selberg心胸狹窄,因為即使Newton或者Gauss這樣的最偉大的數學家也會陷入優先權的爭論之中。這只能說是一場悲劇。

注:Atle Selberg,挪威裔美籍數學家,在數論、調和分析、離散子群、自守函數等方面均有貢獻。1950年獲Fields獎,1986年獲Wolf獎。 1998530日至615日應北京大學的邀請到中國進行學術訪問。


--29--

對於Erdos來說,被剝奪了旅行的權利就像是被剝奪了呼吸的權利一樣。–M.Henriksen

1954年,Erdos被邀請參加一個在阿姆斯特丹舉行的學術會議,他於是便向美國移民局申請再入境許可證。那時正是麥卡錫時代,美國處於一片紅色恐懼之中。(以至於當Erdos想往匈牙利一個共產主義國家打電話時,都沒人敢把電話借給他。)

移民局的官員不想給Erdos發再入境許可證,便向他問了各種各樣愚蠢的問題。

你母親是否對匈牙利政府有很大的影響?你讀過馬克思、恩格斯或者史達林的著作嗎?

沒有。“Erdos回答。

你對馬克思如何評價?

我沒有資格評價他,但毫無疑問他是個偉人。

離開匈牙利容易嗎?“–這是一句廢話,因為誰都知道答案是否定的。

不容易。我現在還不想訪問匈牙利,因為我不知道他們是否會讓我返回來,我只是計畫去英國和荷蘭。

如果你能肯定匈牙利政府會讓你離開,你會訪問匈牙利嗎?

那當然了,我母親在那兒,還有好多朋友也在那兒。

在麥卡錫時代,你是不可以承認你想去一個共產主義國家的。


--30--

我現在在澳大利亞,明天去匈牙利。設k為最大的整數以滿足……–一封典型的Erdos的信件的開頭

移民局沒有給Erdos再入境許可證。Erdos請了一名律師提出上訴,結果被駁回。法院沒有給出任何理由。他的律師被允許查閱部分 Erdos的檔案,發 現其中附有一封Erdos寫給居住在紅色中國的華羅庚的信:親愛的華,設p是一個奇素數……”Erdos一年要寫1500封左右的信,基本上都在討論數 學問題。但移民局的官員顯然害怕信中的那些他們看不懂的數學符號是某種密碼。

另外根據FBI的記錄,Erdos還曾經涉嫌在一個雷達站附近從事間諜活動。所以他被麥卡錫踢出美國是再正常不過的事了。

Erdos說:我沒有取得再入境許可證便離開了美國。我想我這樣做完全是按著美國最優良的傳統行事:你不能讓自己任憑政府擺佈。


--31--

他是一個流浪的學者(wandering scholar)。他時常橫跨五大洲。他效忠的是科學的女王而不是任何特別地方或研究所。–Rado談Erdos

被趕出美國之後,Erdos發現自己已經沒什麼地方可去了:荷蘭只給了他幾個月的簽證,英國也差不多。西歐的各個國家都不願意接納一個對紅色中國親善的人。最後,以色列接納了他,給予他居住權,但他拒絕加入以色列國籍,並且保留自己的匈牙利護照。

1955年,Erdos在密友們的多方奔走和呼籲下,終於得以訪問匈牙利。匈牙利政府頒發給他一個特別護照,證明他是匈牙利公民,但擁有以色列居住權。從此Erdos能夠自由出入匈牙利。他每年都要回去幾次,看望母親和朋友們。

Erdos永遠都不會安居在一個地方,他宣佈自己是世界公民。他以驚人的速度穿梭于各個大學和數學研究所之間。他的足跡踏遍五大洲,他在超過25個國家 裡進行數學研究,在遙遠的地方完成各種重要的論證,有時還在這些地方的不知名的雜誌上發表自己的成果。他曾經在六十年代初和八十年代中期兩次訪問中國。 1990年,為柯召教授八十儷暨執教六十周年,《四川大學學報》出了一本專輯。Erdos熱情地寫了一篇題為《初等數論中的某些問題與成果祝我的朋友 和合作者柯召80壽辰》的論文發表在該專輯上。

他的全部財產都裝在一隻破舊的小衣箱和一個在布達佩斯中心商場購買的土黃色塑膠包裡。

流浪,流浪,這就是一個猶太人的宿命。

注:Richard Rado,德國數學家,後移居英國。主要研究組合數學。

柯召,中國數學家,研究方向為數論、組合數學、代數等。


--32--

Non numerantur sed ponderunter.(不是看數,而是稱重。)俗諺

在古代匈牙利的貴族院,統計選票不是看票數,而是稱重量。Erdos經常會想像上帝正拿著天平衡量他與同事們合著的論文。天平的一端放上他與已去世的同事 合著的論文,另一端放上他與仍在世的數學家合著的論文。當亡者的那一端下沉的時候,我肯定也要死了。他這樣說。

是的,每個人都會衰老,都會死去。所以Erdos以驚人的精力工作,他害怕有一天他再也不能思考。

即使在70多歲的時候,他還一年發表50多篇論文。

有人曾經寫過一首打油詩:

有一個猜想的確深奧
圓是否是圓的有誰知道
Erdos用庫爾德語
寫的一篇論文中
一個反例已經找到

Erdos聽到這首詩時,他想用庫爾德語發表一篇論文,但卻找不到庫爾德語的數學雜誌。


--33--

他(Erdos)的工作節奏真是逼死人。–Ralph Faudree

不知道那些有幸受到Erdos拜訪的數學家們會有何感觸,至少孟菲斯大學的Ralph Faudree是很不適應。他發現Erdos每天僅僅需要3個小時的睡眠,每天很早就起來寫信–都是有關數學的。他起來後,覺得別人也該起來工作了,就 把電視打開,聲音開得大大的。他還會跑去敲Faudree的臥室的門:”Ralph,你還活著嗎?”吃飯的時候,他也會在餐巾上寫寫畫畫或是不停地討論數 學問題。

Faudree後來回憶道:等他住上一兩個星期後你都快要崩潰了,但就在他走後的幾天裡,我還會不斷收到他的電話:證明完成了沒有?你把它交給打字員 了嗎?‘”


--34--

他(Erdos)一定是認為我有可取之處,因為後來連續10多年他每年都來路易斯維爾找我,而且一呆就是一個星期。–Michael Jacobson

1983年,Erdos第一次到路易斯維爾拜訪Michael Jacobson. 那時Jacobson還沒結婚,於是就跟Erdos住在一起。他對Erdos的故事早有耳聞,已經作好準備與之一起拼命工作,但情況顯然遠超過他的預料。

頭一天我們就工作到半夜1點,我已經精疲力竭,上樓睡覺去了。他呆在樓下的客房裡。淩晨4點半,我聽到廚房有響聲,他把鍋碗瓢盆弄得 一片響,那是在告訴 我該起床了。大約6點鐘時,我跌跌撞撞地下了樓。你猜他說的第一句話是什麼?不是早上好!也不是睡得好嗎?而是n是整數,k……’我只穿了 一件浴衣,半裸著身體,眼睛還是半睜半閉, 壊壉矓。我認輸了。我告訴他,不洗一個淋浴的話,我是沒法接著研究數學的。


--35--

沒有人知道Erdos身在何處,甚至不可能知道他在哪個國家。我們唯一能肯定的是,他無處不在。他是最接近於遍歷態的人。–R. E. Bellman

範德比爾特大學的Mike Plummer回憶了這樣一件事情:“1983年耶誕節前夜,我一家都在布達佩斯。這兒耶誕節可是一個隆重的節日,各家各戶都團聚在一起開拆禮物。城市都停止運作了,所有單位都打烊,連公共汽車都不開了。要想坐計程車的話,幾天前就得預訂。我們都穿好了衣服,等著計程車來接我們去看一個朋友。正當我們站在 屋裡時,突然聽到一陣敲門聲。我打開門一看,是Erdos站在那裡。‘Plummer,’他說道,聖誕快樂。設f(n)是以下函數……’就這樣我們一直討論到計程車來時為止。要想止住他的話而離去那是很困難的。

注:Richard Ernest Bellman,美國數學家。在變分法、自動控制、逼近論、控制論、運籌學等方面取得了大量成果。共發表640篇論文和44本專著。


--36--

Erdos有一種激勵人的本領,他能把人們帶到一個全新的水準。他的數學世界是我們都能夠進入的。–Joel Spencer

數學家,尤其是年輕的數學家,都願意跟Erdos討論問題,Erdos也是來者不拒。通常他每到一個地方,就能跟那裡的數學家合作發表一兩篇論文。在數學界廣為流傳著這樣一個笑話,說他有一次坐火車,在路上跟檢票員合作完成了一篇論文。

南京師範大學的單墫教授曾有幸聽過Erdos佈道。他的講演並不精彩,聲音甚低,又常常用身體擋住黑板,只聽他念念有詞,迅速地寫,迅速地擦,不知 他說了些什麼,也不知道他寫了些什麼。但講完之後,人們還是熱烈地圍上去,與他討論問題,交流想法。


--37--

全世界的數學家,聯合起來!–F.Klein

有一年,ErdosUCLA,那裡很多人都想和他討論,便問他什麼時候有空。Erdos總是回答:任何時候。結果他的房間裡經常聚集著一大幫人,而 Erdos同時和幾個不同的人討論不同的數學問題。

他滿屋子轉,就像一位超級棋手同時跟好幾個人下棋。Bruce Rothschild說:那可真夠刺激。當他正與別人合作時,趁著他還沒回到你身邊,你還有點時間考慮考慮。你還有機會知道別人正在著手解決什麼問題。

Erdos自己可以同時思考好幾個問題,但他卻希望他的合作者精力集中在手頭的問題上。當他察覺到他們走神時,他會說:不許開小差!

注:Felix Christian Klein,德國數學家。在他所生活的那個時代,他是哥廷根乃至整個數學界的領袖之一。


--38--

下棋確確實實是一個數學問題,但從某種意義上說卻是一個微不足道的數學問題。–G.H.Hardy

另外一個故事也是關於他的不可思議的分身術的:40年代的時候,Michael Golomb曾看見Erdos正和一位國際象棋高手Nat Fine下棋:“Erdos戰勝對手的機會很少,而且總是通過心理戰術……我看見Nat雙手托著下頜,仔細盤算著如何走下一步棋,而Erdos卻似乎在全 神貫注地研究一本厚厚的醫學大百科全書……我問他:‘Paul,你在幹嘛呢?你不是正在跟Nat下棋嗎?他回答說:別打斷我,我正在證明一個定理。 ‘”


--39--

從來沒有什麼下棋的問題影響過科學思維的進程,而Pythagoras,NewtonEinstein都分別在他們不同的時代改變了科學思維的方向。- -G.H.Hardy

在一次會議期間,Erdos看見單墫和另外一位中國數學家下圍棋,頗感興趣,便要求和單墫下。但他知道中國人是下“Go”的高手,就提 出得讓他四個子。下 的時候,他全身覆蓋在棋盤上(眼睛相當近視)。第一盤自然是輸了,又要求再下一盤。第二盤單墫故意讓他贏,他絲毫沒有覺察,還非常高興,連聲說: “We are equal!”

注:Pythagoras,古希臘數學家、哲學家。他創立了歷史上第一個數學團體,深刻地影響了古希臘的數學發展。


--40--

數學從純理論角度看是有序而美好的,這種秩序超越了物質世界。–Erdos

Erdos只對數學感興趣,但這並不意味著他對數學以外的事物完全無知。他會下國際象棋,會下圍棋,會打橋牌,會打乒乓球,而且他還有十分淵博的歷史和科 技知識。一次,在匈牙利科學院賓館,有人把Erdos介紹給Lajos Elekes. Erdos首先發問:”你從事什麼職業?”許多人在知道Elekes是一位正在寫一本關於15世紀匈牙利將軍János Hunyadi的書的歷史學家時都會無言以對,但Erdos立即追問:”匈牙利軍隊在1444年瓦爾納戰役中慘敗於土耳其的原因是什麼?


--41--

從某種意義上說,數學是唯一無限的人類活動。可以想像,人類終將有一天獲得物理學或者生物學的全部知識,但人類永遠無法窮盡所有的數學知識,因為數學領域 是無限廣大的。數字本身是無窮多的。這就是數學成為我唯一興趣的原因。–Erdos

Erdos最後一次看小說是在20世紀40年代,最後一次看電影是在50年代。有一次,一位同事帶他去航太中心看火箭,但他甚至連頭都沒有抬。還有一次他被人拉去看默劇,可表演沒開始他就睡著了。

40年代的時候,UCLA曾經有過為中國舉行的募捐活動。有人向Erdos提議,如果他跟他們一起去看脫衣舞,那麼他們就捐獻100美 元。出乎眾人的意料,Erdos竟然同意了。當他們支付了100美元時,Erdos狡黠地說:噢,我騙了你們。我取下了眼鏡,便什麼都看不到了!


--42--

Erdos的證明總是很漂亮,使用的技巧常常比別人的更好、更高超。–M.Golomb

Erdos對許多數學領域均有貢獻,而他的智慧遠遠超出了他的專業領域。George Purdy回憶了這樣一件事:”1976年我們在德州農機學院的數學休息室喝咖啡時,看見黑板上有一個有關泛函分析的問題。對這個領域,Erdos一無所 知。碰巧我知道有兩位這方面的專家剛剛得出一個長達30頁的解答並因此而沾沾自喜。Erdos抬頭看了看黑板說道:’那是什麼?那也是一個問題?’我說’ 是的’,然後他就走到黑板前面眯著眼睛看了看那個簡要陳述的問題。他問了幾個有關符號代表什麼意義,便毫不費力地寫出一個兩行的解答。要是那還不是魔力,什麼才是呢?


--43--

上帝不擲骰子。–Einstein

數學往往是要求精確的。但Erdos開創了一種存在性問題的概率證明方法,把隨機性引入證明之中。他可以證明許多現象存在的概率很大,甚至是1,但不給出 構造。這種辦法在電腦裡經常會用到。想像一下這樣一個難題:我是應該先邁左腳,還是應該先邁右腳?對這個問題如果非要找一個合理的回答,那就怎麼也邁不了步,於是便會陷入閉環。最好的辦法是擲一枚硬幣,讓上帝來替我們選擇。

1989年,為紀念Erdos概率證明方法的發現,參加在波蘭波茲南召開的隨機圖論會議的數學家們舉行了一次隨機賽跑。當他們繞著跑道賽跑時,誰也不知道終點在哪裡。賽跑開始前,Erdos作為 賓擲了一枚巨大的骰子以決定起始的圈數,當大家快接近終點線時,Erdos又擲了一次骰子以決定再增加的圈數……Erdos開心地笑了,顯然對自己所扮演的煩人的SF”角色相當滿意。


--44--

有位法國社會主義者說私有財產是竊取之物,而我認為私有財產就是累贅。–Erdos

Erdos每見到一個無家可歸的人,總要給他些錢。D.G.Larman回憶道:“60年代初,當我還是倫敦大學學院的一個學生時, Erdos來這兒講學一年。他第一個月的工資剛發下來就在尤斯頓車站碰上一個乞丐找他要茶錢。Erdos從放工資的口袋裡留出支付自己簡單生活的少量費用後把剩下的錢都給了乞丐。

每當他得知一件好事,比如說艱難起步的古典音樂電臺、美洲土著人運動、走失兒童撫養所,他就會捐一些錢。在他去世一年後,他所捐贈的組織還給他寫信表示感 謝。

--45--

這東西,只這一點點兒,就可以使黑的變成白的,醜的變成美的,錯的變成對的,卑賤變成尊貴,老人變成少年,懦夫變成勇士。莎士比亞,《雅典的泰門》

1984年,Erdos獲得Wolf數學獎。他把5萬美元獎金的大部分捐給了以他父母的名義設立的獎學金,自己只留下720美元。他曾兩次去印度講學,所 得的報酬都捐給了一位素昧平生的印度婦女–Ramanujan的遺孀。

80年代末,Erdos得知一位叫Glen Whitney的高中生想到Harvard去學數學,但還差一點兒學費。Erdos便與他此人見了面。當他深信這名學生確有天資時,就借給了他1000美元,並告訴對方只有在不造成經濟困難的情況下才還錢。10年後Whitney有能力償還這筆錢了,便問Graham:”Erdos要不要利息呢? “Graham向Erdos詢問,Erdos回答:”告訴他,拿那1000美元去做我當年所做的事。


--46--

只要一門科學分支能提出大量的問題,它就充滿著生命力;而問題缺乏則預示著獨立發展的衰亡或終止。–D.Hilbert

Erdos經常在各種數學雜誌上拋出一些懸賞征解的數學問題,獎金數目從五美元到三千美元不等。許多年輕人都愛做Erdos提出的問題,當然不光是因為有 獎金。Erdos提出的問題往往重要而有趣,很多人就是在解決了這些問題後走上數學道路的。

有人曾問Erdos,假如所有的問題都同時解決了,事情會怎麼樣?他還支付得起嗎?Erdos當然支付不起。不過他認為所有問題同時解 決的可能性太小了, 比銀行遭擠兌的概率還要小。Erdos去世後,他的朋友Graham決定負責支付他在圖論問題上的獎金,總額約10000美元,達拉斯的一位銀行家則提出 支付其他領域裡的問題的獎金。

下面是一個有三千美元獎金的問題:

如果正整數序列a1,a2,……有這樣的性質:

1/ai
i=1
那麼原來的數列中存在長度為任意自然數的等差數列。


--47--

孩子們從來不認為他們會死,我也是這樣,直到4歲時。當時我正和母親逛商店,突然意識到自己錯了。我哭了起來,我知道我會死的。從那時起,我總是想再年輕一些。–Erdos

早在四十年代,Erdos便一再在書信裡宣稱自己已經老了。1970年,他在洛杉磯作了一次”我從事數學的前25億年”的講演:”當我 還小時,據說地球已 有20億歲年齡。現在,科學家們說地球有45億歲。這樣一來,我就有25億歲了。”聽講座的學生們畫了一條時間曲線,畫上Erdos正騎著一條恐龍。有人 問他:”恐龍是怎麼一回事?”Erdos答:”你看,我忘記了,因為一個老人只記得很早時候的事,而恐龍則是昨天才出生的,就在1億年以前。


--48--

一個人衰老的第一個標誌,是忘記了自己的定理,第二個標誌是忘記拉上拉鍊,第三個標誌是忘了拉開拉鍊。 –Ulam

70年代初,Erdos開始用P.G.O.M.來代表他的名字,意為“Poor Great Old Man”。到他60歲時,就成了P.G.O.M.L.D.L.D.“Living Dead”。到65歲時,又成了P.G.O.M.L.D.A.D.A.D.意為“Archaeological Discovery”70歲時,換成了P.G.O.M.L.D.A.D.L.D.L.D.“Legal Dead”75歲時,又成了P.G.O.M.L.D.A.D.L.D.C.D.C.D.“Counts Dead”,他解釋道:匈牙利科學院有200名成員。當成員滿75歲時,還可以留在科學院並享有充分的特權,但已不再計為成員了。這就是計數死亡的 含義。


--49--

我從未做過什麼”有用”的事情。我的任何發現都沒有,也不可能對平靜的現實世界產生什麼影響,不管是直接的還是間接的,也不管是正面的還是負面的。– G.H.Hardy

與Hardy不同,Erdos對數學的應用更能容忍,事實上他的很多成果都獲得了應用。但Erdos的興趣只在”純粹”數學方面,並且明確反對任何脫離純粹數學的傾向。

Vázsonyi回憶道:當我為繼續當一位數學家還是去工學院當一名工程師的問題猶豫不決時,Erdos警告我:我會藏起來,等你一去工學院,我就斃 了你。一句話就把我搞定了。


--50--

每一樣能夠用於善舉的東西同樣也能夠用於惡行。歸根到底,確定毒氣傳播的微分方程同樣也能描述污染物的擴散。因此,人們既能有意散播毒氣,又能防止污染的 擴散。–Erdos

二戰期間,M.Kac曾在MIT的輻射實驗室工作,他根據當時的研究成果在《應用物理雜誌》上發表了一篇論文。然後他就收到了Erdos寄給他的明信片, 上面只有一句話:我為你的靈魂祈禱。


--51--

One should have a general attitude of welcoming to everybody.–B.Russell

Erdos非常富有同情心。1945年,他到一位數學同行家裡參加晚會,但剛與大家打了個招呼,便不見了蹤影,直到晚會快結束時才再次見到他。原來 Erdos得知主人有一個雙目失明的老父親,不能來參加晚會,孤零零地呆在樓上的一個房間裡;於是Erdos寧願放棄與數學同行們共度良宵的機會,而上樓 去陪伴那位孤獨的失明老人。

Peter Winkler談了另一件事:我們有一個非常聰明的學生,可惜患有腦癱,人坐在輪椅裡。當Paul第一次見到他時,便立即跑上去,詢問他的病情和預後狀 況。Erdos10分鐘內對這個學生的瞭解比我們在他整個研究生學習期間對他的瞭解都要多。此後Erdos對這個學生的研究工作很是關心當時該生正 在完成他的博士論文,提了很多中肯的建議。諸如此類的事情在他的一生中不勝枚舉。


--52--

每次他(Erdos)回到匈牙利時,他總要問候那些年邁的婦女們。光花在這些數學家的母親和遺孀上的時間就要耗掉他回來後的頭兩三天。 –Vera Sós

1994年在布達佩斯,Erdos去看望他的一位老朋友的岳母。那位老夫人坐著輪椅,並且出於某種原因生活在精神的痛苦中。她不住地埋怨她的保姆:別放 在那兒!“”為什麼不先給Erdos教授先生上茶?臨走的時候保姆把客人們送出門,Erdos給了她一份相當豐厚的小費,好象是對她所受委屈的一種安 慰。

Erdos總是盡自己的可能幫助別人。當身無分文的俄羅斯數學家來到匈牙利時,他把自己所有的錢都給了他們。

塞爾維亞數學家Aleksandar Ivic談了另外一件事:一次他與Erdos一同在餐館吃飯,兩人正討論一個數論問題,Erdos突然從兜裡掏出一疊不同國家的鈔票,並用一種柔和的語調 說:拿著吧!我知道你現在很缺外匯。“Ivic非常窘迫,對Erdos說,從貝爾格勒目前的政治、經濟形勢看,他在可預見的將來是還不了這筆錢的。 Erdos堅持要給他,但Ivic最終還是沒有要。

Tags: ,.
December 24, 2008

今年的面试题中,涉及到随机过程(Stochastic Process)和马尔可夫链(Markov Chain)的题目很多也大多属于相对较难和较有意思的一类。下面从一条题目引开来:

Morgan Stanley的口算题:
抛硬币,第一次遇到连续两次正面朝上的时候停下来,问:抛的次数的期望N

解:
假设期望N次后终止,
  那么第一次如果抛出反面(T)那么就回到了前面的情况,即N+1,这个$latex P_1$是1/2
  如果前两次抛出了正反(HT)那么又回到开始的情况,即N+2,这个$latex P_{2_1}$是1/4
  如果前两次抛出了正正(HH)那么就已经停止了,即2,这个$latex P_{2_2}$也是1/4

那么综合上述:
$latex N=\frac{(N+1)}{2}+\frac{(N+2)}{4}+\frac{2}{4}$
解上面的方程得到:N=6,那么这个问题就解决了。

很容易想到的一个推广:

SinRain的笔算题:
抛硬币,第一次遇到连续n次正面朝上的时候停下来,问:抛的次数的期望N=f(n)

先用前面类似的方法:
那么第一次如果抛出反面(T)那么就回到了前面的情况,即N+1,这个$latex P_1$是1/2
如果前两次抛出了正反(HT)那么又回到开始的情况,即N+2,这个$latex P_2$是1/4
如果前三次抛出了正正反(HHT)那么又回到开始的情况,即N+3,这个$latex P_3$是1/8
..
如果前n次抛出了正…正反(H…HT)那么又回到开始的情况,即N+n,这个$latex P_{n_1}=\frac{1}{2^n}$
如果前n次抛出了正…正正(H…HH)那么就停止了,即此时n,这个$latex P_{n_2}$是$latex \frac{1}{2^n}$

那么综上所述:
$latex N=\frac{(N+1)}{2}+\frac{(N+2)}{4}+..\frac{(N+n)}{2^n}+\frac{n}{2^n}$
解这个方程,得到$latex N=f(n)=2(2^n-1)$
特别的,n=2时,N=6回到上面的答案。

————————————————— 

这个题目说到底是个Markov Chain上的首达问题,下面开始简单介绍下MC. 然后给出一个我猜想的首达问题和物理中电路分析中的电势还有电流电阻的一个比较,我甚至觉得电路中的电子的流动就是Kind of MC. 很有趣的想法,我在床上想了很久,觉得很有意思。

Definition:
Markov Chain
$latex Pr( X_{n+1}=x \mid X_n=x_n, X_{n-1}=x_{n-1}, …X_1=x_1)=Pr( X_{n+1}=x \mid X_n=x_n)$

说白了就是下一步的概率只和当前状态有关,而和如何到达这个状态无关。下面重点讨论使用比较多的MC,已知$latex X_n$为状态i,$latex X_{n+1}$到达状态j的概率(单步转移概率),用
$latex P_{ij}^{n,n+1}=P(X_{n+1}=j|X_n=i)$来表示。

$latex P_{ij}^{n,n+1}$是一个与n无关的变量,通常我们把所有的$latex \mathbb{P}=||P_{ij}||_{nn}$写成一个方阵,称之为“单步状态转移矩阵”

P=|P_00,P_01,P_02...|
  |P_10,P_11,P_12...|
  |P_20,P_21,P_22...|
  |....,....,.......|
  |P_i0,P_i1,P_i2...|
  |....,....,.......|

—————————————————
自然的,P矩阵n次方后就是n步状态转移矩阵了。一个显然的式子是:

$latex P_{ij}^n=\sum_{k=0}^{\infty}P_{ik}^rP_{kj}^s, \forall r+s=n$

如果$latex P^n$很容易求出来一般式子,那么首达问题就可以由定义求出来

$latex E(N(i,j))=\sum_{k=1}^{\infty}kP_{ij}^k\prod_{t=1}^{k-1}(1-P_{ij}^t)$
当然这个是个非常奔放的想法,偶尔题目很简单的时候可以用用:
比如这个:

抛硬币,第一次遇到连续两次抛的一样的时候停下来,问:抛的次数的期望N (答案为3)

一般情况下上上面的方法有些过于奔放了而做不出答案。假设有{X1,X2..Xn}个不同的状态,不妨假设Xn为终止态,从X1出发,这是个单入口单出口的首达问题。假设从Xi出发首达Xn的期望是Yi步,那么可以由下面的方程组来解决问题:),其中Y是一组列向量,且Yn=0;
Y=P’(Y+1),其中P’为将原单步转移矩阵的第n行替换为(0,0,0,…0) (亦即终点态)

继续用最开始的抛硬币的例子做个说明,所有可能的状态是:
X0: NULL;
X1: H; X2: T;
X3: HT; X4: TH; X5: HH; X6: TT;
X0->|X1->X3 |
    |  ->X5 | <--终点
    |       |
    |X2->X4 |
    |  ->X6 |

我们不妨只研究X3-X6的状态就可以了
转移矩阵P为
   3  4  5  6
3| 0 0.5 0 0.5 |
4| 0.5 0 0.5 0 |
5| 0.5 0 0.5 0 |
6| 0 0.5 0 0.5 |

| 0 0.5 0 0.5 | |Y3+1|  |Y3|
| 0.5 0 0.5 0 | |Y4+1|= |Y4|
| 0   0 0   0 | |Y5+1|  |Y5|
| 0 0.5 0 0.5 | |Y6+1|  |Y6|
注意到Y5=0解得: 
                |Y3|=|6|
                |Y4|=|4|
                |Y5|=|0|
                |Y6|=|6|
--------------------

故总的次数为:2+1/4(6+4+0+6)=6 (到达X3-X6的概率都一样都是1/4,前面都用了2步所以要加2)
那么一般的情况也解决了:
都是转化为一个多元的线性方程组来解. 更进一步的,还可以推广到多出口的问题:Xi,Xi+1..Xj都是终点。此外这个题目和电路分析中的电势分析很类似,所谓终止就是接地(V=0),然后已知了上部的电阻的分布,要求的是各个部分的电势。
电子在遇到分叉口时依照一定的概率选择跳到下一个路口,如果是有可能转移的,那么中间以导线相连,转移的概率越大,电阻越小。当源源不断的数以亿万计的电子流过电路时,就好比是Monte Carlo 中的随机simulation,从宏观上表现出来就是各个电路部分的电流大小不一样,并且并联电路上的电势差是一样的。
给个算例:
        C
 A┏━R━┳━R━┳━R━┳━R━┳━R━...
  ┃    ┃    ┃     ┃    ┃
  R     R     R     R     R
  ┃    ┃    ┃     ┃    ┃
 B┗━R━┻━R━┻━R━┻━R━┻━R━...
        D

求A-B的电阻,每一段电阻都是R,这个是个无限的问题,可以用类似前面的技巧来做:
设B为0态,那么A-B的电阻为X那么 C-D两点向右看也是个X,
那么X=R(R+X+R)/(R+R+X+R) 
得到$latex X=(\sqrt{3}-1)R$

总结下:1. 不用技巧的话,首达问题就转化为一个解线性方程组的问题
         2. 用点技巧的话,无限的问题可以转化为一个“无限的旅馆”问题
         3. 我觉得电子在导体内部各个节点的随机游动也好比是个MC问题,平稳后宏观表现就是使得电势差和路径无关(基尔霍夫定律)
下次写点Brownian motion 貌似这个在真实环境用的比较多。

顺便留道思考题,也是某知名公司的面试题:
有一个袋子里有4个不同颜色的球(更一般的有n个),每次操作取两个球,并且把后取出来的球染成前一个的颜色再把两个球放回袋子里。试问球的颜色将变成一种颜色的期望操作次数。

Tags: ,,.