Kolakoski序列：我们知道的还是太少

2011 年 5 月 4 日 / 34 条评论

上帝创造了整数，其余的则是我们人类的事了。正因为如此，质数、完全数、Fibonacci 数之类的数列才会让数学家们如痴如醉，因为它们的存在是如此自然，没有任何人造的因素。事实上，数学家们对这些数的认识也越来越丰富，挖掘出了这些数列中越来越深刻的性质。

不过，人类确实太渺小了。还有好多构造异常简单的“纯天然数列”，我们了解得实在太少。Kolakoski 数列就是最好的例子之一。

Kolakoski 数列仅由 1 和 2 构成，其中头 100 个数是

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1,
2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1,
1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2,
1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2,
2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, …

Arrow不可能性定理：独裁是唯一完美的选举制度

2011 年 4 月 10 日 / 64 条评论

由于某些原因，最近在整理以前的日志。偶然翻到这篇日志时，顺便在 Wikipedia 复习了一下 Arrow 不可能性定理的证明，惊奇地发现这个定理的证明过程非常困难但又非常初等，是一个门槛很低、老少咸宜的思维游戏。虽然不少人都翻译过 Wikipedia 上的这段证明，但我也想自己写一个自己的理解，一来做个笔记，二来也锻炼一下自己的表达能力。

Arrow 不可能性定理是一个与选举制度有关的定理。选举制度，说穿了就是把所有选民的意见综合成一个全体意见的算法。选民的意见，无非是候选对象在心目中谁优谁劣，完整地反应在选票上，就是候选对象们从优到劣的一个顺序；形式最完整的全体意见，也就是候选对象的这么一个排列。因此，我们可以把整个选举制度想像成一个函数，输入 n 个排列（相当于 n 张选票），将会输出一个排列（相当于选举结果）。对输入数据的任何一处小改变，都有可能导致输出结果随之变化。作为一个合理的选举制度，它必须满足一些起码的要求。我们提出两个最基本的选举制度要求：

1. 如果每张选票都认为 X 比 Y 好，那么投票结果中 X 的排名也必须比 Y 更靠前；
2. 如果每张选票中 X 、 Y 的相对排名都不改变，那么投票结果中 X 和 Y 谁先谁后也不能变。

我们将证明，同时满足上述两个条件的选举制度只有一种，就是选举结果唯一地由其中某个选民的选票决定。也就是说，独裁是唯一一种完美的选举制度。为了简便起见，让我们假设候选人只有 A 、 B 、 C 三个人。你会发现，下面的证明过程很容易扩展到多个人的情况。

比Conway生命游戏更酷的Langton蚂蚁

2011 年 3 月 22 日 / 67 条评论

不知道有多少人已经熟知 Conway 的生命游戏，但却从没听说过 Langton 的蚂蚁游戏？反正我是其中之一。直到今天我才听说了这个比生命游戏更酷的游戏—— Langton 的蚂蚁。这也是一个二维自动机形式的零玩家游戏，不过我觉得它比生命游戏有趣得多。这有两个理由：

1. 它的算法过程更简单。初始时，蚂蚁位于一张空白画布的某个方格里。如果当前蚂蚁在白色方格上，则对当前方格反色，左转 90 度，前进一格；如果当前蚂蚁在黑色方格上，则对当前方格反色，右转 90 度，前进一格。如此反复。

漫话折纸几何学

2011 年 2 月 24 日 / 37 条评论

前几天，一篇叫做用正方形纸片折出等边三角形的日志引起大家的讨论，折出正七边形和折出角三等分线的方案更是让大家争论不休。提得最多的问题就是，折纸为什么要比尺规作图更强？这是一个好问题。我查了不少资料，了解到不少折纸几何的历史，收获颇大，不赶紧记下来就亏大了。于是有了这篇文章。

要解答为何折纸如此强大，首先我们得解决一个问题：什么叫折纸。折纸的游戏规则是什么？换句话说，折纸允许哪些基本的操作？大家或许会想到一些折纸几何必须遵守的规则：所有直线都由折痕或者纸张边缘确定，所有点都由直线的交点确定，折痕一律是将纸张折叠压平再展开后得到的，每次折叠都要求对齐某些已有几何元素（不能凭感觉乱折），等等。不过，这些定义都太“空”了，我们需要更加形式化的折纸规则。 1991 年， Humiaki Huzita 指出了折纸过程中的 6 种基本操作（也可以叫做折纸几何的公理）：