智星论坛(IQSTAR BBS)
 
打印

L2[擂台]强盗分钻石(****)[已解]

L2[擂台]强盗分钻石(****)[已解]

显然我的答案和lyy003准备的答案不一致。这就更让我想知道你和我的思路哪里出现了不同!
建议lyy003将自己的结果提前公布,这样更利于大家讨论,何必自己弄个时限来限制自己,而且,这个帖子在我来之前很久也没有人应了,想必除了这里已经出现过的网友之外,也会很少再有人发言了。
同意现在公布的网友请出来支持一下。(nbzhao, likeme,夏日狂龙,……快!)

TOP

L2[擂台]强盗分钻石(****)[已解]

同意,同意,我都快憋死了!
[fly]每天灌水五分钟,让偶做个大头葱[/fly]

TOP

L2[擂台]强盗分钻石(****)[已解]

同意!
于千万人之中,遇见你所遇见的人;于千万年之中,时间的无涯荒野里,没有早一步,也没有晚一步,刚巧赶上了

TOP

L2[擂台]强盗分钻石(****)[已解]

看着这么热闹,我也算了一下,惑今兄的推理基本没问题。
到199时,同意,最后一步,好象有101种方法。
在199中得到0的是100人,得到2的是1人,这101人中,在200个强盗时,只有100人可以得到1块钻石。101人中选100,共有101种方法。
得到1块钻石的人和1号强盗投赞成票。
我很笨,但很勤奋!

TOP

L2[擂台]强盗分钻石(****)[已解]

的确漏了一点!
换句话说,我在上贴所列的200人的方案中,所有拿1个钻石的人(共100人)都有可能交出钻石给199号。而不仅仅是1号和2号!
我想,这下应该全了吧……

TOP

L2[擂台]强盗分钻石(****)[已解]

谁能用一段话表达清楚N=88时1号的分配方案?
谁能用一段话表达清楚N=145时1号的分配方案?

TOP

L2[擂台]强盗分钻石(****)[已解]

答案:(1)N=4时,1号要拉拢2个人同意自己的方案,显然要让2号肯定同意自己的方案是困难的,因为2号若轮到自己分配,可以独吞100枚;所以1号必须要让3号,4号肯定同意自己的方案,而3号,4号在N=3时的方案中一枚也不能得到,1号只需给3号,4号每人1枚即可。1号的唯一最佳方案为(98,0,1,1)
(2)N=5时,1号要拉2票。我们只需关注N=4时的最佳方案(98,0,1,1),1号拉票的对象肯定是上一方案中一枚未得的人,即上一方案中的2号,也就是本方案中的3号,
给他一枚足矣。但是1号必须还要拉1票,只能从N=4方案中的3号,4号身上想办法,为了让他们中的1人能肯定赞成自己的方案,必须给此人2枚。所以,1号的最佳方案有两种,分别是(97,0,1,2,0)或(97,0,1,0,2)。
(3)N=6时,1号要拉3票。很明显,N=5方案中得0枚的人即为拉拢的对象,现在还少一票,有意思的是,依本题的条件,上一方案中得2枚的人也为拉拢对象,只需给他一枚,他即同意,因为N=5有两种最佳方案,他事先并不知道N=5时的1号会采取哪种方案,所以在这一轮中他能够得1枚,总比在下一轮方案中一枚未得要好,所以他必会投赞成票。这样,1号的最佳方案又是唯一的了:(97,0,1,0,1,1)
(4)N=7时,同N=6,1号要拉3票。只需将N=6方案中的0改为1,其中的一个1改为2即可。1号的最佳方案有三种(96,0,1,2,1,0,0),(96,0,1,0,1,2,0),(96,0,1,0,1,0,2)。
(5)N=8时,1号要拉4票。N=7方案中有3个0,1个2,正好是4个。给他们每人1枚,即可。现在可看出,N=7方案中得2枚的那人若在此轮中得到1枚应该很满意了,因为他只有1/3的机会能够在N=7方案中获得2枚。可见,此时1号又只有1种最佳方案了:(96,0,1,0,1,0,1,1)。1号得的钻石数同N=7时的1号。
………………………………………………………………………………………………
………………………………………………………………………………………………
此时,发现规律了吗?N>4时
当N为偶数时,只有一种最佳分配方案,1号得(100-N/2)枚,2号得0枚,3号得1枚,4号得0枚,……,奇数号得1枚,偶数号得0枚,N-1号,N号得1枚。
最佳方案为:(100-N/2,0,1,0,1,0,1,0,1,……,0,1,0,1,0,1,0,1,1)
当N为奇数时,有(N-1)/2种最佳分配方案,1号得[100-(N+1)/2]枚,2号得0枚,3号得1枚,5号得1枚,奇数号得1枚,4号,6号,偶数号,……,N-1号,N号中的某一个人得2枚,其余得0枚。(N-1)/2个最佳方案为:(100-(N+1)/2,0,1,0,1,0,1,……,0,1,0,0)将4号开始的某个0改为2即可。
如果你以为做到这一步就完了,那就错了。注意到我的前提是N>4,并未指出上限,
试想当N=198时,只有唯一的方案,自己还可得1枚,2号得0枚。N的上限是198。
N=199时,1号为了保命,自己得0枚,照前面的结论,2号应得0枚,但是,这时你给他2枚,你说他答不答应。所以这时的100个最佳方案为(0,0,1,0,1,0,1……,0,1,0,1,0,0)
将2号开始的某个0改为2即可。
N=200时,1号当然得0枚,2号,3号,5号,7号,……,97号,99号,100号
共101个人中任取100个人,每人1枚钻石。其余的人得0枚。共有101种最佳方案。
本题的答案是我单独想出的,所以可能有不足之处,欢迎提出意见,以修正不足。

TOP

当前时区 GMT+8, 现在时间是 2008-11-21 21:14

Processed in 0.058200 second(s), 8 queries, Gzip enabled.


Skin By Wing