關於海盜分寶石的題目

今日世界朋友出的題目，和原題目有些出入。原題目的假設條件是投票者不包括分配人。

如果假設條件中，投票者包括分配人。那麽在4 號分寶石的時候，推理就出問題了。因為這時候隻有兩個人，4 號和 5 號，4 號必然投自己的讚成票，那麽按題目規定，讚成票已經達到50%，則 4 號的方案必然通過。5 號根本沒有任何機會。（100，0）

這樣 3 號來分的話，他隻需要給 5 號一個寶石，就可以爭取到他的票，加上自己的讚成票，2：1，於是通過。（99，0，1）

加入 2 號，為了讓自己獲得寶石是數目最多，他應該這樣分，（99，0，1，0），這樣，他可以獲得自己的讚成票，和 4 號的讚成票。放棄3 號，5 號。

加入 1 號，應該這樣分（98，0，1，0，1）。就可獲得自己的票，3 號的票，和 5 號的票。

不知道大家注意到沒有，如果包含了自己的票數。那麽分配的方案就變得十分簡單，自己後一號碼的人不給，隔一個給一個。這是因為自己的票數一旦加入，在剩餘的人中，隻需要少數通過就可以了（加自己，正好半數）。

這樣也失去了題目的複雜性。


原題目是這樣的：100個寶石，5 個海盜，不變。分配次序不變。條件是：不包括分配者，剩餘的人投票，半數及以上通過，則分配。若少於半數同意，則把分配者丟入海裏。同時，還有一個重要條件（為什麽重要，大家可以仔細想，這裏賣個關子）：在利益相同的情況下，海盜傾向於把人丟進海裏。


































這樣，題目的解答比較複雜了，但基本思想，也就是計算機學裏常提到的遞歸思想：

假設沒有123 號，隻有 4 5 號，那麽無論4 號怎麽分，5 號都反對，這樣，丟4 號入海，自己全得，還沒有潛在威脅。

這時加入3 號。

3 號很清楚，如果4 號不同意自己的分配方案，則自己被丟入海後，就是上麵這個情況，4 號必死，所以，無論 3 號怎麽分，4 號都必同意，則3 號可以全得寶石，反正能得到 50% 的支持，可以過關。

這時加人2 號。

2 號知道，一旦自己的方案不能通過，則自己被丟入海，上麵一種情況發生，3 號可以得到所有寶石。

所以，2 號於是決定放棄 3 號。他隻需要給4，5 號一人一顆寶石，就可以了。因為如果 2 號被丟海裏，那麽就是上麵一個情況，4，5號什麽也得不到。所以為了確保4，5 號讚成，則必須給他們一人一顆，否則他們非常願意看2 號喂鯊魚，嗬嗬。這樣2 號 98 顆，3 號沒有，4，5號一人一顆。

這時加入 1 號。

1 號知道，除非自己給 2 號 99 顆，否則2 號是很樂意看到上一種情況發生的，自己也就被丟海裏了。而一旦給 2 號 99 顆，票數還是不夠。所以，1 號決定放棄 2 號。3 號在上一個情況下，什麽也得不到，所以1 號隻需要給3 號一個寶石，就足夠讓他投自己的票。剩下 4，5 號，因為他們可以在上一種情況下每人得一顆寶石，所以必須給他們其中一個人 2 顆寶石，然後放棄另一個。這樣，1 號的分配方案應該是：1 號 97 顆，2 號0，3 號 1 顆，4 號 2 顆，5 號 0。這樣他起碼可以得到 3 號，4 號的讚成票，到了半數，於是通過。（也可以4 號0，5 號 2 顆，一樣的）。