查看完整版本: 我出一道题

我出一道题

50个海盗，得到了100个金币。他们经过商量后决定先抓阄排序，然后按照一下的规则分金币：
1 1号先出一个分配方案，如果不能得到半数以及以上的人认可（可以等于一半），他将被杀掉。
2 杀掉1号后由2号分，如果2号不能得到如半数以及以上的人认可（可以等于一半），他将被杀掉，然后由下一个人分。
。。。。。。。
请问：如果你是1号海盗，你会怎么分？

注：投票人包括自己/投票人不包括自己
假定：海盗的天性是争取利益最大化，损人不利己但是也对自己没坏处的事情他们也喜欢干。
假定：海盗都绝顶聪明，对方案的理解相当深刻和准确。


不能上网找答案！！找出的答案可能是不对的：）

[[i] 本帖最后由 apple 于 2007-11-24 16:31 编辑 [/i]]

这个题15分钟。。

先做再说，15分钟我做不出来，虽然我知道解法

应该是75个把  有点博弈论的意思
1. 从3到49间的排列数为单数的每人分一个金币(包括3和49),共24个
2. 50号分一个金币
3. 一号自己留75个金币

[quote]原帖由 [i]apple[/i] 于 2007-11-21 21:03 发表 [url=http://bbs.sky01.com/redirect.php?goto=findpost&pid=4254&ptid=1264][img]http://bbs.sky01.com/images/common/back.gif[/img][/url]
先做再说，15分钟我做不出来，虽然我知道解法 [/quote]

当时做的时候就是15分钟做出来的。。。

[quote]原帖由 [i]Ghost[/i] 于 2007-11-22 04:15 发表 [url=http://bbs.sky01.com/redirect.php?goto=findpost&pid=4309&ptid=1264][img]http://bbs.sky01.com/images/common/back.gif[/img][/url]


当时做的时候就是15分钟做出来的。。。 [/quote]
Ghost 是推理达人，鉴定完毕:y沉思;

hoho，我又来了

本题使用逆向递归法

假设海盗总数是2，则分配方式：100，0

假设海盗总数是3，则第一个应该争取自己方案失败的情况下得到利益最少的人，即最后一个，则分配方式：99，0，1

假设海盗总数是4，则第一个应该争取自己方案失败的情况下得到利益最少的人，即倒数第二个，则分配方式：99，0，1，0

假设海盗总数是5，则第一个应该争取自己方案失败的情况下得到利益最少的人，即倒数第一个和倒数第三个，则分配方式：98，0，1，0，1

假设海盗总数是6，则第一个应该争取自己方案失败的情况下得到利益最少的人，则分配方式：98，0，1，0，1，0

。
。
。
。
。
。

规律已经出来了

50个海盗的话，则分配方式：76，0，1，0，1，........，0，1，0

即偶数全是0，奇数（除自己外得）是1

第一个海盗得76

看来我说错了。。。

之前做的是5个海盗分100个金币，要求一半以上（不含），同意才通过

比apple哥的题难多了。。。

[quote]原帖由 [i]Ghost[/i] 于 2007-11-22 19:55 发表 [url=http://bbs.sky01.com/redirect.php?goto=findpost&pid=4423&ptid=1264][img]http://bbs.sky01.com/images/common/back.gif[/img][/url]
看来我说错了。。。

之前做的是5个海盗分100个金币，要求一半以上（不含），同意才通过

比apple哥的题难多了。。。 [/quote]

:y奸笑;

你咋不去参加智力快车呢

哦 我没注意到投票人包括本人自己

[quote]原帖由 [i]Forest[/i] 于 2007-11-22 20:02 发表 [url=http://bbs.sky01.com/redirect.php?goto=findpost&pid=4430&ptid=1264][img]http://bbs.sky01.com/images/common/back.gif[/img][/url]


:y奸笑;

你咋不去参加智力快车呢 [/quote]


我懒。。。

[quote]原帖由 [i]月之痕[/i] 于 2007-11-22 23:48 发表 [url=http://bbs.sky01.com/redirect.php?goto=findpost&pid=4470&ptid=1264][img]http://bbs.sky01.com/images/common/back.gif[/img][/url]
哦 我没注意到投票人包括本人自己 [/quote]
如果不包括自己你的答案好像也有点问题~~

不包括自己：

2个人时，第一个人肯定会死掉。最后一个人独吞100.
3个人时候，可以为100 0 0
4个人时，可以为99 0 1 1
5个人时，为97 0 1 2 0或97 0 1 0 2，综合这两种可能 每人的最大利益值为 97 0 1 2 2，以此为依据：
6个人时：94 0 1 2 3 0或者 94 0 1 2 0 3
综合这两种可能每人的最大利益为：94 0 1 2 3 3以此为依据，7人时：

94 0 1 2 3 0 0
8人时：95 0 1 2 0 0 1 1

之后就更麻烦了，哈哈哈，50个人50分钟也不一定做出来
。。。。。。。。

[[i] 本帖最后由 apple 于 2007-11-24 16:36 编辑 [/i]]

试着完成这道题目吧（自己不能投票的情况下）：
9人，三种分法综合最后得到每人的最大利益为95 0 1 2 0 1 1 2 2
10人，92 0 1 2 0 1 2 2 0 0
11人，两种分法综合得每人最大利益94 0 1 2 0 1 2 0 0 1 1
12人，多种分法综合得每人最大利益94 0 1 2 0 1 2 0 1 1 2 2
13人，                                    91 0 1 2 0 1 2 0 1 2 2 0
14人，                                  90 0 1 2 0 1 2 0 1 2 0 0 2
15人，我想吐了~~~~~~~~~~~~~~

[[i] 本帖最后由 apple 于 2007-11-24 16:36 编辑 [/i]]

师兄 当是六个人时   还是97   
这样分就足够  97  0 1  0 1  1   当这次的时候 上边的最后两人不确定自己下一次能否得到2个还是0个 所以这一次只要给他们一人一个就足够

[[i] 本帖最后由 月之痕 于 2007-11-24 22:29 编辑 [/i]]