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

2011 年 4 月 10 日 / 64 条评论

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

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

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

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

UyHiP趣题：如果每个人都随大流，结果会怎样？

2011 年 4 月 4 日 / 22 条评论

一个公司里有 n 个员工，其中某些员工之间有“好友”的关系（这是一个对称的关系）。每天早晨来到公司，员工们都会从茶和咖啡中选择一样作为早饮。此时，每个员工都会观察自己的朋友们都在喝啥：如果超过一半的人都在喝茶，第二天他自己也会跟着喝茶；如果超过一半的人都在喝咖啡，第二天他自己就会跟着喝咖啡；如果喝茶喝咖啡的人数各占一半（仅当他有偶数个朋友时才会发生这种情况），则第二天他的决策不变，继续喝自己今天喝的东西。
由于 n 个员工一共只能产生 2ⁿ 种不同的早饮组合，因此总有一天大家喝的东西会和过去的某一天一模一样，从而产生循环。证明：循环的长度不超过 2 。

UyHiP趣题：拉灯游戏总有解吗？

2011 年 4 月 2 日 / 30 条评论

某公司有 n 间办公室。每间办公室都有一盏灯，拉动它的开关即可改变电灯的状态。某些办公室之间存在“业务相关”的关系（这是一个对称的关系）。一个办公室可以和 0 到任意多个办公室相关。愚人节那天，有人在大家上班之前偷偷对办公室的电灯开关做了手脚：拉动任何一个办公室的电灯开关，都会同时改变该办公室以及所有相关办公室的电灯状态。初始时，所有灯都是关着的。证明：等到大家来上班后，总能用有限次的开关，最终把所有办公室的灯都打开。

UyHiP趣题：限制最苛刻的选票统计程序

2011 年 3 月 16 日 / 32 条评论

因为忙，不少计划写下来的东西都一直搁置着。其中一个拖了很久都没写的就是 UyHiP 一月的题目了。这是一道看上去非常困难的算法题目，当时我没能解答出来；看到答案后才恍然大悟，拍案叫绝。这是一道非常少见的算法好题，在这里记下来。

一个国家里有 N 个公民，这些公民从 1 到 N 依次编号。这是一个民主国家，国家做出的每个决定都需要全体公民投票，每个人必须且只能投一票。

不过，随着该国家人口数量的增加，这种投票方式的效率越来越低。于是，这个国家实行了一种新的民主制度。每过四年，这个国家将会举行一次“代表选举大会”，届时，每个公民都必须且只能提名一个他信得过的人，来作为他自己的代表。注意，提名自己作为自己的代表也是允许的。对于每个被提名了的人，有百分之多少的人提名他，他就拥有了相当于多少张选票的权力（向下取整）。在接下来的四年里，国家要做出某项决定时，就只需要这些代表来参加了。

比方说，这个国家有 200 个人，在代表选举大会上，有 98 个人提名 1 号公民当代表，有 101 个人提名 2 号公民当代表，有 1 个人提名 200 号公民当代表。结果就是，只有 1 号公民和 2 号公民成为代表，在接下来的四年里参与投票，其中 1 号公民一票当 49 票，2 号公民一票当 50 票。值得注意的是， 200 号公民虽然有提名，但支持率仅 0.5% ，因此他今后四年没有当代表的权力。

量纲法竟然还能这样用

2011 年 2 月 20 日 / 37 条评论

公式 h = (1/2)·g·t^2 里， t 头上的平方并不奇怪。显然，物体下落的路程是与重力加速度 g 和时间 t 有关的，高度 h 就由这两个变量决定。注意到 g 是一个加速度单位，是米除以平方秒的形式；为了得出一个以长度为单位的结果，我们必须要消除分母位置上的“平方秒”，因而时间变量 t 必须要以平方的形式出现。

类似地， E = m·c^2 里的平方也不是凭空而来的。能量的单位是牛乘以米，牛本身又是千克乘以米每平方秒，刨根到底能量的单位就该是千克·(米^2)/(秒^2) ，正好符合等式右侧“质量乘以速度平方”的量纲。

在数学中，量纲法也是无处不在。 n 维球的体积公式一定是半径的 n 次方乘以一个系数， Heron 公式 A = √s(s – a)(s – b)(s – c) 看似复杂的外表下也遵循着量纲这一金科玉律。给定 n 个数，我们有多种定义其平均数的方案，包括所有数之和的 n 分之一（算术平均数），所有数乘积的 n 次方根（几何平均数），所有数的倒数和的倒数的 n 倍（调和平均数），所有数的平方和的 n 分之一的平方根（均方根），等等。由于一组数的平均值的量纲应该和这些数本身的量纲保持一致，因此在各种平均数的公式里，平方了就要开回去，取倒了还得倒回来，全乘在一起就得开 n 次方，这样才能得到同样类型的数。

自从在《怎样解题》里看到了量纲法，在学习和讲解数理知识时我便特别留意量纲，慢慢总结出上面这些用于说明量纲规律的经典例子。今天，我又看到了一个把量纲用得神乎其技的经典例子，在这里和大家分享。