趣题:Kontsevich的单人跳棋游戏

           有一个无限大的棋盘,棋盘左下角有一个大小为 n 的阶梯形区域,其中最左下角的那个格子里有一枚棋子,如左图所示。你每次可以把一枚棋子“分裂”成两枚棋子,分别放在原位置的上边一格和右边一格。你的目的是通过有限次的操作,让整个阶梯里不再有任何棋子。下图所示的是 n = 2 时的一种解法。我们的问题是:对于那些 n ,这个游戏是有解的?       

Hofstadter的非线性递推数列

    在著名奇书 Gödel, Escher, Bach: An Eternal Golden Braid 的第五章中,为了展现出递推序列的神奇之处,作者 Douglas Hofstadter 定义了这么一个递推序列: G(n) = n – G(G(n – 1)) ,其中 G(1) = 1 。这个序列的前 30 项如下: n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 […]

用生命游戏来模拟生命游戏

    这是我前几天看到的一个视频。毫无疑问,它是我所见过的各种生命游戏构造中最神奇的一个:            在 LifeWiki 中有一个词条详细介绍了这个构造:它叫做 OTCA metapixel ,是由 Brice Due 在 2005 至 2006 年间构造的。其中,每一个 metapixel 的大小为 2048 × 2048 ,周期为 35328 。   视频出处:http://www.youtube.com/watch?v=QtJ77qsLrpw 查看更多:http://www.reddit.com/r/math/comments/lutec/l_i_f_e_c_e_p_t_i_o_n_or_how_to_simulate_the/ 如果你喜欢生命游戏,不要错过之前我们介绍过的史上最大的生命游戏构造—— Caterpillar 飞船

千万别学数学:最折磨人的数学未解之谜(一)

    数学之美不但体现在漂亮的结论和精妙的证明上,那些尚未解决的数学问题也有让人神魂颠倒的魅力。和 Goldbach 猜想、 Riemann 假设不同,有些悬而未解的问题趣味性很强,“数学性”非常弱,乍看上去并没有触及深刻的数学理论,似乎是一道可以被瞬间秒杀的数学趣题,让数学爱好者们“不找到一个巧解就不爽”;但令人称奇的是,它们的困难程度却不亚于那些著名的数学猜想,这或许比各个领域中艰深的数学难题更折磨人吧。     作为一本数学趣题集, Mathematical Puzzles 一书中竟把仍未解决的数学趣题单独列为一章,可见这些问题有多么令人着迷。我从这一章里挑选了一些问题,在这里和大家分享一下。这本书是 04 年出版的,书里提到的一些“最新进展”其实已经不是最新的了;不过我也没有仔细考察每个问题当前的进展,因此本文的信息并不保证是 100% 准确的,在此向读者们表示歉意。     这篇文章很长,大家不妨用自己喜欢的方式马克一下,一天读一点。

公平分割问题:均衡分割与免嫉妒分割

    大家或许都知道经典的两人分饼问题——为了实现公平性,只需要一个人切,另一个人选即可。不过,在现实生活中,情况远没有那么理想。如果把大饼换成蛋糕,问题就复杂了很多——你想吃奶油,我想吃巧克力,他想吃水果⋯⋯如果分蛋糕的人对蛋糕各部分的价值看法有分歧,还能实现公平的分割吗?如果分蛋糕的人不止两个呢?     事实上,对于两个人分蛋糕的情况,经典的“你来分我来选”的方法仍然是非常有效的,即使双方对蛋糕价值的计算方法不一致也没关系。首先,由其中一人执刀,把蛋糕切分成两块;然后,另一个人选出他自己更想要的那块,剩下的那块就留给第一个人。由于分蛋糕的人事先不知道选蛋糕的人会选择哪一块,为了保证自己的利益,他必须(按照自己的标准)把蛋糕分成均等的两块。这样,不管对方选择了哪一块,他都能保证自己总可以得到蛋糕总价值的 1/2 。     不过,细究起来,这种方法也不是完全公平的。对于分蛋糕的人来说,两块蛋糕的价值均等,但对于选蛋糕的人来说,两块蛋糕的价值差异可能很大。因此,选蛋糕的人往往能获得大于 1/2 的价值。一个简单的例子就是,蛋糕表面是一半草莓一半巧克力的。分蛋糕的人只对蛋糕体积感兴趣,于是把草莓的部分分成一块,把巧克力的部分分成一块;但他不知道,选蛋糕的人更偏爱巧克力一些。因此,选蛋糕的人可以得到的价值超过蛋糕总价值的一半,而分蛋糕的人只能恰好获得一半的价值。而事实上,更公平一些的做法是,前一个人得到所有草莓部分和一小块巧克力部分,后面那个人则分得剩下的巧克力部分。这样便能确保两个人都可以得到一半多一点的价值。     但是,要想实现上面所说的理想分割,双方需要完全公开自己的信息,并且要能够充分信任对方。然而,在现实生活中,这是很难做到的。考虑到分蛋糕的双方尔虞我诈的可能性,实现绝对公平几乎是不可能完成的任务。因此,我们只能退而求其次,给“公平”下一个大家普遍能接受的定义。在公平分割 (fair division) 问题中,有一个最为根本的公平原则叫做“均衡分割” (proportional division) 。它的意思就是, 如果有 n 个人分蛋糕,则每个人都认为自己得到了整个蛋糕至少 1/n 的价值 。从这个角度来说,“你来分我来选”的方案是公平的——在信息不对称的场合中,获得总价值的一半已经是很让人满意的结果了。