Wednesday, August 27, 2008

Pirate's gold distribution problem

Q:
n Pirates with unique rank from 1 to n.
m pieces of gold.

Highest pirate gives proposal and all of them vote. Half or more support, ok.
else kill him. do again.

All pirates are willing to kill others. but if there's benifit, they choose
money. and they all know others are the same.

what's the best strategy for the highest pirate to get as more gold as possible?
write a program to exam your result.

If there's no enough gold, some one will be killed. Under what condition,
the highest pirate can suvive? give the mathematical answer. If m=0,
what's your program's output? is it match the mathematical answer? if not,
what's the problem?

A: Let's label the pirates as P_1,P_2,...,P_n, where p_n has highest rank
1. If P_1 need to make proposal, well, he just keep all the gold;
2. for p_2 , he could propose to have all gold, and got vote from himself;
3. for p_3, he could propose to get m-1 gold, while giving the 1 gold to p_1, so he can win two votes
4. for p_4, he could use 1 gold for p_2, and m-1 for himself
5. for p_5, he need 2 votes, 1 gold each to p_3 and p_1, and m-2 for himself
...
6. for p_(2*m+1), he could use all m gold to p_(2*m-1), p_(2*(m-1)-1), ... , p_1, and thus gather m + 1 votes (including himself), and survive
7. for p_(2*m+2), he could use all m gold to p_(2*m), p_(2*(m-1)), ... , p_2, and survive, but he could also get vote from p_(2*m+1) with 1 gold, because otherwise p_(2*m+1) won't get anything if it is up to himself to distribute the gold. Therefore, p_(2*m+2) can randomly distribute m gold to m of the m+1 pirates: p(2*m+1), p_(2*m), p_(2*(m-1)), ... , p_2, and survive.
8. for p_(2*m+3), there is no enough gold to get m+2 votes, so he will be killed anyway
9. for p_(2*m+4), he can get one vote from himself, m vote from randomly picked m from p_(2*m+2), p_(2*m+1), p_(2*m-1), ... , p_1 (who can not get any gold if do not support the propose), and p(2*m+1), p_(2*m), p_(2*(m-1)), ... , p_2, (who won't be sure to get a gold if p_(2*m+2) is going to distribute the gold), and one vote from p_(2*m+3) (otherwise he will be killed), therefore he can get totally m+2 votes and survive.
9. for p_(2*m+5), he needs m+3 votes to survive, but can only get m+1 votes. so he will be killed anyway
10. for p_(2*m+6), he needs m+3 votes, but can only get m+2 votes
11. for p_(2*m+7), he needs m+4 votes, but can only get m+3 votes
12. for p_(2*m+8), he needs m+4 votes, and can get it from himself, p_(2*m+7), p_(2*m+6), p_2*m+5), plus m votes from randomly picked p_(2*m+4), p_(2*m+3), p_(2*m+2),, ... , p_1 (who won't either get anything or be sure to get one gold, if p_(2*m+4) is going to distribute the gold). Therefore he can get totally m+4 votes and survive.
...
13. for p_(2*m + 2^k), k>0, he can survive as he can get vote by m golds, and votes from p_(2*m + 2^(k-1)+1), ..., p_(2*m + 2^k), totally m + 2^(k-1) votes and survive...the m golds will be distributed randomly picked m from p_1 to p_(2*m+2^(k-1))

if m = 0, p_1, p_2, p_4, p_8, ... , p_(2^k) can survive, this is same as concluded above.

No comments: