數學奇才比爾.蓋茨

　　比爾·蓋茨善於編程的其中一個原因就是程序本身蘊含的運算性與邏輯性。他良好的數學基礎和豐富的科學知識，使得他在編程方面有着天然的優勢。

　　當時，連許多高年級學生都來向他請教，其中包括保羅·艾倫。艾倫比蓋茨高兩屆，他常向蓋茨挑戰。當他遇到難題時，就對蓋茨說：“嘿，我敢打賭你不會做這道題!”而爭強好勝的蓋茨就會設法證明他的話是錯誤的，不管這道題有多難。他們在這種挑戰和應戰中得以互相提高。比爾·蓋茨的天才在於他善於尋求解決問題的方法，而這種特長與思路開闊以及知識、經驗的豐富是分不開的。

　　在哈佛大學，比爾·蓋茨在數學方面最得意的成就是提出了解決一個數學難題的方法。那是刊登在數學雜誌上的難題：一個廚師做了一疊大小不同的煎餅，他要不斷從上面拿起幾個煎餅翻到下面。假設有N個煎餅，廚師需要翻動多少次，才能完成這個排列？

　　比爾·蓋茨想出了解這道難題的一個比較好的辦法。他將這個方法告訴了數學老師教授克里斯托斯·潘帕萊米托(Christos Papadimitriou)。潘帕萊米托將比爾·蓋茨的方法記錄下來，發表在《離散數學》雜誌上。據說比爾·蓋茨的這個解法是解決這一難題的突破性進展，其影響至少可以在數學界持續15年之久。Gates W.H.; Papadimitriou, C.H. Bounds for sorting by prefix reversal. Discrete Math. 27 (1979), 47--57.

　　但是在群英薈萃的哈佛大學後，蓋茨很快發現，竟有人比他還有數學天分，這曾使他甚感沮喪。

　　有一天晚上，他就邂逅了其中的一位天才學生，此人對他的影響之大就像他高中時的老朋友保羅·艾倫一樣。這個名叫斯蒂夫·鮑爾默後來成為了微軟的新總裁。兩人的友誼在一次觀看“雨中情”和“發條橙”電影時得到鞏固。

　　雖然他們住在同一層宿舍樓的兩端，但是經常在一起學習，並在學業和一些運動項目上展開激烈競爭。

　　斯蒂夫·鮑爾默和蓋茨有着許多的共同點，他們都是一樣精力充沛，可以長時間熬夜不眠。但蓋茨常通宵達旦玩牌，兩人會在早餐時碰面，一起討論應用數學，他倆一起選修研究生的數學和經濟學，但蓋茨大多數時候都逃課，期末才玩命突擊，花儘可能少的時間，得儘可能高的分數，這就是他們的遊戲。

　　在“宏觀經濟學”的期末考試中，兩人雖然從未上過一堂課，但鮑爾默得了97分，而蓋茨高達99分。雖然兩人都想將上課時間降到最少，但與蓋茨的不務正業不同，鮑爾默則將大量的時間投入社會活動，他不僅管理足球隊，擔任文化社社長，還是社交俱樂部的成員。總體來講，二人都是數學高手，但巴爾默更勝一籌。在一次著名的全國性數學競賽中，巴爾默還擊敗過蓋茨。蓋茨在鮑爾默的保護下被接納進哈佛的一個社交俱樂部，但因為總是笨手笨腳，他依然像個局外人。

　　兩人個性不同，但較為投緣，用蓋茨的話說，兩人是“高頻段交流”，彼此能接受對方的全部信息。兩人經常如兩態聯機的終端一樣,或爭論或玩笑或嘲笑或閒聊。

　　當蓋茨決定從哈佛退學，曾受到許多親朋好友的勸阻，其中也包括史蒂夫·鮑爾默。有趣的是，數年後，當史蒂夫·鮑爾默來到斯坦福大學商學院攻讀MBA課程時，蓋茨又來勸他退學去共創天下。經蓋茨的輪番勸告，最後史蒂夫·鮑爾默從斯坦福退學，去了蓋茨創辦的當時只有20來人的微軟公司。

　　與他的哈佛朋友蓋茨一樣，巴爾默最終沒有完成學業，不過他在頭一年就獲得兩項一萬美元的獎學金，從而名聲大振。為此，舊金山的風險資金投資商、蓋茨的好友安·文布拉德稱讚巴爾默“智力超群”。

　　由於發現還有其他的人在數學方面的天分高於自己，比爾·蓋茨於是開始一門心思鑽研電腦，認定這是自己的生財之道。比爾·蓋茨喜歡說他進入計算機業僅僅是因為他想寫出“偉大的軟件”，想儘自己所能創造出最好的產品，但在早期，更強大的動力其實就是賺大錢的欲望。因為在學校期間他也一直沒有停下創業的步伐。

　　比爾·蓋茨在談到數學與電腦的關係時說：“很多著名的電腦專家都有深厚的數學功底，這有助於他們把握證明定理的純粹性。這種純粹性只能用確切而非含糊的語言來論述。在數學中，你不得不把定理用一種潛在的方式加以聯繫，你經常得證實能在更短時間裡解出一道題來。數學與電腦程序設計有着非常直接的關係。這一點也許在我心目中要遠遠勝過別人，因為這是我看問題的出發點，我想這兩者之間有一種很天然的聯繫。”

　　隨着比爾·蓋茨在計算機領域日臻爐火純青，計算機軟件事業的大門轟然洞開。在微軟，人們使用計算機語言描述蓋茨擁有“令人難以置信的處理能力和無限的帶寬，他十分擅長並行處理和多任務處理。”

　　現在，蓋茨可以同時在兩台計算機上工作，一台從互聯網絡中連續不斷地獲得數據，另一台處理着上百封電子郵件和備忘錄，把他的大腦與網絡聯成一體。他加工提煉信息的能力實在驚人，也許他的思維真是數字化的。正是這樣一個具有“革命”腦的人領導了個人計算機革命，並將微軟變成了一個媒介和網絡巨人。

翻煎餅難題(The Pancake Problems)

The Pancake Problems (1975, 1979, 1973)

Originator(s): Jacob Goodman, Bill Gates & Christos Papadimitriou, John Conway

Definitions: A prefix of a permutation or string is an initial segment. A flip is the reversal of a prefix. In a signed permutation, each element i occurs as i or i', and i' is treated as a negated element. When reversing a prefix of a signed permutation, the signs also reverse.

Question 1: (Goodman - 1975) What is the maximum number of flips needed to sort a permutation of [n] into ascending order?

Question 2: (Gates and Papadimitriou - 1979) What is the maximum number of flips needed to sort a signed permutation of [n] into ascending order with all positive signs?

Conjecture 3: The signed permutation of [n] that needs the most flips to sort is 1'2'...n', called I'n.

Question 4: (Conway - 1973; Deterministic version) If the number of elements in the prefix reversal always equals the value of the first element, and the process stops when element 1 is at the front, then what is the maximum number of steps to termination?

Background/motivation: Writing under the name ``Harry Dweighter'', Jacob Goodman [D] described a waiter navigating a busy restaurant with a stack of n pancakes. To avoid disaster, the waiter wants to sort the pancakes in order by size. Having only one free hand, the only available operation is to lift a top portion of the stack, invert it, and replace it. Finding the maximum number of flips needed is the Pancake Problem.

Gates and Papadimitriou [GP] introduced the Burnt Pancake Problem. here one side of each pancake is burnt, and the pancakes must be sorted with the burnt side down. We represent the condition that pancake i is "burnt side up" by putting a negative element i' in place of i in the permutation.

The pancake problem relates to the construction of networks of parallel processors. The network defined by prefix reversal has sublogarithmic diameter and degree as a function of the number of vertices (n!). For the hypercube these values are logarithmic. The transposition network on permutations has slighlty smaller diameter than the pancake network (n instead of something between 15n/14 and 5n/3), but its degree is quadratic instead of linear in n. A prefix reversal sorting algorithm provides a routing algorithm in the network. [19] contains further discussion of the applications.

Conway called the process in the deterministic problem "topswaps". Knuth observed that the Fibonacci numbers provide an upper bound and posed that as an examination question in 1974. Berman and Klamkin [BK] called the problem "Reverse Card Shuffle" and conjectured that the permutation with the maximimum number of steps to termination arrives at the identity permutation. This fails for n=12 and n=15 [MS].

Comments/Partial results: For the Pancake Problem, an upper bound of 2n-3 arises by iteratively putting the next largest element in its proper place with two flips. When the initial permutation has none of the desired adjacencies, at least n flips are needed. Gates and Papadimitriou [GP] showed that (5n+5)/3 flips always suffice and that 17n/16 flips may be needed. Heydari and Sudborough [HS] improved the lower bound to 15n/14. They present the exact values up through n=13, where 15 flips is the maximum.

For the Burnt Pancake Problem, the lower and upper bounds provided by Gates and Papadimitriou were improved slightly by Cohen and Blum [CB] to 3n/2 and 2n-2. Cohen and Blum proved that I'n can be sorted in 23n/14 flips, and Heydari and Sudborough [HS] improved this to 3(n+1)/2. A sequence of flips that sorts a burnt permutation also sorts the corresponding ordinary permutation when sign of elements is ignored, so the sorting complexity of each unburnt permutation is bounded by the complexities of its burnt versions. Hence proving Conjecture 3 would improve the upper bound on the original Pancake Problem.

For the deterministic problem, Knuth's upper bound using Fibonacci numbers grows exponentially with n. Knuth conjectured that the maximum length to termination has a linear upper bound. This was disproved by Morales and Sudborough [MS], who constructed permutations that take a quadratic number of steps to termination.

References:

[BK] Berman D.; Klamkin, M.S. A reverse card shuffle, SIAM Review 19 (1977), 739--741.
[CB] Cohen D.S.; Blum, M. On the problem of sorting burnt pancakes. Discrete Appl. Math. 61 (1995), no. 2, 105--120.
[D] Dweighter, Harry. American Mathematical Monthly 82(1975), 1010.
[GP] Gates W.H.; Papadimitriou, C.H. Bounds for sorting by prefix reversal. Discrete Math. 27 (1979), 47--57.
[HS] Heydari M.H.; Sudborough, I.H. On the diameter of the pancake network. J. Algorithms 25 (1997), no. 1, 67--94.
[MS] Morales L.; Sudborough, I.H. A quadratic lower bound for reverse card shuffle. at 26th S.E. Conf. Comb. Graph Th. Computing, preprint 1995.