Redian新闻
>
丝丝杯数学小奖赛:海盗分宝
avatar
丝丝杯数学小奖赛:海盗分宝# Joke - 肚皮舞运动
I*p
1
【 以下文字转载自 Reunion 讨论区 】
发信人: Inevergiveup (I never give up!), 信区: Reunion
标 题: 请问洛杉矶B2延期
发信站: BBS 未名空间站 (Fri Mar 11 12:49:35 2016, 美东)
请问洛杉矶B2延期从他们收到信到收到接受受理一般需要多长时间?
我上周四快递寄出去,到现在一周了,还没有收到受理通知
请问办理过的同学,你们一般多长时间收到接受受理的通知?
谢谢
avatar
l*s
2
应拖板斧之邀出题,活跃版面。还是老规矩:两小时内请只贴答案,别贴解法。两小时
内答对的都有包子。两小时后贴解法,简明易懂的解法有包子。
大家先别急着放狗,因为题目跟标准的海盗分金不一样。
有24海盗得到了5件相同的价值连城的宝贝,他们准备瓜分这5件宝贝。 但宝贝不能被
切割,他们也不愿跟别人共享宝贝,所以就有人分到宝贝,有人分不到。他们按身高从
矮到高排序,小明最矮,排1号,大明最高,排24号。
首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
案分。否则就把24号扔到海里,由其他人中最高的23号提出分配方案。
如果他人中有一半或以上的人同意23号的方案就按23号的方案分,否则就把23号扔到海
里,由其他人中最高的22号提出分配方案。
如此类推,直到有被接受的方案为止。
对这些海盗有如下假设:
1.海盗都很聪明。有多聪明呢?他们都会做对这道题。
2.海盗都想活命。
3.在活命的基础上,海盗都想得到尽量多的宝贝。
4.如果不影响自己活命,也不影响自己得到多少宝贝的条件下,海盗都会不同意分配方
案。
5.海盗都相信数鸟在林不如一鸟在手。也就是说,当前方案中给我n个宝贝,如果当前
方案被否定,我可能得到多于n个宝贝,但也可能少于n个宝贝,那就选择同意当前方案。
现在问题来了:最终会按几号提出的方案分配。
avatar
H*g
3
lui
avatar
c*w
4
12
avatar
r*z
5
13

【在 l*******s 的大作中提到】
: 应拖板斧之邀出题,活跃版面。还是老规矩:两小时内请只贴答案,别贴解法。两小时
: 内答对的都有包子。两小时后贴解法,简明易懂的解法有包子。
: 大家先别急着放狗,因为题目跟标准的海盗分金不一样。
: 有24海盗得到了5件相同的价值连城的宝贝,他们准备瓜分这5件宝贝。 但宝贝不能被
: 切割,他们也不愿跟别人共享宝贝,所以就有人分到宝贝,有人分不到。他们按身高从
: 矮到高排序,小明最矮,排1号,大明最高,排24号。
: 首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
: 案分。否则就把24号扔到海里,由其他人中最高的23号提出分配方案。
: 如果他人中有一半或以上的人同意23号的方案就按23号的方案分,否则就把23号扔到海
: 里,由其他人中最高的22号提出分配方案。

avatar
H*g
6
我就押个14吧
avatar
T*e
7
15

【在 H********g 的大作中提到】
: 我就押个14吧
avatar
T*e
8
16

【在 T******e 的大作中提到】
: 15
avatar
T*e
9
17

【在 T******e 的大作中提到】
: 16
avatar
H*g
10
我再押个“大”
avatar
p*s
11
17
avatar
K*2
12
11,押小吧
avatar
i*l
13
4
edit: 不对,是8
avatar
f*w
14
24啊

【在 l*******s 的大作中提到】
: 应拖板斧之邀出题,活跃版面。还是老规矩:两小时内请只贴答案,别贴解法。两小时
: 内答对的都有包子。两小时后贴解法,简明易懂的解法有包子。
: 大家先别急着放狗,因为题目跟标准的海盗分金不一样。
: 有24海盗得到了5件相同的价值连城的宝贝,他们准备瓜分这5件宝贝。 但宝贝不能被
: 切割,他们也不愿跟别人共享宝贝,所以就有人分到宝贝,有人分不到。他们按身高从
: 矮到高排序,小明最矮,排1号,大明最高,排24号。
: 首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
: 案分。否则就把24号扔到海里,由其他人中最高的23号提出分配方案。
: 如果他人中有一半或以上的人同意23号的方案就按23号的方案分,否则就把23号扔到海
: 里,由其他人中最高的22号提出分配方案。

avatar
l*s
15
两小时时间到,开始讨论吧。
avatar
d*o
16
6号
晚了吗?
好像不对
猜个10号吧

【在 l*******s 的大作中提到】
: 应拖板斧之邀出题,活跃版面。还是老规矩:两小时内请只贴答案,别贴解法。两小时
: 内答对的都有包子。两小时后贴解法,简明易懂的解法有包子。
: 大家先别急着放狗,因为题目跟标准的海盗分金不一样。
: 有24海盗得到了5件相同的价值连城的宝贝,他们准备瓜分这5件宝贝。 但宝贝不能被
: 切割,他们也不愿跟别人共享宝贝,所以就有人分到宝贝,有人分不到。他们按身高从
: 矮到高排序,小明最矮,排1号,大明最高,排24号。
: 首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
: 案分。否则就把24号扔到海里,由其他人中最高的23号提出分配方案。
: 如果他人中有一半或以上的人同意23号的方案就按23号的方案分,否则就把23号扔到海
: 里,由其他人中最高的22号提出分配方案。

avatar
w*3
17
放弃分配权的是否同时失去投票权?

【在 l*******s 的大作中提到】
: 两小时时间到,开始讨论吧。
avatar
l*s
18
没说能放弃分配权,分不好只有死路一条。

【在 w***3 的大作中提到】
: 放弃分配权的是否同时失去投票权?
avatar
p*s
19
第17个把宝贝分给1到13中任意5个
avatar
w*3
20
弄不懂24如何活着?
如果说不能放弃分配权,是否就是说24号不能说5个宝贝留给你们23个人?

【在 l*******s 的大作中提到】
: 没说能放弃分配权,分不好只有死路一条。
avatar
K*2
21
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
估计是错的
avatar
w*h
22
规则不合理啊!要是只剩两个海盗的时候,高个的分,不管怎么分,矮个的不同意,就
可以把高个的扔海里独吞?!
按这个不合理的规则的话。要是有25个海盗,25号的方案会通过。18到24号无论提出什
么方案都会给扔海里。所以答案是17号的方案会被接受。
avatar
w*h
23
各海盗的最佳方案:
#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
avatar
K*2
24
感觉像是对的

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

avatar
l*s
25
这就是为什么是24个海盗而不是25个的原因。

【在 w********h 的大作中提到】
: 规则不合理啊!要是只剩两个海盗的时候,高个的分,不管怎么分,矮个的不同意,就
: 可以把高个的扔海里独吞?!
: 按这个不合理的规则的话。要是有25个海盗,25号的方案会通过。18到24号无论提出什
: 么方案都会给扔海里。所以答案是17号的方案会被接受。

avatar
w*h
26
还是制定分配方案的海盗也参与投票,得票达到或超过半数通过比较合理。这种规则下
答案又是什么呢?
avatar
l*s
27
那就是海盗分金的原题了。

【在 w********h 的大作中提到】
: 还是制定分配方案的海盗也参与投票,得票达到或超过半数通过比较合理。这种规则下
: 答案又是什么呢?

avatar
i*e
28
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.
avatar
s*8
29
为什么数学题要这么血腥暴力。动不动就是你死我活的,要把人扔进海里。不参与分宝
就行了,为啥要扔进海里。
avatar
K*2
30
这题就完事了?
avatar
l*s
31
好吧,下面是从限制级改为辅导级的海盗分宝题。
有24海盗得到了5件相同的价值连城的宝贝,他们准备瓜分这5件宝贝。 但宝贝不能被
切割,他们也不愿跟别人共享宝贝,所以就有人分到宝贝,有人分不到。他们按身高从
矮到高排序,小明最矮,排1号,大明最高,排24号。
首先由最高的24号提出分配方案。如果其他人中有一半或以上的人同意该方案就按该方
案分。否则就把24号开除出社团,海盗一旦被开除就不能参与分配也不能参与投票。
在其他人中,由最高的23号提出分配方案。如果他人中有一半或以上的人同意23号的方
案就按23号的方案分,否则就把23开除出社团,由其他人中最高的22号提出分配方案。
如此类推,直到有被接受的方案为止。
对这些海盗有如下假设:
1.海盗都很聪明。有多聪明呢?他们都会做对这道题。
2.海盗热爱社团,不想被开除。
3.在不被开除的基础上,海盗都想得到尽量多的宝贝。
4.如果不影响自己是否被开除,也不影响自己得到多少宝贝的条件下,海盗都会不同意
分配方
案。
5.海盗都相信数鸟在林不如一鸟在手。也就是说,当前方案中给我n个宝贝,如果当前
方案被否定,我可能得到多于n个宝贝,但也可能少于n个宝贝,那就选择同意当前方案。
现在问题来了:最终会按几号提出的方案分配。

【在 s******8 的大作中提到】
: 为什么数学题要这么血腥暴力。动不动就是你死我活的,要把人扔进海里。不参与分宝
: 就行了,为啥要扔进海里。

avatar
l*s
32
好吧,我来总结一下大家的回帖,供板斧参考发包子。
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个宝贝,就选择不同意当前方案。
avatar
b*r
33
我开始严重怀疑我小学毕业考试时我爸妈给老师塞红包了
avatar
r*z
34
包子已经发放完毕,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楼提出的
: 制定分配方案的海盗也参与投票,得票达到或超过半数通过。

avatar
l*s
35
这不是小学数学题。你可能把“数学小奖赛”看成“小学赛”了。
我在本版出的题都是中学里聪明学生水平的题目.
只有那个Catalan number出难了,幸好有丝丝坐阵,亲自出面解答了。

【在 b**r 的大作中提到】
: 我开始严重怀疑我小学毕业考试时我爸妈给老师塞红包了
avatar
s*e
36
#24说,如果不同意我方案要我跳海,我就抱着所有宝物跳海,同意我方案我就拿一个
,剩余的其他人自己想怎么分
avatar
T*e
37
尼玛我能坦白我只是在捣乱吗,本来准备数到24的,没好意思就只数到17

知。

【在 r****z 的大作中提到】
: 包子已经发放完毕,Terabyte,wagnerwash,imlate 各一,plus 两个,如有误请告知。
: 谢谢出题,题目很有意思,令人回味,我考虑情况不周全就做错了。
: 看来本版确实藏龙卧虎呀。

avatar
A*r
38
你是靠着在拓大妈上面才拿到的包子,你这包子应该分给下面的拓大妈

【在 T******e 的大作中提到】
: 尼玛我能坦白我只是在捣乱吗,本来准备数到24的,没好意思就只数到17
:
: 知。

avatar
T*e
39
什么上面下面的,听起来好淫乱

【在 A*********r 的大作中提到】
: 你是靠着在拓大妈上面才拿到的包子,你这包子应该分给下面的拓大妈
avatar
A*r
40
你滚出去!

【在 T******e 的大作中提到】
: 什么上面下面的,听起来好淫乱
avatar
r*6
42
假如最后剩下一个人(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票
方案通过!
avatar
r*z
43
小奖赛是指答对最多两个包子,奖金不足以养家糊口。

【在 l*******s 的大作中提到】
: 这不是小学数学题。你可能把“数学小奖赛”看成“小学赛”了。
: 我在本版出的题都是中学里聪明学生水平的题目.
: 只有那个Catalan number出难了,幸好有丝丝坐阵,亲自出面解答了。

avatar
r*z
44
已经看出来了。不过严格来说是因为规则不够严密,所以这个包子吃得也不是没有道理。

【在 T******e 的大作中提到】
: 尼玛我能坦白我只是在捣乱吗,本来准备数到24的,没好意思就只数到17
:
: 知。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。