下面大家将会看到的是一个极其简单而又极其复杂的“迷宫”，这无疑是我在本年度见到的最变态的谜题：从左边入口处的 2011 进去，在迷宫里转悠，最后变成 2012 从右边出来。你可以在迷宫里转圈，可以重复之前走过的路，但不能往回退着走。

    你能成功走出来吗？

查看更多 »

    左图是一个凹多边形，而且凹得相当厉害。作为一个完美主义者，我很难容忍这么一个图形，总想着要把凹进去的部分翻出来，把它还原为一个凸多边形。不幸的是，翻折之后的结果仍然不是凸多边形，图中又产生了新的凹陷。于是，我们想继续把凹进去的部分往外翻，直到整个图形变成凸多边形为止。问题是，这个过程有完吗？换句话说，我们一定能通过有限多步翻折，把凹多边形变成凸的吗？

    这个问题有着非常纠结复杂的历史。这个问题最早可能是由数学家 Paul Erdős 正式提出的。 1935 年，他在 American Mathematical Monthly 上猜想，经过有限步翻折之后，凹多边形一定能变凸。 1939 年， Béla Szőkefalvi-Nagy 给出了一个证明。因此，这个结论又叫做 Erdős-Nagy 定理。有趣的是，这个问题是如此的自然，以至于在此之后，又有一大堆人重新提出并研究了这个问题，而且他们明显并不知道相互之间的已有研究。这事儿给我们带来的好处就是，我们有了 Erdős-Nagy 定理的好几种截然不同的证明方法。不过，这些证明或者太长，或者太高深，或者又有些漏洞。 1999 年， Godfried Toussaint 从这些证明中取长补短，给出了一个比较初等的证明。

查看更多 »

    去年年初的时候，我曾经发布过某专业课期末作业研究过程中带来的一个有趣的副产品：汉字的字义网络图。不过，当时我是直接调用的 Mathematica 的相关函数，函数几乎不能调整参数，并且也无法处理边上权重不同的情况。最近在研究引力斥力绘图算法，突然想到把当时的数据重新画一张图。于是就有了汉字地图第二版（点击小图看大图）：

查看更多 »

    一个小镇上即将进行大选，候选人有 m ≥ 3 个，选民一共有 n 人。选举时，每个选民在选票上写下一个候选人的名字，然后由计算机根据某种选举机制算出大选的获胜者来。如果把 n 个选民的选票依次记为 x₁, x₂, ..., x_n 的话，那么选举机制的算法其实就是一个映射到 {1, 2, ..., m} 的函数 f(x₁, x₂, ..., x_n) 。

    为了保证选举程序的公平性，让每个人手中的选票都能发挥作用，政府提出了“差异性原则”：如果每个人的选票都变了，那么竞选的获胜者也应当改变。也就是说，如果对于所有的 i 都有 x_i ≠ y_i ，那么必有 f(x₁, x₂, ..., x_n) ≠ f(y₁, y₂, ..., y_n) 。选票系统的算法虽然不是透明的，但政府保证，这个算法满足差异性原则。

    差异性原则真的能够保证，每个选民的选票都有足够的权力吗？不是。差异性原则看似很强，但实际情况则是，它不但不能保证每张选票都能影响选举结果，甚至还无法避免有选民独裁选举结果的现象发生。更不可思议的是，事实上独裁现象是必然会发生的——独裁是差异性原则的必然推论！下面我们将证明，对于任意一种满足差异性原则的选票算法，我们都能找到这样一个选民，他的选票独裁了选举结果，获胜者是谁完全由他的选票决定，与其他人的选票无关。

查看更多 »

    在集合 {1, 2, ..., n} 中选出尽可能多的子集，使得每个子集所含的元素个数都是奇数，但是任意两个子集的交集都含有偶数个元素。那么，我们最多能够选出多少个这样的子集来？

    容易看出，我们至少可以选出 n 个子集。例如，当 n = 4 时， {1} 、 {2} 、 {3} 、 {4} 就满足要求。我们还能选出更多的子集来吗？简单地尝试后，你会觉得似乎不行。不过，这却并不是显然的，因为存在一些不那么平凡的方案，也能让子集的数量达到 n ，例如 {1, 2, 3} 、 {1, 2, 4} 、 {1, 3, 4} 、 {2, 3, 4} 这 4 个子集也是满足要求的。看来，证明最多只能选出 n 个子集，好像并不那么容易。

查看更多 »

    n 个小朋友在圆桌上坐成一圈。初始时，每个小朋友都拥有一定数量的糖。接下来，反复进行下面两个操作：

      1. 如果有人手里的糖数是奇数，就向老师再要一颗糖，把手里的糖数补成偶数；
      2. 每个人都把自己手中一半的糖传给他右边的人（同时接到从左边传过来的糖）。

    证明：总有一个时刻，所有小朋友手中都会拥有相同数量的糖。
    附加题：这是一个非常经典的问题。猜猜看我最早在什么地方看到的这个问题？

查看更多 »

    这是我前几天看到的一个视频。毫无疑问，它是我所见过的各种生命游戏构造中最神奇的一个：

    在 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 飞船

    这篇文章收录了 Which Way Did the Bicycle Go 趣题集中一个非常有趣的问题：是否有可能在平面上画不可数个不相交的 8 ？答案是否定的。证明方法非常简单。对于任意一个 8 字形，在两个洞里各取一个有理点 P 、 Q （由于平面上的有理点是稠密的，这是总能办到的），则称这个 8 字形圈住了有理点对 (P, Q) 。注意到由于 8 字形不能相交，因此两个 8 字形不可能圈住同一对有理点。由于平面上的有理点对是可数的，因此 8 字形的数量也是可数的。

    注意到，平面上显然能够容下不可数个不相交的直线段，也显然能够容下不可数个不相交的圆（比方说一系列同心圆）。在 Mathematical Puzzles 一书里， Peter Winkler 提出了这样一个问题：我们能在平面上写下不可数个不相交的字母 Y 吗？

查看更多 »