$500$ pirates have just stolen a treasure of $100$ gold pieces, and they decide to share it in the following way: starting from the $500$th pirate, and going on with the $499$th, $498$th, and so on, each pirate proposes a way to share the gold (for instance, he says: "the pirate $1$ will receive $13$ gold pieces, the $2$nd $17$ gold pieces, ..."). The proposal is voted, and if it passes with at least $50\%$ votes (including the pirate that is making the proposal) it is accepted and the gold is shared. If the proposal is not accepted, the pirate is shot and the next pirate is going to make a new proposal, and so on. How many pirates will survive?
Note that each pirate only trusts himself, and their main purposes are, in order:
$\mathbf{\alpha}$) survive,
$\mathbf{\beta}$) gain as much gold as possible,
$\mathbf{\gamma}$) kill the highest number of other pirates.
Have fun! :-)
Update (17/02/2008): Solution posted! (show solution)
Suppose that only 2 the pirates remain alive: in this case, the 2nd pirate will simply bring home all gold (votes: 1vs1). What if they are 3? The 3rd pirate has no way to bring the pirate 2 on his side (because he would get all gold anyway), but he can get the vote of the pirate number 1 by just giving him one gold piece, so he proposes to share the gold as 1/0/99 (votes: 2vs1). If they are 4? the pirate number 4 need one vote, and he can get one by giving one gold piece to the 2 pirate, that would otherwise get no gold at all, so he says: 0/1/0/99 (votes: 2vs2).
Case with 5 pirates: 1/0/1/0/98 (votes: 3vs2)
Case with 6 pirates: 0/1/0/1/0/98 (votes: 3vs3)
Case with 7 pirates: 1/0/1/0/1/0/97 (votes: 4vs3)
Case with 8 pirates: 0/1/0/1/0/1/0/97 (votes: 4vs4)
....
Case with 201 pirates: the 201th can save himself giving 1 gold piece to all odd pirates 1,3,5,...,199 (votes: 101vs100)
Case with 202 pirates: the 202th can save himself giving 1 gold piece to all even pirates 2,4,6,...,200 (votes: 101vs101)
Note that the pirates from 1 to 200 are "semplified" since now on, because with 100 gold pieces each pirate will be able to buy 100 votes, while the other 100 will vote against him.
203 pirates: the 203th can only buy 100 other votes, and they are not enough.
204 pirates: the 204th can buy 100 votes, but he will also get a vote from the 203th, so he will survive.
205 pirates: the 205th pirate will die.
206 pirates: the 206th pirate will die.
207 pirates: the 207th pirate will die.
208 pirates: he can buy 100 votes as usual, and the 205th, 206th, 207th pirates will accept any proposal (because they would die if the proposal is rejected). So he survives.
209 pirates: the 209th pirate will die.
210 pirates: the 210th pirate will die.
....
215 pirates: the 215th pirate will die.
216 pirates: he can buy 100 votes as usual, and the 209th, 210th, ..., 215th pirates will accept any proposal (because they would die if the proposal is rejected). So he survives.
...
Now you've probably guessed that the pirates above the 200th that can make a proposal that will be accepted are the (200+x)ths, where x is a power of 2. So, since the biggest power of 2 less then 300 is 256, the answer to the problem is 456, ie the pirates 500, 499, ..., 457 will all die, and the 456 that will make a proposal that will be accepted.
No comments:
Post a Comment