按规则作弊
《Communications of the ACM》:Cheating by the Rules
【字体:
大
中
小
】
时间:2026年09月26日
来源:Communications of the ACM 7.1
编辑推荐:
## 选举委员会
假设政治光谱类似于一个在1到100之间编号的尺子(其中1代表极权主义,100代表无政府状态,自由民主制大约位于50),以下是规则:任何候选人必须陈述其整数立场值(1到100之间的某个整数,包括两端),且没有两位候选人可以选择相同的值。选民将投票给离其立场最
## 选举委员会假设政治光谱类似于一个在1到100之间编号的尺子(其中1代表极权主义,100代表无政府状态,自由民主制大约位于50),以下是规则:任何候选人必须陈述其整数立场值(1到100之间的某个整数,包括两端),且没有两位候选人可以选择相同的值。选民将投票给离其立场最近的候选人。如果有两位候选人距离选民V的距离相同,则选民V不会投票。现在假设有两个政党在争夺权力。A党必须介绍其候选人及其在这个1到100的光谱上的立场。然后B党介绍其候选人及其立场。选举分两轮进行。第一轮结束时,获得最多选票的两位候选人在决选中对决。如果有几位候选人票数并列,则选举委员会会在可能的情况下安排来自不同政党的成员进行第二轮对决。例如,如果X党有一位候选人赢得了第一轮最多选票,而几位其他候选人并列获得第二高票数,则选举委员会将选择一位来自X党以外的政党的候选人。**热身题:** 如果每个党派出两名候选人,两个党能否保证在决选中至少有一名候选人?请记住,如果来自不同政党的候选人之间出现平局,委员会将确保最终选举中有两个政党代表。**热身题解答:** 假设A党将其候选人放在25和75的位置。如果B党将候选人放在24和26,则B党将获得立场在1–24和26–49的选民。A党将获得51–100的选民。因此,决选将在A党位于75的候选人与由委员会随机选择的B党的一位候选人之间进行。面对A党25和75的选择,B党无法阻止A党至少有1名候选人进入决选。**问题:** 假设有三名B党候选人,但A党仍为两名。当A党先出牌时,B党能否保证决选中的所有候选人都是B党的?请证明你的答案。**解答:** 在这种情况下,B党可以保证决选将在B党的候选人之间进行。假设A党将其候选人分别放在X和X+d的位置。一种可能性是B党将一名候选人放在A党两位候选人的中间(在X + d/2处)。该候选人将获得大约d/2票。B党的其他候选人可以去X-1和1+(X+d)。这将限制A党的候选人获得大约d/4的票数比例。只要满足d/4 < X-1或d/4 < 100-(X+d),B党位于中间的候选人和B党的另一位候选人将进入决选。我们将这种"中间加两端"的策略称为配置1。如果d较大,B党将两名候选人放在X+1和X+d-1,第三位候选人放在X+d+1或X-1(视哪个能让该B党候选人获得更多选票,或至少不少)。我们将这种"包围一位候选人、位于另一位候选人内部"的策略称为配置2。例如,假设X = 10且X+d = 80。B党根据配置2将其候选人放在11和79,各获得大约34%的选票。这两位候选人进入决选。B党将另一位候选人放在81。A党位于10的候选人将获得10%的选票,A党位于80的候选人将获得1%的选票。为证明这在一般情况下成立,请注意A党有充分动机使X和X+d对称地远离两端,即X = 100-(X+d)。否则,在任一种配置中,B党都将占据更大的那一端(配置1中自动实现,配置2中通过选择实现)。这种对称性意味着2X = 100-d。回顾一下,配置1在满足d/4 < X-1时对B党有利。根据对称条件,d/4 < ((100-d)/2) - 1 = 49 - d/2。因此d < (4/3) × 49 = 66(约65.33)。例如,如果d = 64,则A党将其候选人放在X = 18和X+d = 82的位置。根据配置1策略,B党将其候选人放在17、83和50。位于50的候选人将获得35到65的所有选票。A党位于18的候选人将获得18到34(含)的选票,即17%。A党位于82的候选人将获得66到82的选票,也是17%。然而B党位于83的候选人将获得18%,B党位于50的候选人将获得31%(35到65)。因此B党的候选人将出现在决选中。配置2在满足X < (d/2) - 1时对B党有利。因此,例如,如果d > 53,则配置2有效。在d = 54的情况下,A党将其候选人放在X = 23和X+d = 77的位置。B党将候选人放在24、76和78。B党位于24和76的候选人各获得26%的选票。A党位于24的候选人仅获得24%的选票,A党位于76的候选人仅获得1%的选票。因此,如果d > 64,使用配置1。否则使用配置2。事实上,对于d在54到64之间(含两端),两种配置都将有效。**解答完毕****挑战题:** 假设有C名X党候选人和C'名Y党候选人,C > C',但X党必须在Y党之前部署所有候选人。对于C和C'的哪些取值,Y党仍能保证在决选中至少派出一名候选人?是否存在Y党能保证在决选中派出两名候选人的取值?---**丹尼斯·沙莎**(Dennis Shasha,shasha@cs.nyu.edu)是美国纽约市纽约州立大学柯朗数学研究所计算机科学系计算机科学教授。全知全能的埃科博士与他是好朋友。欢迎大家将解决方案提交至 upstartpuzzles@cacm.acm.org;挑战题的解答和讨论将发布在 http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号