千万别学数学：最折磨人的数学未解之谜（一）数学之美不但体现在漂亮的结论和精妙的证明上，那些尚未解决的数学问题也有让人神魂颠倒的魅力。和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的存在性，它完全没有给...
