最近看到了一个有趣的问题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年给出。

Read more…

    很多问题并不完全符合二分的模型。最常见的一个情况估计应该是无穷长的有序队列中的二分查找问题。例如，前文所提到的求解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塔与世界末日……无数火星的例子告诉我们，倍增的力量是异常强大的。如果你不信的话，下次来北京时请我喝酒，不妨这样来试试：先我喝一杯，你喝一口；然后我喝一杯，你喝两口；然后我喝一杯，你喝四口……看咱俩谁坚持的久。

Read more…

    二分思想真的是无所不在，即使在中文系的专业课中我们也能见到这个词。在语言学概论中我们提到，一个音位可以由一组区别特征确定下来，这些区别特征总是以只具有“是/否”、“有/无”等两种对立属性的“二元偶分组”形式存在，因为这样可以最方便最快捷地确定出一个元素。这有点像猜数字一样，我想一个数字后让你来猜，我告诉你你的猜测是大了还是小了。只是在这里，回馈的信息不再是大小，而是“辅音/元音”、“口音/鼻音”、“浊音/清音”、“送气/不送气”等形式逐层细分。这让人联想到5张卡片猜年龄的老把戏，一系列火星的称球问题，基于比较的排序算法的复杂度下界，或者经典的20q在线游戏。
    一个有趣的事实是，相当多的人都错误地理解了“二分”这个词，但他们在生活中却拥有很强的二分意识。我们语言学概论的老师（这里就不说是谁了）在讲解二分时举了一个甚为荒谬的例子：如果你要在房间里找一根针，那么你可以把房间划分为两半，如果这一半找不到的话说明针一定在房间另一半，此时再把那一半分成两部分，不断分分分分分最后总能找到针的位置。这是这位老师无数荒唐的例子中的冰山一角，因为这个“二分”与搜索别无二致。这个“二分”的判断环节并不是即刻返回的，而且最关键的是它并不具有规模减半的功能，或者说一旦返回“真”后我们并不会再接着二分下去。如果让我来举例子的话，同样是拿找东西打比方，在合唱队中找出跑调了的人是一个绝佳的例子，因为在合唱中我们能轻易分辨出一个不和谐的声音（虽然无法准确判断这个声音是从哪儿传来的），不断叫当前的人的其中一半来合唱便可渐渐判断出那个人的位置。但讽刺的是，这老师在举这个错误例子的同时，竟然在不自觉地用二分法来调整课件的字号。他发现这一页ppt的字号太小了，我们可能看不清，于是希望让字号尽可能的大但又不致于大到显示不下。他开始尝试40号，发现字已经超出屏幕了；然后把字体改成20号，又觉得还能再大一些；进而又改到28号（工具栏上的字号调整以4为步长），最后确定到了24号字。

    如果真的叫一个课讲的好的老师来说二分，课程可以变得相当有意思。每次回我们高中时我都讲了很多次课，我最喜欢聊到的话题之一就是二分。从猜数游戏引入二分查询有序队列中的指定元素，然后提出一些标准的有序队列二分搜索的实际应用，比如解方程x^x=100一类的问题。紧接着提出二分的各种有趣的变形，例如如何在有序整数序列中查询A_i=i的元素。提出这些问题的目的就在于告诉大家，二分的思想不仅仅是用在猜数游戏一类的情况下。二分判断并不只限于“比目标值大/比目标值小”，只要能判断出目标值在哪边都行，例如在这里，A_i<i表明目标元素一定还在右边，A_i>i则表明目标元素在左边。

 i  =    1   2   3   4   5   6   7   8   9   10
A_i = -100 -20  -3   0   2   6  13  14  27  298

Read more…

    一个完全图K_n是指一个有n个顶点的图，其中每两个点之间都有一条边相连。一个完全二分图是指这样一种图，图中的顶点分为两个点集L和R，L里的每个顶点都和R里的所有点相连。上图显示了一种把K_5划分为四个完全二分图的方法（分别用红蓝绿灰四种颜色来表示这四个子图）。你觉得，最少可以把完全图K_n划分成多少个完全二分图？给出一种划分方案，并证明这个数目已经不能再少了。

Read more…

    作为一个UyHiP的忠实粉丝，我决定把上个月的题目和解答翻译过来，即使类似的把戏我们之前已经见到过了。
    题目就一句话：根号2和根号3的和的1948次方的小数点后第48位是多少？如果你立即就想到了正确算法的话，我敢保证在别人还没打开Mathematica的时候你就已经得到答案了。

    这道题背后隐藏的把戏就是，(√2 +√3)^1948 + (√2 -√3)^1948永远是一个整数，因为展开之后偶数次幂本来就是整数，而奇数次幂的项恰好又正负互相抵消了。注意到√3 -√2只比0.3多一点，因此(√2 -√3)^1948是一个很小很小的数，粗略估算一下的话它小数点后面紧跟着好几百个“0”；而前面说了(√2 +√3)^1948和(√2 -√3)^1948加起来是个整数，那么前者的小数点后必然有相当长的一段数字9。保守估计的话，不但(√2 +√3)^1948小数点后的第48位是“9”，就是480位也是“9”。事实上，这个数的小数点后面900多位都是“9”。