一个小镇上即将进行大选，候选人有 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) 。选票系统的算法虽然不是透明的，但政府保证，这个算法满足差异性原则。

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

         为了便于叙述，我们假设有 6 个选民，有 4 个候选人。因此，选票算法相当于是一个把所有仅由数字 1 到 4 组成的全部 46 个 6 位数映射到 {1, 2, 3, 4} 的一个函数。我们不妨把这些 6 位数看作是由所有可能的前 5 位数加上最后一位数得来的。

     让我们先来考虑这样一种情形：在所有可能的前 5 位数中，存在一个 5 位数，它后面加上 1 、 2 、 3 、 4 后所对应的获胜者各不相同。不妨假设这个前 5 位数是 14232 吧。也就是说，当 i 取 1 到 4 时， 14232i 正好对应了所有可能的获胜者。下面，我们任意选取另外一个 5 位数组合 x1x2x3x4x5 ， 使得它的每一位数字正好都和 14232 上对应位置的数字不同。考虑 x1x2x3x4x51 所对应的获胜者，它必然和 142321 、 142322 、 142323 、 142324 之一相同；但根据差异性原则，它和 142322 、 142323 、 142324 都不同，因而只可能是和 142321 相同。同理， x1x2x3x4x52 所对应的获胜者也就和 142322 相同，事实上对于每个 i ， x1x2x3x4x5i 所对应的获胜者与 14232i 都完全一致。

     我们还可以继续推出，事实上，对于任意的前 5 位数组合 y1y2y3y4y5 都有，对于每个 i ， y1y2y3y4y5i 所对应的获胜者都与 14232i 完全一致。为了看出这一点，我们只需要精心选取一个适当的前 5 位数 x1x2x3x4x5 ，使得它和 14232 、 y1y2y3y4y5 对应位置上的数字都不相同。由前面的推理， x1x2x3x4x5i 所对应的获胜者已经与 14232i 一致了，根据同样的道理，y1y2y3y4y5i 所对应的获胜者又依次与 x1x2x3x4x5i 相同，如此一“传递”便证明了任意 5 位数 y1y2y3y4y5 都与 14232 拥有完全相同的效力。

     也就是说，选举结果与前 5 个人的选票无关，完全被最后一个人的选票独裁了。

         接下来，我们来考虑另一种情形：对于所有可能的前 5 位数 x1x2x3x4x5 ，当 i 从 1 取到 4 时，在 x1x2x3x4x5i 当中都至少有两个相同的获胜者。下面，我们任选一个前 5 位数组合，比方说 12314 吧，然后给前 5 个人定义 4 个新的选票算法 gk (这里 k 可以取 1 、 2 、 3 、 4 中的任意一个)：当 y1y2y3y4y5 ≠ 12314 时， gk(y1y2y3y4y5) 就等于 y1y2y3y4y5i 当中重复出现的那个获胜者；当 y1y2y3y4y5 = 12314 时，就让 gk(y1y2y3y4y5) 等于 y1y2y3y4y5k 所对应的获胜者。注意到，每一个选票算法 gk 同样满足差异性原则。这是因为，任取每位数字都不相同的两组选票 a1a2a3a4a5 和 b1b2b3b4b5 ，我们可以假设 a1a2a3a4a5 在 gk 中所对应的获胜者也就是原来的选票算法中 a1a2a3a4a5m 所对应的获胜者(即使 a1a2a3a4a5 恰好等于 12314 )，其中 m 是某个 1 到 4 之间的数。那么， b1b2b3b4b5 就不可能再等于 12314 了，因而，一定存在某个 p 和 q ，使得 b1b2b3b4b5 在 gk 中对应的获胜者和原选票算法中的 b1b2b3b4b5p 、 b1b2b3b4b5q 都相等。其中， p 和 q 必有一个与 m 不同，比如说 p 吧。那么在原选票算法中，由差异性原则， b1b2b3b4b5p 和 a1a2a3a4a5m 对应了不同的获胜者。因而在 gk 中， b1b2b3b4b5 和 a1a2a3a4a5 也对应了不同的获胜者。

     但是 g1 、 g2 、 g3 、 g4 这四个选票算法其实只有一个差别： 12314 所对应的获胜者不同。两个满足差异性原则的选票算法怎么可能只在一处有不同呢？ 12314 和 23421 、 34132 、 41243 两两之间都构成了完全差异的情况，根据差异性原则，它们正好对应了 4 个不同的获胜者；如果后面三种情况对应的获胜者都不变， 12314 所对应的获胜者自然也没有别的选择。因此，两个选票算法绝不可能只在一处有区别。这说明，事实上 g1 、 g2 、 g3 、 g4 这四个选票算法是完全相同的，它们其实都把 12314 映射到了相同的获胜者身上。回顾 gk 的定义，我们立即发现，当 i 从 1 取到 4 时， 12314i 所对应的获胜者是相同的。

     根据同样的道理，把 12314 换作任意一个 5 位数组合 z1z2z3z4z5 ， 那么 z1z2z3z4z5i 都对应着相同的获胜者。这说明，事实上最后一张选票没有任何权力，获胜者完全由前 5 张选票决定，不随最后一张选票的改变而改变。于是，我们可以无视最后一张选票，递归地对前 5 张选票继续分析，直到发现独裁者为止。至此，我们便完成了整个证明。

         不过话说回来，文章开头提到的“差异性原则”，其实是明显不合理的――谁说每个人的选票都变了，结果就一定要变的？这个条件太不自然，当然会造成一些诡异的结果。相比之下， Arrow 不可能性定理则更加令人震撼，在“全体一致性”和“无关候选人独立性”这两个看上去更加自然的条件下，独裁仍然是一个必然推论。因此，最后还是那句颇有些耸人听闻的话：独裁是唯一完美的选举制度。

     题目来源：http://www.cs.cmu.edu/puzzle/puzzle13.html

     原题答案的叙述方式很怪异，我看了很久才看明白。