偶然读到一个非常帅的证明：用信息熵可以瞬间证明素数有无穷多个。这个证明比本 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 的素数个数的一个下界。

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

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

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

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

查看更多 »

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

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

查看更多 »

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

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

查看更多 »

    不知道大家有没有幻想过，数学中是否存在这样一个牛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之间。不过，最终还是没有找到突破口。

查看更多 »

    概率论并不仅仅是用来算算概率的。有些时候，概率论远比我们想象中的更强大。

    考虑这样一个问题。考虑集合X上的一个集合族，集合族中的所有集合大小均为d。我们说这个集合族是可以二染色的，如果对X的元素进行适当的红蓝二着色之后，每个集合里面都包含了两种颜色的元素。例如，当d=3时，{1,2,3}, {1,2,4}, {1,3,4}, {2,3,5}就是可二染色的，把1、2染成红色，把3、4、5染成蓝色，则每个集合里都含有两种颜色。是否存在d=3的不可二染色集族呢？这样的集族当然是存在的，例如取集合{1,2,3,4,5}的全部C(5,3)个元素个数为3的子集，则无论如何染色，总会有一个集合里面的元素全是一种颜色。上述推理立即告诉我们，对于一个给定的d，一定存在一个集合个数为C(2d-1, d)的不可二染色集族。这个数目还能再少吗？我们想知道，不可二染色集族中的集合个数最少可以少到什么地步。一个极其简单的证明给出了一个下界：集族的大小一定大于2^(d-1)。当d=3时，你一辈子也不能构造一个不可二染色集族，里面只含4个集合。
    为了证明这一点，不妨对X中的所有元素进行随机着色，每个元素取成红色和蓝色的概率均等。那么，一个元素个数为d的集合中，所有元素均为一种颜色的概率就应该是1/2^(d-1)。如果集族内的集合个数只有不到2^(d-1)个，那么即使“集合中是否只有一种颜色”是互相独立的，这些事件的并（至少有一个集合内只有一种颜色）的概率也不超过2^(d-1) * 1/2^(d-1) = 1，何况这些事件还不是独立的，因此存在单色集合的概率必然小于1。这个概率值小于1说明什么？这说明，“至少有一个单色集合”并不是必然事件，一定有一种染色方案使得每个元素里都含两种颜色，换句话说该集族可以被二染色。

查看更多 »

    大家都知道，在一个有序数组里查找指定的数可以做到O(logn)的复杂度。但是大家想过没，在一个有序链表中又怎么样呢？让我们假设有这样一个链表，每个元素都严格小于它的后继元素。每个元素都能访问到自己的前驱元素和后继元素（如果有的话）。另外，我们知道每个元素在内存中的地址，因此可以进行随机存取。或者可以说，这个有序链表中的所有元素都是储存在一个数组中的，但数组本身并不有序。
    现在，我们需要在这个链表中寻找一个指定的数x。你能否设计出一个平均复杂度低于O(n)的算法来？

查看更多 »

    这个月月初就开始看《从一到无穷大》，花了接近两个星期才看完。这确实是一本让人放不下手的好书。考虑到我的阅读速度，一个多星期一本书已经近乎神速了。在这本书里我经常会看到一些有趣的数学知识，前段时间我还写过书里提到的一个有趣的东西——环面上的染色问题反而比平面上的“四色问题”更加简单。这种例子并不罕见，很多时候一些扩展版的问题反而比原问题更加简单。在第八章，我看到了另一个好玩的东西：随机游走(random walk)问题。
    随机游走问题是说，假如你每次随机选择一个方向迈出一个单位的长度，那么n次行动之后你离原点平均有多远（即离原点距离的期望值）。有趣的是，这个问题的二维情况反而比一维情况更加简单，关键就是一维情况下的绝对值符号无法打开来。先拿一维情况来说，多数人第一反应肯定是，平均距离应该是0，因为向左走和向右走的几率是一样的。确实，原点两边的情况是对称的，最终坐标的平均值应该是0才对；但我们这里考虑的是距离，它需要加上一个绝对值的符号，期望显然是一个比0大的数。如果我们做p次实验，那么我们要求的平均距离D就应该是

    其中d的值随机取1或者-1。这里的绝对值符号是一个打不破的坚冰，它让处于不同绝对值符号内的d值无法互相抵消。但是，当同样的问题扩展到二维时，情况有了很大的改变。我们把每一步的路径投射到X轴和Y轴上，利用勾股定理我们可以求出离原点的距离的平方R^2的值：

    一旦把平方展开后，有趣的事情出现了：这些X值和Y值都是有正有负均匀分布的，因此当实验次数p充分大时，除了那几个平方项以外，其它的都抵消了。最后呢，式子就变成了

    于是呢，就有平均距离R=sqrt(n) （准确的说是均方根距离）。我们得出，在二维平面内随机选择方向走一个单位的长度，则n步之后离出发点的平均距离为根号n。这是一个很美妙的结论。

查看更多 »