比尔.盖茨和煎饼问题

前两天收拾办公室，在落满尘土搁置十几年的纸箱里看到1988年夏天看过的那篇论文：“Boundsfor Sorting By Prefix Reversal”。三十年过去了，弹指一挥间，这篇文章让我想起了我的青葱岁月。

那一年的夏天，我和我的老师Sudborough教授捡起了这个离散数学的经典问题：煎饼问题（pancake problem）。当时我们手头唯一的参考资料就是这篇1979年发表在离散数学杂志的论文。

保留了三十年的一篇论文

       这种枯燥无趣的纯数学问题估计我的读者没听说过，但它曾经的一个证明者却是无人不晓的微软创始人比尔.盖茨。先给大家介绍下什么是煎饼问题：

       一个懒散的厨子做了一叠大小不一的煎饼，随机将它们放在一个盘子里。服务生在将这盘煎饼送给客人前，需要用铲子不断翻转，将其形状变成金字塔形状，也就是最大的放在最下面，最小的放在最上面。请问如果盘子里有n个煎饼的话，服务生需要翻转几次，才能完成这个转换？

       论文题目中的“Prefix Reversal”其实就是将煎饼问题变成了一个对等的排序问题，虽然当时已经快十年了，但结果依然没被超越。

       这个问题的上限（最坏情况需要翻转的次数不会超过这个数）的最明显答案是2n– 3，因为从大到小，最多两次我们可以把一个煎饼放在正确的位置：找到剩下最大的煎饼，先将其翻转到最上面，然后在将其翻转到最下面。每完成一个，我们只需要继续处理上面剩下的煎饼。这样n-1次后，就可以将任何形状的n个煎饼转换成金字塔形。需要翻转次数是2（n-1），因为最后两个煎饼只需翻转一次，所以答案是2n-3。

       算法里下限（有一个形状至少需要翻转这么多次）的证明往往会困难些，一个简单的下限是n+1。感兴趣的朋友可以自己推导下。

       比尔.盖茨在哈佛上大二时，他的数学老师给大家介绍了这个问题。这位未来的计算机巨头被其简单之美所吸引。当时的背景是，他一边为微软初创奋斗，另外一边还要对应哈佛多门课程，即便是这样的焦头烂额，人家愣是生生挤出档期，给出了一个非常漂亮的证明（下限的证明），一个非常有创意的算法（上限的证明）。

       比尔.盖茨证明了对于任意形状的n个煎饼，最多需要翻转（5n+5）/ 3次（大约是1.666n）次，就可以将其转换成金字塔。这个结果大大改进了2n-3的上限。他同时证明下限是17n/16，这个结果也改进了之前n+1的结果。

       我和老师重新拾起这个问题的原因和网络研究相关，具体问题就是找出煎饼网络图的直径，其答案就是煎饼问题的答案。

恩师当年

       记得当时看完盖茨的论文后，只能膜拜。据说他花了很少时间就找到了思路，1978年初他和他的老师将论文投给了著名的离散数学杂志，经过多位编委的严格审阅，于1979年发表。当时的盖茨已经跟哈佛再见，来到了新墨西哥州的Albuquerque，投身到改变人类生活的软件革命。

       整个夏天，在老师的指导下，我对煎饼问题做了些改进，其结果也是我博士论文的一部分。从此，我再也没碰这个问题，而是转向其它问题的研究。我的恩师则继续致力于煎饼问题的解决，如果没记错的话，他1996年左右证明了下限是15n/14，上限是18n/11。

煎饼问题让我想起了多年没再联系的恩师。除了父母，他是我最感恩的人，真希望能回到三十年前，回到那个简单快乐的时候。

老去的恩师