l*******s
发帖数: 7316 | 1 应拖板斧之邀出题，活跃版面。还是老规矩：两小时内请只贴答案，别贴解法。两小时
内答对的都有包子。两小时后贴解法，简明易懂的解法有包子。
大家先别急着放狗，因为题目跟标准的海盗分金不一样。
有24海盗得到了5件相同的价值连城的宝贝，他们准备瓜分这5件宝贝。 但宝贝不能被
切割，他们也不愿跟别人共享宝贝，所以就有人分到宝贝，有人分不到。他们按身高从
矮到高排序，小明最矮，排1号，大明最高，排24号。
首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
案分。否则就把24号扔到海里，由其他人中最高的23号提出分配方案。
如果他人中有一半或以上的人同意23号的方案就按23号的方案分，否则就把23号扔到海
里，由其他人中最高的22号提出分配方案。
如此类推，直到有被接受的方案为止。
对这些海盗有如下假设：
1.海盗都很聪明。有多聪明呢？他们都会做对这道题。
2.海盗都想活命。
3.在活命的基础上，海盗都想得到尽量多的宝贝。
4.如果不影响自己活命，也不影响自己得到多少宝贝的条件下，海盗都会不同意分配方
案。
5.海盗都相信数鸟在林不如一鸟在手。也就是说，当前方案中给我n个宝贝，如果当前
方案被否定，我可能得到多于n个宝贝，但也可能少于n个宝贝，那就选择同意当前方案。
现在问题来了：最终会按几号提出的方案分配。 |
H********g
发帖数: 43926 | |
c*w
发帖数: 4736 | |
r****z
发帖数: 12020 | 4 13
【在 l*******s 的大作中提到】
: 应拖板斧之邀出题，活跃版面。还是老规矩：两小时内请只贴答案，别贴解法。两小时
: 内答对的都有包子。两小时后贴解法，简明易懂的解法有包子。
: 大家先别急着放狗，因为题目跟标准的海盗分金不一样。
: 有24海盗得到了5件相同的价值连城的宝贝，他们准备瓜分这5件宝贝。 但宝贝不能被
: 切割，他们也不愿跟别人共享宝贝，所以就有人分到宝贝，有人分不到。他们按身高从
: 矮到高排序，小明最矮，排1号，大明最高，排24号。
: 首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
: 案分。否则就把24号扔到海里，由其他人中最高的23号提出分配方案。
: 如果他人中有一半或以上的人同意23号的方案就按23号的方案分，否则就把23号扔到海
: 里，由其他人中最高的22号提出分配方案。
|
H********g
发帖数: 43926 | |
T******e
发帖数: 18290 | 6 15
【在 H********g 的大作中提到】
: 我就押个14吧
|
T******e
发帖数: 18290 | 7 16
【在 T******e 的大作中提到】
: 15
|
T******e
发帖数: 18290 | 8 17
【在 T******e 的大作中提到】
: 16
|
H********g
发帖数: 43926 | |
p**s
发帖数: 2707 | |
|
|
K*****2
发帖数: 9308 | |
i******l
发帖数: 268 | |
f****w
发帖数: 407 | 13 24啊
【在 l*******s 的大作中提到】
: 应拖板斧之邀出题，活跃版面。还是老规矩：两小时内请只贴答案，别贴解法。两小时
: 内答对的都有包子。两小时后贴解法，简明易懂的解法有包子。
: 大家先别急着放狗，因为题目跟标准的海盗分金不一样。
: 有24海盗得到了5件相同的价值连城的宝贝，他们准备瓜分这5件宝贝。 但宝贝不能被
: 切割，他们也不愿跟别人共享宝贝，所以就有人分到宝贝，有人分不到。他们按身高从
: 矮到高排序，小明最矮，排1号，大明最高，排24号。
: 首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
: 案分。否则就把24号扔到海里，由其他人中最高的23号提出分配方案。
: 如果他人中有一半或以上的人同意23号的方案就按23号的方案分，否则就把23号扔到海
: 里，由其他人中最高的22号提出分配方案。
|
l*******s
发帖数: 7316 | |
d****o
发帖数: 32610 | 15 6号
晚了吗？
好像不对
猜个10号吧
【在 l*******s 的大作中提到】
: 应拖板斧之邀出题，活跃版面。还是老规矩：两小时内请只贴答案，别贴解法。两小时
: 内答对的都有包子。两小时后贴解法，简明易懂的解法有包子。
: 大家先别急着放狗，因为题目跟标准的海盗分金不一样。
: 有24海盗得到了5件相同的价值连城的宝贝，他们准备瓜分这5件宝贝。 但宝贝不能被
: 切割，他们也不愿跟别人共享宝贝，所以就有人分到宝贝，有人分不到。他们按身高从
: 矮到高排序，小明最矮，排1号，大明最高，排24号。
: 首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
: 案分。否则就把24号扔到海里，由其他人中最高的23号提出分配方案。
: 如果他人中有一半或以上的人同意23号的方案就按23号的方案分，否则就把23号扔到海
: 里，由其他人中最高的22号提出分配方案。
|
w***3
发帖数: 938 | 16 放弃分配权的是否同时失去投票权？
【在 l*******s 的大作中提到】
: 两小时时间到，开始讨论吧。
|
l*******s
发帖数: 7316 | 17 没说能放弃分配权，分不好只有死路一条。
【在 w***3 的大作中提到】
: 放弃分配权的是否同时失去投票权？
|
p**s
发帖数: 2707 | |
w***3
发帖数: 938 | 19 弄不懂24如何活着？
如果说不能放弃分配权，是否就是说24号不能说5个宝贝留给你们23个人？
【在 l*******s 的大作中提到】
: 没说能放弃分配权，分不好只有死路一条。
|
K*****2
发帖数: 9308 | 20 0 0 5
1 1 0 3
2 0 1 0 2
1 1 0 1 0 2
2 0 1 0 1 0 1
1 1 0 1 0 1 0 1
2 0 1 0 1 0 1 0 0
1 1 0 1 0 1 0 1 0 0
0 0 1 0 1 0 1 0 1 1 0
估计是错的 |
|
|
w********h
发帖数: 48 | 21 规则不合理啊！要是只剩两个海盗的时候，高个的分，不管怎么分，矮个的不同意，就
可以把高个的扔海里独吞？！
按这个不合理的规则的话。要是有25个海盗，25号的方案会通过。18到24号无论提出什
么方案都会给扔海里。所以答案是17号的方案会被接受。 |
w********h
发帖数: 48 | 22 各海盗的最佳方案：
#2: must die
#3: 005
#4: 1103
#5: 20102 / 02102, min 00102
#6: 110102
#7: 2010101 / 0210101 / 0012101, min 0010101
#8: 11010101
#9: 201010100 / 021010100 / 001210100 / 001012100 / 001010120, min 001010100
#10: 11010101100 / … , min all 0
#11: 10000000004 / … / 00000000014, min 00000000004
#12: must die
#13: 1111100000000 / … / 0000011111000, min all 0
#14: must die
#15: must die
#16: must die
#17: 11111000000000000 / … / 00000000111110000, min all 0
#18: must die
#19: must die
#20: must die
#21: must die
#22: must die
#23: must die
#24: must die
#25: 1111100000000000000000000 / ... / 0000000000001111100000000, min all 0 |
K*****2
发帖数: 9308 | 23 感觉像是对的
001010100
【在 w********h 的大作中提到】
: 各海盗的最佳方案：
: #2: must die
: #3: 005
: #4: 1103
: #5: 20102 / 02102, min 00102
: #6: 110102
: #7: 2010101 / 0210101 / 0012101, min 0010101
: #8: 11010101
: #9: 201010100 / 021010100 / 001210100 / 001012100 / 001010120, min 001010100
: #10: 11010101100 / … , min all 0
|
l*******s
发帖数: 7316 | 24 这就是为什么是24个海盗而不是25个的原因。
【在 w********h 的大作中提到】
: 规则不合理啊！要是只剩两个海盗的时候，高个的分，不管怎么分，矮个的不同意，就
: 可以把高个的扔海里独吞？！
: 按这个不合理的规则的话。要是有25个海盗，25号的方案会通过。18到24号无论提出什
: 么方案都会给扔海里。所以答案是17号的方案会被接受。
|
w********h
发帖数: 48 | 25 还是制定分配方案的海盗也参与投票，得票达到或超过半数通过比较合理。这种规则下
答案又是什么呢？ |
l*******s
发帖数: 7316 | 26 那就是海盗分金的原题了。
【在 w********h 的大作中提到】
: 还是制定分配方案的海盗也参与投票，得票达到或超过半数通过比较合理。这种规则下
: 答案又是什么呢？
|
i****e
发帖数: 642 | 27 No 11 can survive for sure: can always get 5 votes;
No 12 has no plan to get 5 votes, so he will vote for any plan from No 13 to
survive;
No 13 is safe: 1 vote from No 12 and 5 votes from others for gold;
No 14 has no plan;
No 15 will get vote from No 14, but not from No 12 for free, since No 12
knows that No 13 can save him; so No 15 has no plan to get 7 votes;
No 16 can get 2 free votes from No 14 and 15, and 5 gold votes; Not enough;
No 17 is safe, with 3 free votes (No 14~16), plus 5 gold votes;
No 18 has no free votes, so no plan to get 9 votes;
No 19 can get 1 free vote from No 18, but that is far less than enough;
No 20 has 2 free votes, not enough;
No 21 has 3 free votes, not enough;
No 22 has 4 free votes, not enough;
No 23 has 5 free votes, not enough;;
No 24 has 6 free votes, not enough.
So the plan from No 17 will be accepted with 8 votes, 5 gold votes and 3
votes from No 14, 15 and 16.
If there were pirate No 25, he would get 7 free votes from No 18~24, plus 5
gold votes, which is just enough to pass. |
s******8
发帖数: 4192 | 28 为什么数学题要这么血腥暴力。动不动就是你死我活的，要把人扔进海里。不参与分宝
就行了，为啥要扔进海里。 |
K*****2
发帖数: 9308 | |
l*******s
发帖数: 7316 | 30 好吧，下面是从限制级改为辅导级的海盗分宝题。
有24海盗得到了5件相同的价值连城的宝贝，他们准备瓜分这5件宝贝。 但宝贝不能被
切割，他们也不愿跟别人共享宝贝，所以就有人分到宝贝，有人分不到。他们按身高从
矮到高排序，小明最矮，排1号，大明最高，排24号。
首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
案分。否则就把24号开除出社团，海盗一旦被开除就不能参与分配也不能参与投票。
在其他人中，由最高的23号提出分配方案。如果他人中有一半或以上的人同意23号的方
案就按23号的方案分，否则就把23开除出社团，由其他人中最高的22号提出分配方案。
如此类推，直到有被接受的方案为止。
对这些海盗有如下假设：
1.海盗都很聪明。有多聪明呢？他们都会做对这道题。
2.海盗热爱社团，不想被开除。
3.在不被开除的基础上，海盗都想得到尽量多的宝贝。
4.如果不影响自己是否被开除，也不影响自己得到多少宝贝的条件下，海盗都会不同意
分配方
案。
5.海盗都相信数鸟在林不如一鸟在手。也就是说，当前方案中给我n个宝贝，如果当前
方案被否定，我可能得到多于n个宝贝，但也可能少于n个宝贝，那就选择同意当前方案。
现在问题来了：最终会按几号提出的方案分配。
【在 s******8 的大作中提到】
: 为什么数学题要这么血腥暴力。动不动就是你死我活的，要把人扔进海里。不参与分宝
: 就行了，为啥要扔进海里。
|
|
|
l*******s
发帖数: 7316 | 31 好吧，我来总结一下大家的回帖，供板斧参考发包子。
8楼 Terabyte首先给出正确答案，但有猜的嫌疑。这回就给他发包子吧。以后规则改成
每个ID的第一个回帖正确的才有包子。
10楼 plus 答案正确，并在18楼给出关键步骤， 显然是自己作对的。本想请plus给个
详细的过程，但后面很快就有人给出了。
21，22楼 wagnerwash 的步骤是对的。
27楼 imlate 也是对的，但有一个typo，
No 12 has no plan to get 5（应该是6） votes
这个可以有几个变例。其中一个是25楼提出的
制定分配方案的海盗也参与投票，得票达到或超过半数通过。
这样的话，18号的方案，给1到14号中任意5个人每人一个宝贝，会被接受。因为18号用
5个宝贝拿到5票，还有15，16，17三个死忠恼残粉，加上18号1票，正好够9票。
另一变化是，把第5条假设改成，
5.海盗都勇于冒险投资。也就是说，当前方案中给我n个宝贝，如果当前
方案被否定，我可能得到多于n个宝贝，就选择不同意当前方案。 |
b**r
发帖数: 352 | 32 我开始严重怀疑我小学毕业考试时我爸妈给老师塞红包了 |
r****z
发帖数: 12020 | 33 包子已经发放完毕，Terabyte，wagnerwash，imlate 各一，plus 两个，如有误请告知。
谢谢出题，题目很有意思，令人回味，我考虑情况不周全就做错了。
看来本版确实藏龙卧虎呀。
【在 l*******s 的大作中提到】
: 好吧，我来总结一下大家的回帖，供板斧参考发包子。
: 8楼 Terabyte首先给出正确答案，但有猜的嫌疑。这回就给他发包子吧。以后规则改成
: 每个ID的第一个回帖正确的才有包子。
: 10楼 plus 答案正确，并在18楼给出关键步骤， 显然是自己作对的。本想请plus给个
: 详细的过程，但后面很快就有人给出了。
: 21，22楼 wagnerwash 的步骤是对的。
: 27楼 imlate 也是对的，但有一个typo，
: No 12 has no plan to get 5（应该是6） votes
: 这个可以有几个变例。其中一个是25楼提出的
: 制定分配方案的海盗也参与投票，得票达到或超过半数通过。
|
l*******s
发帖数: 7316 | 34 这不是小学数学题。你可能把“数学小奖赛”看成“小学赛”了。
我在本版出的题都是中学里聪明学生水平的题目.
只有那个Catalan number出难了，幸好有丝丝坐阵，亲自出面解答了。
【在 b**r 的大作中提到】
: 我开始严重怀疑我小学毕业考试时我爸妈给老师塞红包了
|
s*******e
发帖数: 1630 | 35 #24说，如果不同意我方案要我跳海，我就抱着所有宝物跳海，同意我方案我就拿一个
，剩余的其他人自己想怎么分 |
T******e
发帖数: 18290 | 36 尼玛我能坦白我只是在捣乱吗，本来准备数到24的，没好意思就只数到17
知。
【在 r****z 的大作中提到】
: 包子已经发放完毕，Terabyte，wagnerwash，imlate 各一，plus 两个，如有误请告知。
: 谢谢出题，题目很有意思，令人回味，我考虑情况不周全就做错了。
: 看来本版确实藏龙卧虎呀。
|
A*********r
发帖数: 2301 | 37 你是靠着在拓大妈上面才拿到的包子，你这包子应该分给下面的拓大妈
【在 T******e 的大作中提到】
: 尼玛我能坦白我只是在捣乱吗，本来准备数到24的，没好意思就只数到17
:
: 知。
|
T******e
发帖数: 18290 | 38 什么上面下面的，听起来好淫乱
【在 A*********r 的大作中提到】
: 你是靠着在拓大妈上面才拿到的包子，你这包子应该分给下面的拓大妈
|
A*********r
发帖数: 2301 | 39 你滚出去！
【在 T******e 的大作中提到】
: 什么上面下面的，听起来好淫乱
|
O**e
发帖数: 569 | |
|
|
r******6
发帖数: 18 | 41 假如最后剩下一个人（1号存活，我们命名为状态A），则1号得全部宝贝，游戏结束，
因此A是个最终稳定态。我们定义最终稳定态是到达这个状态之后游戏必定结束！这个
最终稳定态随着我们的分析会发生更新，看后文自明。
假如最后剩下两个人了（2号和1号，我们命名为状态B），则1号会投死2号，然后转移
到A状态，因为B状态是个暂态，必定会转移到A状态。以上道理2号懂，所以假如最后剩
下三个人了（状态C），则无论3号如何分宝贝，2号为避免到达状态B则必须同意3号的
分配方案，因此3号可以霸占全部宝贝，游戏结束，所以状态C是新的最终稳定态。这个
最终稳定态也是个无条件最终稳定态。
状态：C（无条件稳定态）
船员号：1 2 3
宝贝数：0 0 5
假如最后剩下4个人（状态D），聪明的4号肯定不希望达到状态C，但他无论怎么分，3
号肯定投反对，2号无所谓，1号无所谓，所以4号的策略是给2号和1号每人一件宝贝，
自己得3件宝贝（2号会想如果投死4号到达C状态，自己则会一件宝贝都拿不到，1号会
想如果投死4号到达C状态自己也是一件宝贝都拿不到）。所以状态D会到达最终稳定态
，不过我们称这个稳定态为条件最终稳定态。条件是1号和2号有最基本收益。
状态：D
船员号：1 2 3 4
宝贝数：1 1 0 3
假如最后剩下5个人（状态E），聪明的5号知道状态D是条件最终稳定态，在D状态下1、
2、4号都有稳定收益。因此状态E肯定不会是无条件最终稳定态，而且4号肯定希望转移
到D状态，除非他的收益大于3。但是分给4号4个宝贝还不如给3号一个宝贝，因为3号在
状态D的收益为0。至于1号和2号，他们在D状态下就有1个宝贝的期望收益，所以如果在
状态E下还继续保持这种分配是有风险的，但也并不需要继续分宝贝给1和2号，只需要
给1号两个宝贝，2号不给，就可以保证1号绝对支持。因此，状态E也是个条件最终稳定
态，1号2个宝贝，3号1个宝贝，自己2个宝贝，2号和4号没有宝贝。
状态：E
船员号：1 2 3 4 5
宝贝数：2 0 1 0 2
（1号和2号构成互斥收益，也即赢着吃2个宝贝，剩下的一个即便给了1个宝贝还是会投
反对票，因为他会冒险在下一轮中独吃互斥收益）
假如最后剩下6个人（状态F），聪明的6号知道状态E是条件最终稳定态，因此为了避免
自己被投死，他需要得到3个人的支持。因为在状态E下4号的收益为0，因此分配4号一
个宝贝能获得4号支持，这个是最有效率的投资。1号和2号是双斥收益，因为在状态E下
，只能有一个人收益2个宝贝（如果在F状态下给1号两个宝贝，1号肯定不愿意冒险在状
态E下收益被2号获取，从而1号会赞成F状态）。3号要赞成则必须收益为2个宝贝，5号
要赞成则必须收益为3个宝贝。所以对于状态F而言，如果要成为条件稳定状态，则分配
结果是：1号两个宝贝，3号两个宝贝，4号一个宝贝。五个人投票，三个人会赞成。但
是6号自己则没有任何宝贝收益，但能活命！
状态：F
船员号：1 2 3 4 5 6
宝贝数：2 0 2 1 0 0
（1号和2号构成互斥）
假如最后剩下7个人（状态G），聪明的7号知道状态F是条件最终稳定态，也知道状态F
下分配结果，因此最为有利的投资是给状态F下收益最小的人。于是4号（2个宝贝），5
号（1个宝贝），6号（1个宝贝），自己得1个宝贝。
状态：F
船员号：1 2 3 4 5 6 7
宝贝数：2 0 0 0 1 1 1
1,2,4号组成互斥收益
假如最后剩下8个人（状态H）：
状态：H
船员号：1 2 3 4 5 6 7 8
宝贝数：2 0 1 0 2 0 0 0
（1,2,4号会争夺互斥收益，因此给2或4是多余的，除非每人都给到2个宝贝，但宝贝总
数目限制了）
假如最后剩下9个人（状态I）：条件稳定态
状态：I
船员号：1 2 3 4 5 6 7 8 9
宝贝数：2 0 0 0 0 1 1 1 0
（1,2,3,4号会争夺互斥收益）
假如最后剩下10个人（状态J）：坍缩！
状态：J
船员号：1 2 3 4 5 6 7 8 9 10
宝贝数：2 0 0 0 ？ 2 0 0 ？ 0
（1,2,3,4号会争夺互斥收益，拿到3张反对票（除非花费4个宝贝，但这样一来肯定拿
不到5张赞成票）；6,7,8也会争夺互斥收益，拿到2张反对票（除非花费4个宝贝，但同
样会拿不到5张赞成票）。所以状态J是不稳定状态，是10号极力避免的。
假如最后剩下11个人（状态K）：坍缩！
状态：K
船员号：1 2 3 4 5 6 7 8 9 10 11
宝贝数：2 0 0 0 1 ？ 0 0 0 0 0
K状态可以无条件取得10号的支持，但同样因为1,2,3,4号互斥收益以及6,7,8号互斥收
益，因此也会坍缩到状态J最后到达I状态。
假如最后剩下12个人（状态L）：坍缩！
状态：L
船员号：1 2 3 4 5 6 7 8 9 10 11 12
宝贝数：2 0 0 0 1 ？ 0 0 1 0 0 0
L状态可以无条件取得10号和11号的支持，但11个人需要6张赞成票，同样会坍缩。
假如最后剩下13个人（状态M）：条件稳定态
状态：M
船员号：1 2 3 4 5 6 7 8 9 10 11 12 13
宝贝数：2 0 0 0 1 0 0 0 1 0 0 0 1
（1,2,3,4号是互斥收益，6,7,8互斥收益关系在此状态下解除）
假如最后剩下14个人（状态N）：坍缩
状态：N
船员号：1 2 3 4 5 6 7 8 9 10 11 12 13 14
宝贝数：0 0 0 0 0 1 1 1 0 1 1 0 0 0
有了状态M垫底，10~12号有了收益预期。但13人一半或一半以上标志着需要6个宝贝才
能最低限度满足6张赞成票。但此时只有5个宝贝。所以该状态必定坍缩，但是可以得到
5张赞成票！
假如最后剩下15个人（状态O）：坍缩
状态：O
船员号：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
同样的会坍缩！
...
假如最后剩下17个人（状态Q）：条件稳定态
状态：Q
因为14,15,16都是无条件赞成，因此用5张票买另外5个赞成是可能的，于是达到条件稳
定态：
船员号：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
宝贝数：0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0
此时，1,2,3,4号的互斥解除。根据对坍缩态的理解，再对比M状态，状态Q是条件稳定
态。此时12~17均有了获利企图！但是从此5张票能获得5个赞成！
假如最后剩下18个人（状态Q）：坍缩，需要9赞成，但是有5赞成
假如最后剩下19个人（状态.）：坍缩，需要9赞成，但是有6赞成
假如最后剩下20个人（状态.）：坍缩，需要10赞成，但是有7赞成
假如最后剩下21个人（状态.）：坍缩，需要10赞成，但是有8赞成
假如最后剩下22个人（状态.）：坍缩，需要11赞成，但是有9赞成
假如最后剩下23个人（状态.）：坍缩，需要11赞成，但是有10赞成
假如最后剩下24个人（状态.）：坍缩，需要12赞成，但是有11赞成
假如最后剩下25个人（状态X）：条件稳定态，需要12赞成，有12赞成（其中18~24号是
无条件赞成），分配方案如下：
给1~5,9,12~17号，随机找5个人，每个人一个宝贝：5票
18~24号，无条件赞成：7票
方案通过！ |
r****z
发帖数: 12020 | 42 小奖赛是指答对最多两个包子，奖金不足以养家糊口。
【在 l*******s 的大作中提到】
: 这不是小学数学题。你可能把“数学小奖赛”看成“小学赛”了。
: 我在本版出的题都是中学里聪明学生水平的题目.
: 只有那个Catalan number出难了，幸好有丝丝坐阵，亲自出面解答了。
|
r****z
发帖数: 12020 | 43 已经看出来了。不过严格来说是因为规则不够严密，所以这个包子吃得也不是没有道理。
【在 T******e 的大作中提到】
: 尼玛我能坦白我只是在捣乱吗，本来准备数到24的，没好意思就只数到17
:
: 知。
|
