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

题目

十多年前,中国数学奥林匹克集训队请来华裔美国人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票反对,恰好能通过。

思考

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

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

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

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

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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注