千万别学数学——最折磨人的数学未解之谜(一)

千万别学数学：最折磨人的数学未解之谜（一）数学之美不但体现在漂亮的结论和精妙的证明上，那些尚未解决的数学问题也有让人神魂颠倒的魅力。和Goldbach猜想、Riemann假设不同，有些悬而未解的问题趣味性很强，“数学性”非常弱，乍看上去并没有触及深刻的数学理论，似乎是一道可以被瞬间秒杀的数学趣题，让数学爱好者们“不找到一个巧解就不爽”；但令人称奇的是，它们的困难程度却不亚于那些著名的数学猜想，这或许比各个领域中艰深的数学难题更折磨人吧。作为一本数学趣题集，MathematicalPuzzles一书中竟把仍未解决的数学趣题单独列为一章，可见这些问题有多么令人着迷。我从这一章里挑选了一些问题，在这里和大家分享一下。这本书是04年出版的，书里提到的一些“最新进展”其实已经不是最新的了；不过我也没有仔细考察每个问题当前的进展，因此本文的信息并不保证是100%准确的，在此向读者们表示歉意。这篇文章很长，大家不妨用自己喜欢的方式马克一下，一天读一点。天使和恶魔天使和恶魔在一个无限大的棋盘上玩游戏。每一次，恶魔可以挖掉棋盘上的任意一个格子，天使则可以在棋盘上飞行1000步之后落地；如果天使落在了一个被挖掉的格子上，天使就输了。问题：恶魔能否困住天使（在天使周围挖一圈厚度1000的坑）？这是Conway大牛的又一个经典谜题。经常阅读这个Blog的人会发现，Conway大牛的出镜率极高。不过这一次，Conway真的是伤透了不少数学家的脑筋。作为一个很“正常”的组合游戏，天使与恶魔的问题竟然一直没能得到解决。目前已经有的结论是，如果天使每次只能移动一步，恶魔一定能获胜。不过，天使只要能每次飞两步，似乎就已经很无敌了。当然，魔鬼的优势也不小——它不用担心自己“走错”，每多挖一个坑对于它来说都是有利的。话说回来，Conway本人似乎仍然相信天使能赢——他悬赏了1000美元征求恶魔必胜的证明，但只悬赏了100美元征求天使必胜的证明。一些更详细的讨论可以见这里。Update:网友yllan评论到，这个问题已经被解开了，n≥2时天使贏。详见这里。3x+1问题从任意一个正整数开始，重复对其进行下面的操作：如果这个数是偶数，把它除以2；如果这个数是奇数，则把它扩大到原来的3倍后再加1。序列是否最终总会变成4,2,1,4,2,1,…的循环？这个问题可以说是一个“坑”——乍看之下，问题非常简单，突破口很多，于是数学家们纷纷往里面跳；殊不知进去容易出去难，不少数学家到死都没把这个问题搞出来。已经中招的数学家不计其数，这可以从3x+1问题的各种别名看出来：3x+1问题又叫Collatz猜想、Syracuse问题、Kakutani问题、Hasse算法、Ulam问题等等。后来，由于命名争议太大，干脆让谁都不沾光，直接叫做3x+1问题算了。3x+1问题不是一般的困难。这里举一个例子来说明数列收敛有多么没规律。从26开始算起，10步就掉入了“421陷阱”：26,13,40,20,10,5,16,8,4,2,1,4,2,1,…但是，从27开始算起，数字会一路飙升到几千多，你很可能会一度认为它脱离了“421陷阱”；但是，经过上百步运算后，它还是跌了回来：27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1,4,2,1,…随机01串的最长公共子序列如果从数字序列A中删除一些数字就能得到数字序列B，我们就说B是A的子序列。例如，110是010010的子序列，但不是001011的子序列。两个序列的“公共子序列”有很多，其中最长的那个就叫做“最长公共子序列”。随机产生两个长度为n的01序列，其中数字1出现的概率是p，数字0出现的概率是1-p。用Cp(n)来表示它们的最长公共子序列的长度，用Cp来表示Cp(n)/n的极限值。关于Cp的存在性，有一个非常巧妙的证明；然而，这个证明仅仅说明了Cp的存在性，它完全没有给计算Cp带来任何有用的提示。即使是C1/2的值，也没人能成功算出来。MichaelSteele猜想C1/2=2/(1+√2)≈0.828427。后来，V.Chvátal和D.sankoff证明了0.773911C1/20.837623，看上去MichaelSteele的猜想似乎很可能是对的。2003年，GeorgeLueker证明了0.7880C1/20.8263，推翻了MichaelSteele的猜想。更糟的是，“当p为1/2时Cp达到最小”似乎是一件很靠谱的事，但这个结论也无人能证明。曲线的内接正方形证明或推翻，在平面中的任意一条简单封闭曲线上，总能找到四个点，它们恰能组成一个正方形。这样一个看上去如此基本的问题，竟然没有被解决！这个Blog上曾经证明过，任意凸多边形上总存在四个可以构成正方形的点；对证明方法进行改进，可以把结论扩展到凹多边形上。目前，对于充分光滑的曲线，似乎已经有了肯定的结论；但对于任意曲线来说，这仍然是一个悬而未解的问题。平面上的曲线无奇不有，说不准我们真能精心构造出一种不满足要求的怪异曲线。环形跑道难题有一个环形跑道，总长为1个单位。n个人从跑道上的同一位置出发，沿着跑道顺时针一直跑下去。每个人的速度都是固定的，但不同人的速度不同。证明或推翻，对于每一个人，总会有一个时刻，他与其他所有人的距离都不小于1/n。乍看上去，这个问题无异于其它各种非常巧妙的初等组合数学问题，但不可思议的是，这个问题竟然直到现在仍没解决。目前最好的结果是，当n≤6时，结论是成立的。直觉上，对于更大的n，结论也应该成立，不过尚未有人证明。排序问题加强版有n个盒子，从左至右依次编号为1,2,…,n。第1个盒子里放两个编号为n的小球，第2个盒子里放两个编号为n-1的小球，以此类推，第n个盒子里放两个编号为1的小球。每一次，你可以在相邻两个盒子中各取一个小球，交换它们的位置。为了把所有小球放进正确的盒子里，最少需要几次交换？为了说明这个问题背后的陷阱，我们不妨先拿n=5的情况做个例子。首先，如果每个盒子里只有一个球，问题就变成了经典的排序问题了：只能交换相邻元素，如何最快地把5,4,3,2,1变成1,2,3,4,5？如果一个数列中前面的某个数反而比后面的某个数大，我们就说这两个数是一个“逆序对”。显然，初始情况下所有数对都是逆序对，n=5时逆序对共有10个。我们的目的就是要把这个数目减少到0。而交换两个相邻的数只能消除一个逆序对，因此10次交换是必需的。不过，题目里面每个盒子里有两个球，那么是不是必须要交换20次才行呢？错！下面这种做法可以奇迹般地在15步之内完成排序：55,44,33,22,1154,54,33,22,1154,43,53,22,1154,43,32,52,1154,43,32,21,5154,43,21,32,5154,31,42,32,5141,53,42,32,5141,32,54,32,5141,32,42,53,5141,32,42,31,5541,32,21,43,5541,21,32,43,5511,42,32,43,5511,22,43,43,5511,22,33,44,55第一次看上去似乎很不可思议，但细想一下还是能想明白的：同一个盒子里能够放两个数，确实多了很多新的可能。如果左边盒子里的某个数比右边某个盒子里的数大，我们就说这两个数构成一个逆序对；但如果两个不同的数在同一个盒子里，我们就把它们视作半个逆序对。现在让我们来看看，一次交换最多能消除多少个逆序对。假设某一步交换把ab,cd变成了ac,bd，最好的情况就是bc这个逆序对彻底消除了，同时ac、bd两个逆序对消除了一半，ab、cd两个（已经消除了一半的）逆序对也消除了一半，因此一次交换最多可以消除3个逆序对。由于一开始每个盒子里的两个相同的数都会在中间的某个时刻分开来，最后又会合并在一起，因此我们可以把初始时两个相同的数也当作一个逆序对。这样的话，初始时每两个数都是逆序对，n个盒子里将产生C(2n,2)个逆序对。自然，我们至少需要C(2n,2)/3步才能完成排序。当n=5时，C(2n,2)/3=15，这就说明了上面给出的n=5的排序方案是最优的。这个分析太巧妙了，实在是让人拍案叫绝。就只可惜，这个下界并不是总能达到的。当n=6时，上述分析得出的下界是22步，但计算机穷举发现没有23步交换是不行的。于是，这个问题又变成了一个诱人的坑，至今仍未被填上。多面体的展开证明或推翻，总可以把一个凸多面体沿着棱剪开，展开成一个简单的平面多边形。这是一个看上去很“自然”的问题，或许大家在玩弄各种纸制包装盒的时候，就已经思考过这个问题了。现在，人们已经找到了不满足条件的凹多面体，也就是说存在凹多面体使得无论怎样展开它都会不可避免地得到与自身重叠的平面多边形。同时，确实也存在一些凸多面体，按照某种方式展开它后，会得到与自身重叠的平面多边形。不过，对于某个凸多面体，任何一种方法都不能把它展开到一个平面上，这听上去似乎不大可能；然而，在数学上这一点却一直没被证明。用平面镜拼成的多边形证明或推翻，对于任意一个内壁全是镜面的多边形，总能在里面找到一个点，使得位于这个点的光源可以照亮整个多边形内部。这是一个非常有创意的问题，只可惜问题最早的出处已经不得而之了。问题有趣就有趣在，“多边形”这个条件是必需的：如果允许有曲线的话，我们就能构造出一个由镜面构成的平面图形（左图），里面的每个点都不能照亮整个图形。对于多边形的情况，1995年Tokarsky给出了一个26边形房间（右图），把光源放在其中一个点上，它将无法照到另一个点（假设顶点处不反射光线）。因此，问题就只剩下一个了：有没有什么多边形，任意位置的光源都无法照亮整个图形？在与之相关的领域中，还有很多很帅的未解问题，大家可以参见这份ppt。Thrackle猜想如果一个图中，每条边都与其它所有边相交恰好一次（顶点处相接也算相交），这个图就叫做一个thrackle。问，是否存在边数大于顶点数的thrackle图？给你一次机会，让你猜猜这个猜想是谁提出来的！没错，又是JohnConway。这明显又是一个坑，看到这个问题谁都想试试，然后就纷纷崩溃掉。Conway悬赏1000美元征解，可见这个问题有多么不容易。目前已知的最好的结果是，一个thrackle的边数不会超过顶点数的两倍减3。遍历所有的“中间子集”证明或推翻，你可以通过每次添加或者删除一个元素，遍历集合{1,2,…,2n+1}的所有大小为n或n+1的子集。看完上面的这一行字，我可以想象你已经有一种克制不住的冲动，拿起铅笔、草稿纸和电脑，开始寻找n不大时的规律。这可以说是本文的所有问题中最大的一个坑了——这个问题极具诱惑性，每个人第一次看到这个问题时都会认为存在一种对所有n都适用的构造解，于是众人一个接一个地往坑里跳，拦都拦不住。没有人认为这个猜想是错误的，简单的计算机枚举显示，随着n的增加，遍历这些子集的方案数不但也随之增加，而且增长得非常之快。到了某个n，方案数突然跌到了0，这明显是一件极不可能发生的事。但是，几十年过去了，却没有人能够证明它！关于Venn图画惯了三个集合的Venn图