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种最佳方案。
本题的答案是我单独想出的,所以可能有不足之处,欢迎提出意见,以修正不足。