2011年度最变态的迷宫难题

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

      

    你能成功走出来吗?

Read more…

经典证明:不断把凹的部分翻出来,总能把凹多边形变凸吗?

      

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

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

Read more…

汉字地图第二版

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

   

Read more…

如此保证选举公正性能成吗?

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

    为了保证选举程序的公平性,让每个人手中的选票都能发挥作用,政府提出了“差异性原则”:如果每个人的选票都变了,那么竞选的获胜者也应当改变。也就是说,如果对于所有的 i 都有 xi ≠ yi ,那么必有 f(x1, x2, …, xn) ≠ f(y1, y2, …, yn) 。选票系统的算法虽然不是透明的,但政府保证,这个算法满足差异性原则。

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

Read more…