数学、物理、化学、生物等基础学科虽然对人类的生产生活贡献很大，但并不是每个人每一天都会用到。另一些学科则与每个人的生活都有着密切的联系，但人们往往并没有意识到。其中有三门学科尤其贴近人们的生活：经济学、统计学和信息学。这三门学科从不同的角度解析生活中的种种现象，代表了三种不同的科学思维方式，是人生中的三门必修课。很可惜，并不是所有人都有机会一睹这三门学科的风采，即使理解它们并不需要太多的基础知识。
    我很高兴地看到，最近市面上出现了一些与统计学和经济学相关的普及读物。它们以浅显易懂的文字向读者揭示事物背后的科学道理，让每个人都有机会领略到统计学和经济学的魅力。但是，我目前还没找到任何一本与信息学相关的普及读物。于是，我萌生了自己写一本信息学普及读物的念头。我想把自己近几年来对算法的感悟写下来，让越来越多的人体会到算法的科学性、趣味性和实用价值。
    这里特别要感谢周筠老师和徐定翔老师，是你们的支持和鼓励才让我真正下定了写书的决心。当然，还要感谢长期支持这个网站的网友们。在以后的写作过程中，我可能会有偿向大家征集好的建议和主意，希望能够靠众人的力量收获最巧妙、最有趣、具原创性的点子。

查看更多 »

    说有一个潜水艇，初始时位于数轴上的某个整数点，并沿着数轴以每秒整数个单位的速度做匀速运动（但你不知道具体的初始位置和移动速度是多少，移动方向也是未知的）。每一秒你都可以在某个整数点投放深水炸弹，如果此时潜艇正好在你放炸弹的位置，这个潜艇就被炸掉了。你是否有办法可以保证炸毁潜艇？

    这是可以办到的。不管初始时潜水艇在哪儿，它的速度有多大，我总能在有限的时间里炸毁潜艇。假设潜艇的速度为 a ，初始位置为 b ，则在第 t 秒时它的位置就在 a*t + b 。把所有可能的有序数对 (a,b) 看作是平面直角坐标系上的整格点，每次考虑其中的一个点；假设第 i 秒考虑的点是 (a_i, b_i) ，那就在 a_i * i + b_i 处放一个炸弹。如此重复做下去，每次排除一种情况，直到击中目标为止。现在的问题就是，用怎样的顺序遍历平面上的所有格点才能保证每个 (a,b) 都会在有限的时间里访问到。这个方法就多了，比如从原点开始以一条螺旋线为路径一圈一圈地遍历周围越来越远的点。

    这个问题展示了一些典型的数学思维在传统智力题方面的应用，它背后的数学方法非常深刻。

 
来源：http://www.reddit.com/r/math/comments/as2d5/sinking_the_submarine_a_puzzle/

    搞过 OI/ACM 的同学们想必对一道经典题目印象极深：求 n 的阶乘末尾有多少个 0 。注意到末尾的一个 0 是由一个因子 2 和一个因子 5 相乘产生的；但在 n 的阶乘里，因子 5 的个数通常远远少于因子 2 。因此这个问题就等价于问 n 的阶乘里有多少个因子 5 。在 n 的阶乘式中，每个 5 的倍数里都含有一个因子 5 ，每个 25 的倍数里都还含有另外一个因子 5 ，每个 125 的倍数里都还有第三个因子 5 ……因此， n 的阶乘里因子 5 的个数的计算公式就是 ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ... 。如果把 K 的阶乘里素因子 p 的个数记作 Φ(p, K) ，则 Φ(p, K) = Σ⌊K/(p^i)⌋ 。有意思的是，最近 The American Mathematical Monthly 上的一篇文章利用这个公式瞬间证明了素数无穷多的定理。

    如果素数是有限的，则 K 的阶乘就可以写成所有 p^Φ(p, K) 的乘积，其中的 p 取遍所有的素数。注意到 Φ(p, K) = Σ⌊K/(p^i)⌋ < Σ(K/(p^i)) = K/(p-1) < K ，因此对任意正整数 K 都有 K! < (Πp)^K ，其中 Πp 表示所有素数的乘积。但当 K 充分大的时候， K! 显然会超过一个常数的 K 次方，矛盾。因此素数不可能是有限的。

 
来源：http://www.cut-the-knot.org/wiki-math

原来一直在想，有没有什么物理手段可以得到分形图形，没想到还真有。
看上去确实很帅。

视频来源：http://www.youtube.com/watch?v=S5-U8bazU7E
查看更多：http://tesladownunder.com/LowVoltagePower.htm#Wood%20burn%20fractals

    UyHiP上个月的题目：把所有大于 1 的自然数划分成两个集合，证明至少能在其中一个集合里找到互不相同的三个数 a 、 b 、 c 满足 a^b=c 。然后，试着给出一种划分，使得只有其中一个集合里存在这样的三元组。
    Update: 后一个问题要求两个集合都是无限集。感谢网友 Triple.J 的提醒。

    证明：如果集合 A 里只有有限个数，那就在集合 B 里选两个比集合 A 中的最大数还大的数 a 和 b ，显然 a^b 也在集合 B 里。类似的，若集合 B 里只有有限个数，我们立即可知 A 中存在满足 a^b=c 的三元组。因此，我们只需要讨论两个集合里都有无穷多个数的情况。
    从集合 A 里选一个数 x ，从集合 B 里选一个数 y 。无妨假设 xy 在集合 A 中。在集合 A 中选一个比 xy 大的数 r 。由于集合 A 是无限大的，因此这样的数总存在。由于 r 比 xy 大，因此 x 、 y 、 xy 、 r 、 r^x 、 r^(xy) 这六个数两两不同。为了避免在同一集合里出现满足要求的三元组， r^x 和 r^(xy) 都必须在集合B里面，但这样的话， r^x 、 y 和 r^(xy) 就成了符合要求的三元组了。
    后一个问题则出奇的简单：把所有素数放进一个集合，所有合数放进另一个集合。显然，一个素数不可能是另一个素数的整数次幂
。

    这个月的题目非常有意思，点击这里围观。

    语言统计分析期末大作业要求我们统计全唐诗中的对偶字，并用所得到的统计结果反过来评判出对仗最工整的诗句。我在数据处理过程中突然想到，鉴于互成对偶的两个字之间有一定的语义联系，我们便有了一个庞大的汉字语义关联库；如果把所有汉字之间的关联画成一张图会是什么样子呢？于是我用 Mathematica 7 提出了全唐诗中处在对偶位置上的所有字对，得到了 464448 个可能的对偶关系；再利用一些算法得到了最稳定、最常用的 2000 个对偶关系，把它们都描绘在一张大图上，于是便有了上面的这个图。点击这里查看高清无码大图，1600x1600 像素。可以看到，有语义关联的汉字自动地聚合到了一起。

查看更多 »

图片来源：http://xkcd.com/688/
真是太有才了！

    The Bottle Imp 是一则有意思的短篇小说。某日，小说里的主人公遇上了一个怪老头。怪老头拿出一个瓶子，说你可以买走这个瓶子，瓶子里的妖怪就能满足你的各种愿望；但同时，持有这个瓶子会让你死后入地狱永受炼狱之苦，唯一的解法就是把这个瓶子以一个更低的价格卖给别人。如果你是小说里的主人公，你会不会买下这个瓶子呢？你会以什么价格买下这个瓶子呢？
    以什么价格买入这个瓶子，这个问题貌似并不容易回答。你当然不愿意花太多的钱，在你的愿望被满足之前你至少还得给自己留一点钱花；但你也不能花太少的钱，否则你会承担着卖不出去的风险。但是，在做出一些理性的分析后，我们得出了一个惊人的结论：任何人都不应该以任何价格购买这个瓶子。
    和很多博弈问题一样，这一系列的分析首先从最简单的情形开始。首先，你是绝对不能只出 1 分钱就买下这个瓶子的，因为这样的话这个瓶子就永远也卖不出去了——没有比 1 分钱更低的金额了。那么，用 2 分钱买瓶子呢？这样理论上貌似是可行的，但仔细一推敲你会发现还是有问题——这样你只能以 1 分钱卖掉这个瓶子，但没有人会愿意用 1 分钱去买瓶子（否则他就卖不掉了）。因此，用 2 分钱买下瓶子后，你同样找不到下一个买家。和上面的推理一样，用 3 分钱买这个瓶子也不是什么好主意，因为没有人愿意以 1 分钱或 2 分钱购入瓶子，因此你的瓶子不可能卖得掉。依此类推，你不应该以任何价钱去购买这个瓶子，因为每个人都知道，他无法以任何价格卖掉这个瓶子。

查看更多 »