UOJ Logo matthew99的博客

博客

分金币问题

2015-10-26 15:56:32 By matthew99

今天的模拟题给了我们一次刻骨铭心的经历。

题目是这样的,n个人分m个金币,每个金币完整不可分。从第一个人开始,每个人提出一个分金币方案,如果投票同意的人超过半数,那么这个方案就通过,否则这个人将被杀掉。

现在假设每个人都很聪明。每个人尽可能的保证生命。如果可以保证生命,那么他希望自己分到的金币最多。如果不能过获得更多金币,就会希望别人死。如果一个人知道自己肯定要死,那么他对别人的方案会投反对票。

假设有6个人,100个金币。

对于一个人,显然分到所有金币。

对于两个人,显然第二个人必死,第一个人分到所有金币。

对于三个人,他会给自己留100个金币,其他人不分,第二个人想,自己不同意就会死,第一个人显然不会同意,而第三个人自己的方案显然会同意,所以有两个人同意,方案通过。第三个人获得100个金币,前两个人都没有金币。

对于四个人,他会给自己98个金币,第一个人和第二个人各1个金币,前两个人想,如果我不同意而给第三个人决定,那么自己就不会有金币了,因此会同意,而第四个人显然会同意,所以有三个人同意,第四个人获得98个金币,前两个人各1个金币,而第三个人得不到金币。

对于五个人,他会给自己97个金币,第三个人1个金币,第一个或者第二个人2个金币,这样第三个人肯定同意,给了2个金币的那个人也会同意,第五个人自己也同意,所以分金方案是第五个人97个金币,第三个人1个金币,第一个或者第二个人2个金币。

对于第六个人,矛盾就出现了。

考虑给自己留97个金币,第四个人1个金币,第一个和第二个人各1个金币。 自己和第四个人肯定会同意,而第一个和第二个人会不会同意呢。

第一个人和第二个人的想法是,如果自己不同意,那么自己可能一分钱没有,也可能会得到两块钱,如果他们都想保全这一块钱,那么就都会同意,反之如果有人想奋力一搏,觉得还不如不同意,说不定有两块钱,那么大家都不会同意,出现了矛盾。

如果第一个人和第二个人都清楚第五个人的选择,比如第一个人和第五个人关系特别好,他知道第五个人肯定会给他,而第二个人也清楚这一点,那么,如果是上面这样分,只会有第一个人同意,第六个人就会被杀死。

这个时候正确方案应该是自己留96,第二个人留1,第四个人留1,第三个人留2。 如果第六个人想:“唉我还这么年轻,真的不想死啊,钱是身外之物我不想要了!”,那么他就会做出这样的决策:

自己留94,第四个人留1,第三个人留3,第二个人或者第一个人留3,这样给3个金币的人肯定会同意,另外三个也会同意,自己肯定死不了。

五个人的情况似乎是小学奥数的经典内容?因为五个人的情况是没有争议的。

事实上,我考场上实现的,包括出题人的数据,都是第二个想法,就是大家都是先知,都可以预测别人的想法。然而也有相当一部分人写的是第一种想法,而第三种没听说有人写过。

实际上题面也什么也没说清楚,所以才会导致这么大的撕逼。

如果是CF或者TC遇到这种情况当然unrated咯。

但实际上大家为此撕逼了一中午和一下午233333333333333333333。各抒己见,感觉还是很好玩很刺激。

实际上如果大家都可以预测别人的想法,那两个人玩起石头剪刀布,究竟会怎么出呢,估计两个人的大脑都栈溢出咯......

事实上撕逼这种问题也不是第一次,CTSC day2的前夕和吉丽、松爷、猪猪侠和DZY也为此撕逼过。详见http://jiruyi910387714.is-programmer.com/posts/94162.html

公平分配中的争议还真是多。

评论

lyxin65
前排膜毛爷爷
zhangzj
前排膜myy
wxjlzbcd
中排膜myy
z123z123d
膜拜毛爷爷
Prime
感觉源头都是matrix67 比如那个分饼的:http://www.matrix67.com/blog/archives/3944 以及分金币的:http://www.matrix67.com/blog/archives/655 , http://www.matrix67.com/blog/archives/3885 。
zhouzixuan
orz
h10
%%%myy

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。