有一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续的 n 个正面？它的答案是 2^(n+1) - 2 。取 n=2 的话，我们就有这样的结论：平均要抛掷 6 次硬币，才能得到两个连续的正面。或许这个期望次数比你想象中的要多吧。我们不妨试着来验证一下这一结果。由简单的递推可得，所有 1 都不相邻的 k 位 01 串有 F_k+2 个，其中 F_i 表示 Fibonacci 数列中的第 i 项。而“抛掷第 k 次才出现连续两个正面”的意思就是， k 位 01 串的末三位是 011 ，并且前面 k - 3 位中的数字 1 都不相邻。因此，在所有 2^k 个 k 位 01 串中，只有 F_k-1 个是满足要求的。因此，我们要求的期望值就等于 ∑ (k=2..∞) k * F_k-1 / 2^k 。这个无穷级数就等于 6 。我怎么算的呢？我用 Mathematica 算的。

 
    显然，当 n 更大的时候，期望值的计算更加复杂。而简单美妙的结论让我们不由得开始思考，这个问题有没有什么可以避免计算的巧妙思路？万万没有想到的是，在赌博问题的研究中，概率论帮了不少大忙；而这一回，该轮到赌博问题反过来立功了。
查看更多 »

    数学常数最令人着迷的就是，它们常常出现在一些看似与之毫不相干的场合中。 随便取一个 0 到 1 之间的数，再加上另一个 0 到 1 之间的随机数，然后再加上一个 0 到 1 之间的随机数⋯⋯直到和超过 1 为止。一个有趣的问题：平均需要加多少次，才能让和超过 1 呢？答案是 e 次。

查看更多 »

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

    IBM Ponder This上个月的题目比较有趣：我在心里面想一个2到166之间的整数（包括2和166），你的任务是用尽可能少的是非问句（我只能回答是或者否）猜出这个数除1以外的最小约数是多少。
    (1) 寻找一种策略使得在最坏情况下猜到答案的询问次数最少。
    (2) 寻找一种策略使得在平均情况下猜到答案的期望询问次数最少。

    第一个问题很容易回答。虽然2到166之间的整数一共有165个，但它们的最小约数（以后我们说的“最小约数”都是指的不包括1的最小约数）只有38种。因此，事实上你只需要用二分法在38个可能的答案当中找出一个就可以了。由于2^5=32，2^6=64，因此最坏情况下需要6次询问才能保证猜到。
    真正困难的是后面一个问题：要想让平均猜测次数尽可能少，我们该从哪里入手呢？

查看更多 »

    昨夜，M同学牵着女朋友的手走出宿舍楼，整夜没有回来；直到今天早晨，大家才见他支着腰回到寝室，样子十分疲惫。我们几个好友似乎已经心领神会，于是一行人走上前去，带着淫邪的笑容拷问他：昨晚干啥了，那么疲惫？本以为M同学会支支吾吾答不上话来，殊不知他义正严词地答道：我和女朋友去看通宵电影去了。几个人不服气，问他，那电影票呢？谁知他说了一句“忘了放哪儿了”后，还真煞有其事地在包里翻来翻去。一群人大笑着说，唉呀，你就别装了吧。两分钟后，我们全都傻了眼——M同学还真摸出两张电影票。一哥们儿猛地拍了一下M同学的肩膀说，唉呀，为了骗过我们真是煞费苦心啊，居然到影院门口找散场观众买了两张票根！
    笑过之后，我突然开始想，假如M同学为了掩饰自己的恶劣行径，真的准备好了伪证的话，他的演技可不是一般的高明。试着想象以下两个画面：

1. 几个人不服气，问他，那电影票呢？M同学不急不慢地从口袋里掏出两张电影票说，在这儿呢。
2. 几个人不服气，问他，那电影票呢？M同学假装到处寻找电影票，过了两分钟才翻出来。

    显然，第二种做法更令人相信，他真的跑去看通宵电影去了。事实上，M同学还能做得更好：

查看更多 »

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

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

查看更多 »

最近几天见到了几道零散的、不成系统的趣题，在这里合成一篇文章，与大家分享。

1. 证明：对任意正整数n，n^2+n+1一定不是完全平方数。

2. 说一个实数是可表达的，当且仅当它能用有限长的语句明确地描述出来，如2147483648可以说成是“二的三十一次方”，√2即为“平方后等于二的正实数”，π即为“圆的周长和直径之比”。问题是，是否存在一个不可表达的实数？

3. 一个人有两个小孩儿，其中有一个生于星期二的男孩儿。问另一个是男孩儿的概率是多少？

4. 无需积分，计算。

查看更多 »

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

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

查看更多 »