引人深思——关于民主投票的数学竞赛题

题目

十多年前，中国数学奥林匹克集训队请来华裔美国人Zuming Feng老师讲课。他在课上讲了下面这道组合题：

某公司有1位老板和100位员工。初始时老板和每位员工的工资都是1元。现在老板可以不断的提出新的工资分配方案，需要满足老板和每位员工的工资都是非负整数，且总和不变还是101元。然后新方案交给员工们投票，老板自己没有投票权。每位员工都是绝对的利己主义者，只考虑新方案下自己的工资和当前比，如果涨了就投赞成票，如果跌了就投反对票，如果不变就投弃权票。任何一个新方案必须满足“赞成票的数目严格多于反对票的数目”才能通过。假设老板提出新方案的次数不限，那么老板最多可以把自己的工资变成多少元？

思路

首先注意到，老板一上来提新方案的时候必须把自己的工资改成0元。不然每收获1张赞成票都需要把至少1个员工的工资减到0元，必然也带来1张反对票。那么赞成票的数目不会严格多于反对票的数目，新方案根本无法通过。当然老板可以先弃后取，之后再找机会给自己加工资。当然由于老板自己没有投票权，后面提方案的大概思路是把个别员工的高工资改成0元，然后给其他几个员工每人加1元这样的。最后老板的工资有可能接近101元，但肯定拿不到101元，具体能拿多少呢？

解答

答案

答案是98元。你做对了吗？

解题步骤

假设本题的答案是x元。为了写一份严谨的解答，我们需要做两件事情：

• 论证：证明老板的工资不可能多于x元。
• 构造：给出老板提出的一系列工资分配方案，说明老板这样操作之后确实可以让自己的工作变成x元。

我们证明老板的工资最多是98元。

首先注意到任意一个不同的新方案一定会动了某个员工的“奶酪”，所以反对票总是至少1票。然后永远不可能只有一个员工有正数工资，否则达成这种状态的新方案只有那一位员工的赞成票，不会多于反对票，通不过的。假设老板可以让自己拿99元，那么达成99元的那个新方案需要至少2票赞成，只能是剩下2元的额度分给了之前0元的两位员工，于是恰有2票赞成且新方案下其他员工全是0元。但由上面的论证，之前的方案下至少有两位员工是正数工资，变成了0元就会有至少2票反对，新方案无法通过，矛盾！所以老板的工资最多是98元。

我们再说明，老板可以成功地把自己的工资改成98元。

老板一开始先把自己改成0元，给随便某个员工加1元，1票赞成通过。之后每次选择一名有至少2元工资的员工，把ta的工资改成0元，而这部分工资加给至少2个已经有正数工资的员工(各加至少1元)，其他人不变，则这样的新方案有至少2票赞成和恰好1票反对，总能通过。那么在这个过程里，有正数工资的员工人数不断减少，直到只剩2个。最后一次把仅剩的2个正数工资的员工全改成0元，然后给3个0元工资的员工各加1元，剩下98元给自己。则3票赞成和2票反对，恰好能通过。

思考

从解答可以看出，这个题还有深刻的寓意。

• 虽然老板的目标是自己利益最大化，但也不能一毛不拔。这个题目的关键就是要先放弃自己的工资，后面才有机会加倍赚回来。一开始如果老板不动自己工资，只调整员工的，容易发现赞成票最多等于反对票，新方案怎么都通不过，也就根本达不到目标了。

• “一人一票”的制度看似民主，却可能有严重的缺陷。比如说，很容易发生“吃大户”的现象。因为少数大户即使利益严重受损，话语权也比不过获得了一点利益的大量群众。在人类的历史上也不乏这样的现实例子。

• 不能做完全的利己主义者。“吃大户”的时候兴高采烈，却完全不考虑自己也可能有一天作为“大户”被“吃”了。类似地，别人利益受损的时候默不作声甚至助纣为虐，自己就也可能面临同样的下场。

• 设置议题的权力太重要了。这道题目的场景里面，老板没有投票权，新方案通过的门槛还是较高的严格多数，但却能把员工们玩弄于鼓掌之中！