【数学八卦】前首富比尔·盖茨的唯一一篇数学论文

luyuanhong

【数学八卦】前首富比尔·盖茨的唯一一篇数学论文

原创 小数点茶馆 小数点同学会 2024 年 08 月 13 日 20:42 山西

虽然才星期二，小数点茶馆要开讲啦！

咱们今天说一个冷门的小八卦，和前首富有关。他在成为首富之前，还发表过一篇数学论文。

松饼排序问题

1975年，美国数学家雅各布·古德曼（Jacob Goodman）在做家务的时候发现了一个有意思的问题。他当时正在叠毛巾，有一摞毛巾因为大小不一，放得歪歪扭扭的。一般人看到这种情况，就抽出来小的毛巾往上放，调整几次就可以把毛巾放整齐了。可古德曼作为数学家，当然是选择更有挑战的方案了：他拿起来上面的几条毛巾，整个翻了个面，再放回去。不断重复这个操作，直到调整好毛巾的顺序。

古德曼试了几次，发现这是一个很有意思的问题，就用笔名 Harry Dweighter （harried waiter ，急匆匆的服务员），虚构了这样一个故事投稿给了《美国数学月刊》（American Mathematical Monthly）：

我们店的厨师特别不讲究，做出来的每张松饼大小都不一致，就那么堆成一摞交给我。没办法，我只好一边整理松饼的顺序（好让最小的那张在最上面，以此类推，一直到最大的那张垫在最下面），一边端去给顾客。我每次只能一下铲起上面的若干张松饼，把它们整个翻过来，重复这个操作（只不过翻的松饼数会有变动），直到调整好顺序。如果有 n 张松饼，我最多需要翻多少次，就能保证理好它们的顺序？

最多翻几次？

古德曼起初觉得这个问题上不了台面，所以用笔名隐瞒了身份。不过，这个问题看起来小儿科，实际解决起来却没那么容易，以至于最后成了一个著名的数学难题：“松饼排序问题”（pancake sorting）。

如果 n=1 ，答案当然是 0 了。只有 1 张松饼，那无所谓松饼的顺序，也就不需要翻转。

如果 n=2 ，答案则是 1 。要么不需要翻转，要么翻一次就能让小的在上大的在下。

如果用 f(n) 来表示松饼排序问题的答案，那么 f(1)=0 ，f(2)=1 。

那 n=3 呢？松饼的顺序自上而下有 6 种可能：小中大、小大中、中小大、中大小、大小中、大中小。需要的翻转次数依次为 0、3、1、2、2、1 。因此， f(3)=3 。


via Simon Singh

更多松饼的情况就变得复杂起来。

n≥4 时，可以肯定 f(n)≥n 。这是因为，当 n≥4 时，我们可以故意把松饼的初始顺序排得很“乱”，使得任意两张都不该相邻（包括最下面的那张松饼，我们让它也不是最大的松饼，不该和盘子相邻）。



如果我们把松饼从小到大编号为 1, 2, 3, …, n ，那么初始时，任意两个相邻的松饼编号都至少相差 2 。此时，n 张松饼一共产生了 n 处不该相邻的地方。只有从不该相邻的两张松饼之间插入铲子，才有可能变出正确的相邻关系，否则这两张松饼永远相邻。这就说明，一定有某种初始状态，至少需要使用 n 次铲子才能排好顺序。

但是，现在我们只能得出 f(n) 一定大于等于 n ，却无法确定 f(n) 的具体值。f(n) 的值有可能更大。比如说，f(6) 的值就是 7 。其中一种需要 7 次翻转的情况是 5, 3, 6, 1, 4, 2 。你可以找来 6 本大小不同的书，按这个顺序叠放在桌子上，自己试一试，看能不能用 7 步给这些书排好序。

不过，不管 n 是多少，f(n) 一定不超过 2n 。这是因为，不管松饼的初始顺序如何，我们都有一种万能的方法，保证 2n 次翻转就能给松饼理好顺序：先找最大的松饼，把它翻到顶上，然后再把所有松饼整个翻面，让最大的松饼到最下面。接着，找第二大的松饼，把它翻到顶上，然后再翻到它该在的位置。不断这样下去，2n 次翻转一定能完成排序。

首富的松饼排序算法

1970 年代，哈佛大学的数学教授哈里·刘易斯（Harry Lewis）在他的组合数学课上介绍了松饼排序问题。那天台下坐着一个不起眼的学生，他 13 岁进入私立学校念书，爱上了计算机编程。松饼排序问题显然很对他胃口，下了课他就开始研究起来。

后来，这位学生就和哈佛的一名年轻助理教授——希腊计算机科学家赫里斯托斯·帕帕季米特里乌（Christos Papadimitriou）——合写了一篇论文投给了《离散数学》（Discrete Mathematics）杂志。他的大名也工工整整地印在了论文的开头——威廉·盖茨（William Gates）。论文中，两人证明了，f(n)≤(5n+5)/3 ，并且当 n 是 16 的倍数时，f(n)≥17n/16 。

两年后，帕帕季米特里乌激动地告诉威廉，论文被接受了！可彼时的威廉已经不在乎了，因为那时他早已从哈佛退学，办了一个写代码的小公司。帕帕季米特里乌心里直嘀咕，白瞎这么聪明一孩子。威廉后来怎么样了呢？

你可能不知道，威廉（William）可以简称威尔（Will），还可以进一步昵称为比尔（Bill）。没错，故事里的威廉还有一个家喻户晓的名字——比尔·盖茨（Bill Gates）。所以，后面的故事你应该也知道了，那个小公司名叫“微软”，开发了 Windows 操作系统，现在已然是科技公司巨头，盖茨也因此成为世界首富。


学生时代的比尔·盖茨

盖茨和帕帕季米特里乌合写的这篇论文是他人生中唯一的一篇数学论文（这也使得比尔·盖茨有了一个埃尔德什数：4）。论文发表的 30 年后，才终于有人成功改进了比尔·盖茨的松饼排序算法，但仅仅优化了 1% ， 并且借助了计算机。要不是比尔·盖茨对计算机行业发展的巨大推动，说不定到现在也没人能够打败他的松饼排序算法。

今天的故事就到这里，小数点茶馆打烊啦！

小数点同学会