比较严肃的投票通常都会设法让选项缩到两个,
方法是每次淘汰一半,
或著每个人可以在投票上加上权重,做基本筛选,
然后只要让同数人时主席多一票或著不记入就能解决问题.
事件发生后,第十队几乎停止存在.
SAS也声称他们的行动摧毁导弹发射器也是灾难. 因为伊拉克牧童发现了他们. 十年后,英国记者找到了长大的牧童,他说他没有看到任何人. 但他和村民听到了直升机的声音.
结论是由于情报不佳,行动从一开始规划就是失败的.
投票人数要和主题的数量互质(一人一票的前提)
希望不算推旧文.
问题:考虑r人投票想从n个选项中选出1个 (rn>=2),有没有一种投票结果是为平手.
固然原po问的r为偶数时,必定有平手的机会.
n>=3时,更是无论r为何,也是必定有机会平手.
反过来,其实只有r为奇数而n=2时,能保证不会平手.
以上定论,即使引入一人有多票,
甚至票有不同比重 (如每人有1票值1分,1票值2分),
或加上一人不能投同一项多于若干分等,五花八门的规则,
还能弃权的话,人人都全弃权不就当然平手,本题秒杀.
其实容许了也是变成:r为奇数,n=2时,也能平手而已.
先诠释好命题.
r人投n项可视为选出r个n维数组,数组取值非负整数 (甚至推广到实数或任意有全序的集).
投票结果是将数组加总 (可推广到任意公平,且对r变量中每个都严格递增的函数f),然后数值最大的胜出.
若最大者非唯一,则称为平手.
而上面一人多票,比重和添加的规则,全可透过限定每人可选的n维数组的形式,表达出来.
如一人2票,不能投给同一项,就是要求数组有2项1,其余皆0.
类推,一切附加的规则都可表达成一个包含所有可选数组的集.
不过为保证选项间地位公平,这数组集S应符合:
设p为对n维数组的重排列 (permutation),若x属S则p(x)属S.
上面提过的公平函数f,也用排列的说法定为:
即r人投票先后没有影响.
那么现在看有偶数r人时,要构造平手,可令r人平分成两组,
然后一组全人投 x=(a_1a_2...a_k...),不失一般性可使a_1>=a_2,其余任一a_k<=a_2,
而另一组全人投 y=(a_2a_1...a_k...),即首两项和第一组相反投,其余全一样地投,
由选项公平原则确保可这样投.
u_1=f(a_1...a_1a_2...a_2),其中a_1a_2各有r/2项,f是将r人对此项投的票数加总的函数,
由投票先后无关原则可知u_1=u_2,即首两选项同票.
=u_1=u_2.
因此首两项就是最高票者,也可能有其他同票,总之出现了平手.
白话说就时一人怎样投,另一人就跟随,但将他投首两高票的掉换投,抵销掉首两名的差距.
(可留意要求n>=3就是因为这次多了a_3.)
r必能表成非负偶数和三的非负倍数的和:n=2s+3t,st>=0
2s的一部分人按偶数人数的段落,投成首两项平手,
3t的一部分人按人数三的倍数的段落,投成首三项平手,
再将两部分人的结果加总,易知首两项还是平手.
最后未论述到的只n=2的情况.
若人数是偶数,落入上面证过的情形,必有机会平手.
若人数是奇数,显然一般一人一票的投票已可保证不会平手.
一切n,r的组合经已拆解过.
要杜绝平手,多票,比重,其他附加规则都不能保证做到,
奇偶,互质的特性也非绝对 (除了只有两选项时).
不过也不是说以上的就没用,以上是证明了不能完全避免平手,
但端看每人投票意愿,还是有可能减低平手机会的.
如r人互选领袖,人人都想当,一人一票并且能投自己的话,当然会全投自己,没完没了.
规定不能投自己就很机会能分高下了 (非一定,考虑三人,A投B,B投C,C投A).
等价的规定还有一人两票而不能都投同一人,等等.
另外,问题还可伸延,再作思考:r人投票想从n个选项中选出m个而非只选出1个,又会如何?