最近看到了一个有趣的问题Gossip Problem。假如我们班有n个MM，每一个MM都有一个独家八卦消息。两个MM可以通过电话联系，一通电话将使得双方都获知到对方目前已知的全部消息。要想所有n个MM都知道所有n条八卦消息，最少需要多少通电话？
    一个最简单的办法就是从n个人中选一个消息汇总人，所有n-1个人都打电话给她，她再打电话给所有人。这样总共需要2n-2通电话。其实，汇总阶段的最后一通电话和发布阶段的第一通电话可以合并为一通电话，这样的话该方案实际上只需要2n-3通电话。打电话的次数还能更少吗？给出一个最优解，并证明这个数目已经不能再少了。

 
    显然，n=2时只需要一通电话，n=3时必须要3通电话。当n=4时，可以让AB互相通话，CD互相通话，此时每个人都知道了（包括自己的）两条消息；然后A和C通话，B和D通话，从而使得每个人都获知另外两条自己还不知道的消息。显然，对于4个人的情况，4通电话已经是最少的了。
    对于n>4的情况，有一种算法可以保证在2n-4通电话内解决问题。首先，选出4个人作为消息汇总人。其余每个人都选择一个汇总人并与之通话；然后4个汇总人再用4通电话互相更新一下消息（用刚才n=4的办法）；最后4个汇总人把电话再打回去，实现所有消息全部共享。下面我们证明，2n-4已经是最少的了。证明方法很多，也都很复杂。最常见的证明由Brenda Baker和Robert Shostak在1972年给出。

查看更多 »

    很多问题并不完全符合二分的模型。最常见的一个情况估计应该是无穷长的有序队列中的二分查找问题。例如，前文所提到的求解x^x=a实际上就是这样的问题，这里x的取值范围可以是大于0的所有实数。当然，这里的x明显有一个上界，比如x明显要比a小。但是，如果有什么二分问题，它没有一个明确的上界呢？比如，我们再玩一次猜数游戏，我想一个数，然后告诉你你的猜测是大了还是小了。不同的是，我不告诉你这个数是在什么范围内选的，我想的数可以是任意一个正整数。那你该怎么办呢？最初的想法当然是，不断往大的猜，直到某个时候它超过了目标值为止；然后以它为上界，剩下的就可以看作有限多了。关键是，我们以什么样的跨度来枚举这个上界？首先必须肯定的是，这个上界枚举序列必须是发散的，否则会有数我们一辈子也猜不到；同时，线性增长的策略也是很傻的：跨度太小了你可能得到猴年才能找出上界，跨度太大了的话一来就确定了上界，但待考虑的队列也可能远远超过所需。一个比较灵活的想法是：按照1, 2, 4, 8, 16, ..., 2^n的序列来猜测上界。这是一种“相对大小”的思想：既然连前面N个数都小了，我们也就不在乎那么一两个了，不妨直接再跳过N个数直接考察2N。这样的话，整个猜测过程仍然保持log(n)的复杂度，整个算法也更加美观一些。

    假如你有一台时光机，可以让你到任意远的未来去，你打算怎么来使用它？或许你会说，先去100年后看看，生活一年之后再去200年后体验体验，然后再去300年后生活一年，再去400年后生活一年……其实，这种线性的时光旅行并不科学。当你已经跨越了数千年以后，相比之下100年的跨度已经不算遥远了，1000年后与1100年后的差异远远没有今天和100年以后的变化那样令人震撼。我说我和Stetson MM的思维如出一辙，那不是说着好玩的。一次MSN聊天时我们讨论到这个话题，两人同时想到了这样的时间旅行方式：先直接跳到1年后生活，再到2年后生活一段时间，再到4年后，再到8年后……用这种方式来体验未来，即使我在每一个时间点停留一年，我也能保证见到从我余生的感情生活到人类文明的各种不可思议的形态，甚至到文明的轮回与宇宙的毁灭等各种尺度下的牛B事。我的确能够看到充分远的未来，了解到足够宏大的文明史和宇宙史：假设我还能活80年，那么我可以看到2^80=1208925819614629174706176年内的种种，这么多年里估计就是宇宙热寂也该结束了。
    折纸后的高度、在棋盘里放米、Hanoi塔与世界末日……无数火星的例子告诉我们，倍增的力量是异常强大的。如果你不信的话，下次来北京时请我喝酒，不妨这样来试试：先我喝一杯，你喝一口；然后我喝一杯，你喝两口；然后我喝一杯，你喝四口……看咱俩谁坚持的久。

查看更多 »

  来源：http://brownsharpie.courtneygibbons.org/?p=808

    严重剧透警告！！这篇日志涉及到Saw V的一个非常非常科学的twist，打算看Saw V但是还没看的同志们别进来！！
    严重剧透警告！！这篇日志涉及到Saw V的一个非常非常科学的twist，打算看Saw V但是还没看的同志们别进来！！
    严重剧透警告！！这篇日志涉及到Saw V的一个非常非常科学的twist，打算看Saw V但是还没看的同志们别进来！！

查看更多 »

    看完Proofs from THE BOOK的几何部分，我决定把书又放一放，开始阅读Infinity and the Mind。我承认我不该在当代文学史课上读这本书——读到第15页时，我看到了一段非常有趣的文字，竟然在课堂上放声大笑出来。不知道大家之前是否见过这个“思维实验”，我好像是第一次见到，它真的好搞笑。
    历史上，不同的人对宇宙空间有着不同的见解。古罗马哲学家Lucretius认为，宇宙是无限的。让我们来看一看他的经典论证。假设宇宙是有限的。我们往宇宙的边界投掷一根标枪。则我们将看到以下两种情况之一：这根标枪穿过边界飞向远方，这说明宇宙并无边界，它是无限的；或者这根标枪一头装上宇宙边界停了下来，这说明边界外“有东西”挡住了标枪，同样说明宇宙是无界的。

Update: 其实我想说的是，笑点不是古人的论证与现代科学的差距，而是论证自身用到的二难性所带来的滑稽效果与逻辑推理出奇宏大的力量；正如证明上帝不是万能的（上帝能否创造一块连自己也举不起来的石头），或者大球小球落下去的速度一样快之类的思维实验，它们总是让人会心一笑。

    有些时候，数学模型和物理世界相结合可能会得出一些不可思议的悖论，Gabriel喇叭就是最经典的例子。这里，让我们来看另一个有趣的例子。

  
    假设有一个无穷大的桌面，上面垂直地树立着一根有限长的金属杆。在这根金属杆的顶端用铰链连接一根无穷长的金属杆。这根无穷长的金属杆可以绕着活动关节处上下转动。让无穷长的金属杆随重力自由活动。注意到夹角α绝对不可能小于90度，因为我们的金属杆和桌面都是理想刚体，它们不能相交、穿透。这样的话，α只可能是90度。于是，荒唐的一幕发生了：这根无穷长的金属杆平行地悬在桌面上空，但却只有端点处这一个支撑点。

来源：http://www.cut-the-knot.org/WhatIs/Infinity/InfiniteRod.shtml

    大家都知道，三角形具有稳定性。如果你把三根木条钉成一个三角形，则这几根木条是不能活动的。这是因为，根据三角形的SSS全等判定法则，两个三角形的三边长对应相等，则这两个三角形一定全等。但四边形就不是了，用四根一样长的木条钉成一个正方形，握着相对的两个角往两边一拉，正方形就变成菱形了。不知道大家想过没有，类比到三维空间中，多面体的稳定性又是怎样的呢？
    Cauchy定理指出，如果两个凸多面体对应的面全等，那么这两个多面体全等。这告诉我们，任何一个凸多面体一定都是不可活动的。在Cauchy定理中，“凸多面体”这一条件是必需的。如果允许凹的多面体存在，对应面相等但整个多面体不全等的形状可以很轻易地构造出来。例如，想象立方体的某个面中心有一个小金字塔，这个金字塔既可以是向外凸的（就像表面上的一根刺），也可以是向内凹的（表面上的一个坑）；这是两个截然不同的多面体，但它们的对应面都是相等的。不过，这与我们的稳定性并没有关系，因为它并不是做连续的变形，而是直接一下就“跳”过来了。
    很长一段时间，人们曾经猜想，不存在可以做出连续变形且保持所有面不变的“可活动多面体”(Flexible Polyhedron)。1978年，Connelly找到了第一个反例。他给出了一个由18个面组成的可活动多面体。

查看更多 »

    历经四年多的单身生活后，本Blog经常提到的，在我们系我们年级的一个和我纠结了大半年的，被我称为古汉MM的，最近几乎每篇日志下面都会以“燕仰”为名留下评论的MM，半个月前正式和我走到了一起。在学术方面，古汉MM和我几乎是两个极端，我们俩最终能走在一起真是一个奇迹。她在文学方面是一个巨牛，今后我亲爱的她将会在www.matrix67.com/yanyang写一个文学随想类的Blog，希望大家能够喜欢并帮忙宣传。不管最后结局如何，这个Blog都会一直更新下去。
    好啦，废话不多说了，大家开始疯狂留评论吧……

Update: 承诺在下星期内向大家交代详情，并在再下周发pp
Update: 最近忙，承诺怕是兑不了现了……