海盗分宝石|海盗分财宝 2007-12-05 02:24 <原版>
5个海盗分100颗宝石 每个人提出一种意见 如果意见有半数或以上通过 就算通过并实施 否则 把提出意见得丢海里干掉 如果第一个人意见没通过就杀掉并由第二个人提出建议 还剩4个人 再没通过再杀 还剩3人 以此类推 请问:第一人该如何保证自己不被杀而且使自己利益最大化 <原版>解题 相对简单 1,2,3,4,5 反推:
1.当剩下4,5时候
4无论怎么分 5都没办法反抗 因为4具备50%的表决权 4 5 100 0
结论:5不会让4有分配的机会 只要3给他哪怕一个宝石 他就会全力支持3 2.当剩下3,4,5时候
3要成功分配就必须拉拢1个人支持自己 首先排除4(4巴不得3去死 自己就可以全占 分4多少宝石他都不爽)
只剩下5的话 考虑到5的心思 所以只给他1个宝石就OK 3 4 5 99 0 1
结论:4不爽自己什么都没有 所以他不会让3有分配的机会 只要2给他哪怕一个宝石 他就全力支持2 3.当剩下2,3,4,5时候
2要成功分配就必须拉拢1个人支持自己 首先排除3(理由同上) 剩下4,5
4号只需要给他1个宝石安慰奖 就会支持2号 所以我们选择给4号一个宝石 以
赢得计划成功
5号需要给他2个宝石才可以确保他支持2号 如果只给1个的话 他会觉得支持2号和3号都可以 可能选择杀2 2 3 4 5 99 0 1 0 4.当剩下1,2,3,4,5时候
1要成功就必须拉拢2个人以达到3/5 超过50% 首先排除2 剩下3,4,5
3号在2号的计划中 没得到一点好处 所以我们给他1个宝石 他就会听话 4号在2号的计划中 得到1个宝石 我们要赢得他100%的支持 就必须给2个 确保他不会反对
5号在2号的计划中 也一样不爽 我们给1个宝石 他也听话 1 2 3 4 5 98 0 1 0 1
抽象:偶数会一直为0 除分配者作为1号以外的 奇数都可以拿到1个宝石 所以 奇数为1(1号位置除外)
设海盗=N,宝石=L,第M个人想的分配计划: N%2!=0结果是 K=L-((N-1)>>2)
1 2 3 ****** N k 0 1 ****** 1 N%2=0结果是 K=L-(N>>2)
1 2 3 ****** N
k 0 1 ****** 0 <修改版>
5个海盗分100颗宝石 每个人提出一种意见 如果意见有半数以上通过 就算通过并实施 否则 把提出意见得丢海里干掉 如果第一个人意见没通过就杀掉并由第二个人提出建议 还剩4个人 再没通过再杀 还剩3人 以此类推 请问:第一人该如何保证自己不被杀而且使自己利益最大化 <修改版>解题: 1,2,3,4,5 反推:
1.当剩下4,5时候
4无论怎么分 5都可以否定 让4去死 无法超过50% 所以4只能自保 避免自己死去 4 5 0 100
结论:4不会让前3个人都死掉 也就是说 他不会让自己有分配财宝的机会 只要前3个人能给他好处 他就同意啦 2.当剩下3,4,5时候
3拉拢一个人就可以超过50%会考虑2个情况: A拉拢5 3 4 5 99 0 1
这里会出现问题 5号不会同意 因为他觉得他弄死3号的话 自己就分得所有财宝 何必只拿一个宝石 B拉拢4 3 4 5
99 1 0
分给4号一个宝石 让他吃点甜头 总比3号死掉 4号自己 要么也死要么什么都得不到要强很多
结论:3号可以获得99个宝石 如果它给4号甜头的话 5号呢 绝对会反对3号的计划
3.当剩下2,3,4,5时候
2号必须拉拢2个人才可以超过50% 所有他会考虑4和5的利益.排除3是因为3号很希望2号死掉 他就可以施展自己的计划
2号成功拉拢4号的条件是 给他2个宝石 以超过3号只给他1个宝石的承诺 然后对于5号来说 2号丢一个宝石给他做安慰奖 因为如果2号死掉 3号根本不考虑5号的利益 2 3 4 5 97 0 2 1
结论:2号获得97个宝石,4,5号因为获得相对3号更多的利益 所以会选择同意 4.当剩下1,2,3,4,5时候
1号必须拉拢2个人以超过50% 所以他会首先排除2号,剩下3,4,5中选择2个做利益伙伴
成功拉拢3号的条件是给他1个宝石(2号的计划中 一个都不给他)
成功拉拢4号的条件是给他3个宝石(2号承诺给他 2个宝石 同级下4号无所谓 可能会选择杀死1号 为确保故必须给3)
成功拉拢5号的条件是给他2个宝石(2号承诺给他 1个宝石 同级下4号无所谓 会选择杀死1号)
综合来看 只需要选择 3,5就可以了 1 2 3 4 5 97 0 1 0 2
以上为逻辑推理 抽象数学模型 还得有番研究 over