经典证明：用信息熵证明素数无穷多

2010 年 1 月 6 日 / 29 条评论

偶然读到一个非常帅的证明：用信息熵可以瞬间证明素数有无穷多个。这个证明比本 Blog 之前讲过的五种非主流证明 (282, 539, 1678) 看上去都要帅，并且更重要地，它道出了素数无穷多的根本原因：只有无穷多的素数，才有能力表达出如此丰富的自然数世界。
假设我们从所有不超过 n 的自然数中随机选取一个数 N ，并把它分解成质因数的乘积 N = P1^X1 * P2^X2 * … * Pm^Xm，其中 m 是不超过 n 的素数的个数。注意到由于 2^Xi ≤ Pi^Xi ≤ N ≤ n 对所有 i 都成立，因此我们有 Xi ≤ log(n) 。真正帅的地方来了。考虑随机选取一个 N 带来的信息熵，我们有：

log(n) = H(N)
         = H(X1, X2, …, Xm)
         ≤ H(X1) + H(X2) + … + H(Xm)
         ≤ log(log(n)+1) * m

上面的第一个等号是由信息熵的定义直接得出的。第二个等号是由唯一分解定理得到的：由于一个数可以唯一地分解为质因数的乘积，因此 N 和 (X1, X2, …, Xm) 是一一对应的，知道了前者也就确定了后者，它们的信息熵是相同的。第三行的不等式是由于我们放开了 Xi 的取值条件（每个 Xi 独立取值可能会导致它们的乘积超过 n ），必然会增加结果的不确定性。而每个 Xi 的取值范围不会超出 0 到 log(n) ，最多 log(n)+1 种情况，因此 H(Xi) ≤ log(log(n)+1) ，这就得到了第四行的那个不等式。
整理上式，我们得到了 m ≥ log(n) / log(log(n)+1) ，这不但告诉我们当 n 趋于无穷大时不超过 n 的素数个数也是趋于无穷的，还给出了不超过 n 的素数个数的一个下界。

算法问题征解：怎样生成随机数而不借助任何工具？

2009 年 12 月 27 日 / 73 条评论

如果你身上没有任何可以使用的工具（手机、mp3、手表、尺子、纸和笔等等），也无法寻求别人的帮助，碰巧这时你突然急需获取一个小于10的随机自然数，你该怎么办？

先抛砖引玉，说说我自己想到的一些办法：

取当前年月日之和的个位数（理论上随机性不佳）
憋住呼吸并循环慢念0到9这十个数，在吸下一口气之前看念到多少（潜意识会导致随机性不佳）
拔10根头发，看第几根最长（可以边拔边比并不断更新最大值）
回忆一下看有多少天没来那个了，取个位数（只适用于女性）
看身上一共有多少块钱，取个位数
完整地唱完一首歌，取歌词字数的个位数
随意想一个英文单词，算出所有字母的ASCII码之和并模10

你还能想到哪些有趣的算法？欢迎在下面留言讨论，我会把有意思的留言在这里更新出来。

Buffon投针实验：究竟为什么是pi？

2009 年 11 月 6 日 / 59 条评论

重要通告：最近多次发现我的tom邮箱发出的邮件被识别成了垃圾邮件，是什么原因我还不是很清楚。最近向我的tom邮箱发过邮件但迟迟没有收到回复的朋友麻烦检查一下垃圾邮件箱，或者重新给我发一次邮件，我换一个邮箱回复您。

数学学习真正悲哀的就是，记住了某个神奇而伟大的定理，看懂了其最严密的推导过程，但却始终没能直观地去理解它。虽然严密的推导是必要的，直观理解往往是不准确的，但如果能悟出一个让定理一瞬间变得很显然的解释，这不但是一件很酷的事，而且对定理更透彻的理解和更熟练的运用也很有帮助。我惊奇地发现，国内的每一本高数课本上都严格地讲解了微积分基本定理的证明，但几乎没有任何一个课本上讲过积分等于函数下方的图形面积究竟是为什么。事实上，这几乎是显然的，但还是有不少人学完微积分后仍然没有意识到。每当谈到这个问题时，我更愿意首先提出一个非常有启发性的事实——圆的周长是2·pi·r，圆的面积就是pi·r^2，后者的导数正好就是前者。这个现象是很容易理解的，因为圆的半径每增加一点，面积增加的就是周长那么一圈，换句话说面积的变化就等于周长。类似地，如果你能找到一个函数g(x)，它的导数正好就是f(x)，那么当x每增加一点，g(x)就增加了一条小竖线段，显然g(x)就应当是f(x)下方的面积。看清了这一点之后，我们才能欣赏到微积分基本定理真正牛B的地方。原先大家都是用分割求极限的办法来求函数下方的面积，但Leibniz却把面积看作一个可变的整体，用一种办法“一下子”就把它求了出来。有趣的是，这种现在看来如此自然的神奇办法，一千多年来居然没有任何人想到。

趣题：随机选取两个无穷大的图，求两者相同的概率

2009 年 7 月 20 日 / 43 条评论

假设我们俩各自独立地随机选取一个有无穷多个顶点的图（两点之间1/2的概率有边1/2的概率没有边）。那么，我们俩选到相同的图的概率是多少？

令人难以置信、但想通了之后又异常显然的是，两个图相同的概率为1。并且，我可以精确地告诉你，这个相同的图是什么样子的。考虑这样一个无穷大的图，我们用自然数1, 2, 3, …给所有顶点标号，然后如果y的二进制表达中的右起第x位为1，就在顶点x和顶点y之间连一条线。比如，顶点5就和顶点1、顶点3相连。我可以证明，我们俩都100%地会选取到上述这个图。

趣题：均匀分布且和为常数的n个变量

2009 年 5 月 3 日 / 16 条评论

不知道大家有没有幻想过，数学中是否存在这样一个牛B的问题，发表出来后十几年硬是没有一个人解开；后来某人惊奇地发现，它有一个极其精妙的解答，整个解决过程只需要几句话就能说清楚，但它实在是太巧妙了，这么多年就没有任何人想到。最近我就遇到了这样的事情。3月份UyHiP的题目非常有趣，整个证明几句话就完了，但想到解法的却只有一人。
题目描述也极其简单。对于哪些n，存在一种生成n个随机变量的算法，使得它们在0和1之间均匀分布，且它们的和是一个常数？更进一步，如果这n个变量中任意k个都相互独立，满足要求的k最大是多少（表示成关于n的函数）？

当然，这道题目我也没想出来。答案公布前，我思考了很久，最后还是放弃了。显然n是偶数时这样的算法是存在的，例如当n=6时，只需要先独立地选取3个随机变量X_1, X_2, X_3，然后令X_4 = 1 – X_1，X_5 = 1 – X_2，X_6 = 1 – X_3即可。这可以保证6个变量之和总为3，且它们均匀地分布在[0,1]区间里。但是当n是奇数时，满足要求的算法就未必存在了。例如当n=3时，不妨让X_1和X_2随机取，X_3等于1.5 – X_1 – X_2。这种算法似乎很和谐，问题就出在X_3有可能不在0和1之间。那么，重复执行该操作直到返回一个落在[0,1]里的X_3呢？这样的话变量又不是均匀分布的了，这将让变量更容易取到中间去，因为X_1和X_2太小或太大往往算不出合法的X_3（下图是Mathematica模拟的结果）。我试图从“n个变量的和的期望值是n/2”出发，证明和为1.5的3个变量不可能均匀分布在0到1之间。不过，最终还是没有找到突破口。