用数学归纳法思考宝石海盗问题
1. 问题描述5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。
他们决定这幺分：
1。抽签决定自己的号码（1，2，3，4，5）
2。首先，由1号提出分配方案，然后大家5人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
3。如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
4。以次类推。
条件： 每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。
问题： 第一个海盗提出怎样的分配方案才能够使自己的收益最大化？
2. 问题的域
a) 海盗数量N, 不可为负数
b) 当海盗数量N = 1时,该海盗自动获得所有宝石
c) 当N = 2时, 因不可能有半数人同意,首个提出的方案(除第一个提出方案的人把所有宝石给第二个人), 则此时, 首个提出方案的海盗必死(或得不到任何东西)
d) 当N=3时, 首个海盗只需给 第2个人一个宝石即可, 因为,如果首个死了, 第二个必死(此时2:1)
e) 当N= 4时, 首个给最后那个和倒数第二个各一个宝石即可,因为如果他死了, 就回到了情况d(3:1)
f) 当N = 5 时, 同情况e(当不以多杀人为准则时,因为无论此时首个提出方案的人死于否,宝石分配方案都不会在少一人的情况下发生变化) 此时3:2
根据上述的分析,可知问题的域为(N>=3)
3. N= 3的情况
N = 3时, 首个海盗只需给 第2个人一个宝石即可, 因为,如果首个死了, 第二个必死(此时2:1)
4. N= k+1的情况
a) N= k+1 为 奇数, 首个提出方案的人要做如下分配
i. 分给倒数第一个和倒数第二个人各一个宝石
ii. 分配(N-1)/2 -2 个宝石,给第二个人之后的(N-1)/2-2个人, (如此说(N-1)/2-2 > 0)
b) N= k+1 为 偶数, 首个提出方案的人要做如下分配
i. 分给倒数第一个和倒数第二个人各一个宝石
ii. 分配N/2 -2 个宝石,给第二个人之后的N/2-2个人, (如此说N/2-2 > 0)
5. 用归纳法证明情况
a) 证明4a
i. 已证明N=3时,成立
ii. 设N=K时,(K为偶数)成立
iii. 则,N=K+1时,N为奇数
此时,分1个给倒数第一个和倒数第二个,他们必然同意此方案,因为,即使此时提出方案的人死了,也不可能使他们获得更多的宝石
再分(N-1)/2-2个宝石,给第二个人之后的(N-1)/2-2个人, 必有(N-1)/2-2个人同意此方案,因为,当当前提出方案的人死后,并不能使他们多获得宝石,相反,第3个人还会少获得宝石
因此,此时同意方案的人数为 2+(N-1)/2-2+1
iv. 此时,问题变为 证明 (N-1)/2+1 > N/2 为真, 可证明此式为真
v. 因此证明N=k+1,N为奇数时,成立
vi. 因为,N>=3
又因为, N=3时成立
又N=k+1时成立
vii. 固证明, 4a成立
b) 证明4b
i. 同理, 不再另行证明
--------------------编程问答-------------------- 4a的证明 应该为
a) 证明4a
i. 已证明N=3时,成立
ii. 设N=K时,(K为偶数)成立
iii. 则,N=K+1时,N为奇数
因为,N=K,(K为偶数)成立, 因此,有倒数第一和第二及当前的第4个起的N/2-2-1个人有一个宝石,此时使他们同样拥有一个宝石就可以保证他们同意当前方案(利益不变则少杀人的原则), 因此,此时有 2+N/2-2-1=N/2-1个人同意此方案,再计算本人 , 如不改变N=K时的方案,有 N/2-1+1= N/2个人同意此方案, 仍未超过半数.
固,此时给当前第3个人一个宝石, 他必同意此方案,因为,如果当前提出方案的人死了, 他将什么也得不到.
此时,同意的人数为 N/2+1, 超过半数,
所以4a 成立
--------------------编程问答-------------------- up --------------------编程问答-------------------- 有一个问题，因为必须过半数才成立，问题里没有提到少杀人原则，只提到利益，就是宝石数量，主要宝石数量一样，海盗就没有坚定的立场了，不能把少杀一人的功德折算成一颗宝石的一部分来计算。
三个人时，分配 99 1 0 可以获得通过，1 1 0， 2：1
四个人时，必须分配 97 0 2 1才可以获得通过 1 0 1 1， 3：1。如果时 98 0 1 1，对比一下，倒数第二个获得的数量都是1，没有增长，也没有减少，所以同不同意所获都一样，所以倒数第二人的一票是不确定的。 --------------------编程问答-------------------- 这个问题好费脑子，哈哈 --------------------编程问答-------------------- 我觉得不管你给最后一个海盗多少，他都是不同意的，你没有必要给最后一个海盗，任何东西。除非，条件修改为 只要半数同意，就可以通过方案 --------------------编程问答-------------------- TO Linux7985
在大于3个海盗的情况下, 给最后一个海盗宝石,是可以起到,使他同意计划的作用的
因为, 当前面的海盗都死光, 回到3个海盗的状态时, 最后那个海盗将不能得到任何宝石
当然,这一切都是建立在, 利益不变的情况下,少杀人的前提下的 --------------------编程问答-------------------- 你自己把思路都罗列出来了，应该很好解决了呀！
补充：.NET技术 , C#
