从海盗分钻石来看数学归纳法

-

话说有100颗钻石，有5个海盗去分这100颗钻石，每个海盗都绝顶聪明。所谓绝顶聪明就是每个海盗到底同不同意某一个分配方案，只会考虑一下这个方案是否能够让他获得最大化利润，如果是他就同意如果不是他就不同意。为了公平起见他们决定抓阄，去抓阄决定到底按照什么顺序提供方案，其抓阄结果是先1号提再2号提，再3号再4号再5号，按这个顺序方案提。为了公平起见，他们规定了任一个方案如果不能让50%的人通过的话这个就将为扔到大海里面。什么意思呢，就是先1号提方案，1号提完之后如果总共的这5个人达不到50%通过，1号就被扔到海中就剩4个人了，然后再2号提方案，然后2号所提的方案还不能让剩下的这4个人中的50%也就是两个人通过的话，2号也将被扔到大海中。最后问题问的是如果你是1号的话你怎么提方案，能够让你获得最大化利润且你还不会被扔到大海之中。

在这里，数学归纳法帮了我们的大忙。它告诉我们，当规律不变时，那么最初的最小值的规律点也就是最大值是完全一摸一样的。

如果只有一个人分这100颗钻石，这100颗全给自己，对吧。当有两个人时，一个1号一个2号，要求是50%的人通过就可以了，也就是说两个人中只要一个人通过就可以了，而这一个就是他自己，所以当只有两个人时，1号所提方案仍旧是把100颗全给自己。

如果是三个人呢？由于任意一个海盗到底同不同意某一个方案，只会根据这个海盗所提方案到底能不能让自己获得最大化利润去决定，那我们可以想一下当有3个人时，1号怎么提方案呢？1号会想2号永远不同意，因为2号知道，只要能把1号扔到大海里的话，就将只剩两个人，而刚才我们已经算过了，当只有两个人时，他会把东西全给自己，所以我们知道，当有3个人时，2号永远不同意，2号知道只要没有了1号，我就可以获得100颗钻石。那既然2号永远不同意，那对于1号这个人而言就不用拉拢2号了。只要拉拢3号就可以了，只要让3号同意就可以了。而我们知道3号是很害怕1号被扔到大海之中的，因为如果一旦1号被扔到大海之中，在只剩两个人的情况之下，2号他将把钻石全分配给自己，而这时候3号将一颗钻石都获得不到，因此我只要给3号1颗，他就一定会同意，因为他要不同意的话连1颗都获得不到，于是我们就知道了3个人的方案，那就是99、0、1。也就是说一个人是100，两个人时是100、0，三个人时是99,、0、1。

那同理再往下，4个人时应该是99、0、1、0，给自己99颗，2号0颗，3号1颗，4号0颗；5个人时就应该是98、0、1、0、1。

这就是完整的钻石分配方案，也是数学归纳法运用的一个典型案例。由此我们知道数学归纳法的思想也就是你在一个计算复杂时，用最简单的计算，然后从简单的开始，往复杂的方向递推的一个过渡