选举制度的学问

2010 年 8 月 15 日 / 33 条评论

完美的制度是永远不存在。我们可能会产生一种觉得某某制度很完美的错觉，这只是因为我们习惯了它而已。若把这个制度拿出来仔细琢磨琢磨，你会发现它还存在太多的问题。
我们习惯了“多数票当选”的选举制度。每个投票者把自己手中的票投给其中一位候选人，得票数最多的候选人即获胜，因为他的支持者最多。这看上去似乎挺合理。但在实际生活中，这种选举制度并不见得总是合理的——得票数最多的候选人很可能并不是大家喜欢的候选人。有时候，获胜的候选人竟会是最不受欢迎的那个人。

假设有 A 、 B 、 C 、 D 四位候选领导人，其中 A 、 B 、 C 三人的思想、观点、作风都不相上下；候选人 D 则观点偏激、做事极端，他故意与前面三个人作对，一心想在竞选中获胜。虽然 A 、 B 、 C 三人大受好评，但他们却处于一个非常不利的地位：由于得票最多的候选人获胜，三人内部的激烈竞争很可能会使他们都输掉竞选。我们假设只有 34% 的人支持候选人 D ，而另外 66% 的候选人都在 A 、 B 、 C 三人之间犹豫不决。最终， A 、 B 、 C 每个人都只得到 22% 左右的票，候选人 D 以绝对的优势获得胜利。但请注意，候选人 D 却是最不受欢迎的那个人。如果按照投票淘汰制进行选举，候选人 D 将在第一轮就被淘汰，因为最不喜欢他的人达到了 66% 。
有人会说，那么干脆以后选举都搞投票淘汰制，每个投票者每轮都选出一位仍未淘汰的人中自己最讨厌的，问题不就解决了吗？这样也有问题——对称地，如果 A 、 B 、 C 三人都很讨厌，投票者会在他们三人之间纠结， D 却反而处于了最不利的地位。因此，要想彻底避免这种问题，我们还得想点儿别的着。

– 1 + 2^7 = 127 这样的算式有多少个？

2010 年 5 月 5 日 / 28 条评论

或许有人会对算式 5^2 = 25 有一种特别的偏好——等式左右两边都用到了相同的数字，让人深感奇妙。类似的算式还有很多，例如

      5^(6 – 2) = 625
      (4 / 2)^10 = 1024
      ((86 + 2 * 7)^5 – 91) / 3^4 = 123456789

我们自然而然地提出了这样一个问题：这样的算式究竟有多少呢？答案是：无穷多。只需要借助本文一开始提到的算式 5^2 = 25 ，我们就能轻易构造出无穷多个同样满足这种神奇性质的算式来：

      50^2 + 0 = 2500
      500^2 + 0 + 0 = 250000
      5000^2 + 0 + 0 + 0 = 25000000
      ……

现在，让我们来看看另一类更加精妙的算式：等式两边的数字顺序也完全一样！

      – 1 + 2^7 = 127
      (3 + 4)^3 = 343
      16^3 * (8 – 4) = 16384

这样的算式是否仍然有无穷多个呢？

Mathematica真的什么都能求出来吗？

2010 年 4 月 25 日 / 51 条评论

Mathematica 强大的符号计算和化简能力相信会让不少人震撼不已。输入 Sum[1/n^2, {n, 1, ∞}] ， Mathematica 竟然知道它等于 π^2/6 。我不禁问自己， Mathematica 真的什么都能化简出来吗？今天，我偶然遇到一个简单的表达式， Mathematica 竟然不知道它的精确值。

在 Mathematica 中输入 Cot[π/2] ， Mathematica 会告诉你它等于 0 ；在 Mathematica 中输入 Cot[π/4] ， Mathematica 会告诉你它等于 1 ；但在 Mathematica 中输入 Cot[π/8] ， Mathematica 返回的却还是一个 Cot[π/8] ，并没有给出它的值。而 Cot[π/8] 并不是一个复杂到无法用四则运算和平方开方表达出来的数。在一个边长为 1 的正八边形中，每条边的所对应的“圆心角”为 2π/8 = π/4 ，因此“圆周角” α 就等于 π/8 。由下图我们可以轻易看出， Cot[π/8]=√2+1 。

如此排序能成吗？

2010 年 4 月 9 日 / 32 条评论

书架的某一层里放了一套百科全书，但它们排列的顺序却是乱的。一个傻子想要把这套书排好顺序，也就是说他想要书架里的书从左至右分别是第 1 卷，第 2 卷，……，第 n 卷。他给这套书排序的办法是这样的：不断取出一本原应放在更左边的书，插进它该在的位置。比方说，某本书的卷号是 3 ，它的位置却是左起第 5 ，位于其目标位置的右侧。那么傻子就可以把这本书拿出来，插入当前左起第 2 本书的右边，把那些占了它位置的书挤到更右边去，而不管这一操作是否会破坏掉已经就位的书。注意到这种排序法很可能捡了芝麻，丢了西瓜，为了一本书的位置而破坏掉一连串原已排好的书，可谓是鼠目寸光，缺乏远见。我们的问题是，在哪些情况下这样的排序法最终一定能实现排序，哪些情况下可能会陷入永无止境的死循环？

什么是算法：如何寻找稳定的婚姻搭配

2010 年 3 月 19 日 / 70 条评论

引言什么是算法
如何寻找稳定的婚姻搭配

    据说，一本书开篇就直言不讳地谈起两性的话题，这本书准能畅销。有幸的是，在众多可以用来引入“算法”的话题中，我最喜欢的那一个还真与两性有那么一些关系。假如你是一个媒人，有若干个单身男子登门求助，还有同样多的单身女子也前来征婚。如果你已经知道这些女孩在每个男人心目中的排名，以及男孩们在每个女孩心中的排名⁽¹⁾，你应该怎样为他们牵线配对呢？
    最好的配对方案当然是，每个人的另一半正好都是自己的“第一选择”。这虽然很完美，但绝大多数情况下都不可能实现。比方说，男 1 号的最爱是女 1 号，而女 1 号的最爱不是男 1 号，这两个人的最佳选择就不可能被同时满足。如果出现了好几个男人的最爱都是同一个女孩儿的情况，这几个男人的首选也不会同时得到满足。当这种最为理想的配对方案无法实现时，怎样的配对方案才能令人满意呢？
    其实，找的对象太完美不见得是个好事儿，和谐才是婚姻的关键。如果男 1 号和女 1 号各自有各自的对象，但男 1 号觉得，比起自己现在的对象，女 1 号更好一些；女 1 号也发现，在自己心目中，男 1 号的排名比现男友更靠前一些。这样一来，这两人就可能会发生外遇，最后扔下各自现在的对象，一起私奔了——因为这个结果对他们两人都更好一些。在一种男女配对的方案中，如果出现了这种情况，我们就说婚姻搭配是不稳定的。作为一个红娘，你深深地知道，对象介绍得不好没有关系，就怕婚姻关系不稳定。给客户牵线配对时，虽然不能让每个人都得到最合适的，但婚姻搭配必须得是稳定的。换句话说，对于每一个人，在他心目中比他当前的伴侣更好的异性，都不会认为他也是一个更好的选择。现在，我们的问题就是：稳定的婚姻搭配总是存在吗？应该怎样寻找出一个稳定的婚姻搭配？