seanieg89
Well-Known Member
- Joined
- Aug 8, 2006
- Messages
- 2,662
- Gender
- Male
- HSC
- 2007
Okay, here goes my attempt to explain it.
For small numbers of pirates, there is a unique optimal plan for the pirate king to propose (optimal in the sense that it maximises the gold he gets and ensures his survival). I present the first few here for you to get the idea:
(100,0), (99,0,1), (99,0,1,0), (98,0,1,0,1), (98,0,1,0,1,0) etc.
To show these plans are optimal, it suffices to compare the outcome of each of the k pirates in a given plan to his outcome if the plan is rejected and the optimal (k-1)-pirate plan is proposed and accepted. For a k pirate plan to be accepted, the king pirate must merely ensure that he offers enough of the pirates more gold than they would receive in the optimal (k-1)-pirate plan.
This is certainly possible (and unique) for small numbers of pirates. Things get a little interesting when we reach the 200 mark. Now the king pirate can no longer afford to hang on to any gold for himself, his survival is at stake. As he posesses a vote himself, he can still survive when there are 202 pirates via the plan
(0,0,1,0,1,...,1,0).
Moreover, this is the unique agreeable plan when there are 202 pirates.
So now we know that the bottom 202 pirates are safe no matter what...ie their decisions on the plans when there are > 202 pirates are motivated purely by money and their thirst for blood.
When there are 203 pirates, the king pirate can only satisfy 100 pirates with gold pieces, and his own vote makes 101, not enough for survival! So if there are 203 pirates, the pirate king is doomed no matter what he proposes. (*)
HOWEVER, this does not mean that 202 is the maximum number of pirates for which an agreeable plan is possible.
If there are 204 pirates for instance, the king can propose the plan (0,0,0,0,0,1,0,1,0,...,0,1). As before, the 100 pirates receiving gold are happy, because they do not receive gold in the unique plan that would be agreed upon if the top two pirates are killed. Finally, the king himself and his #2 are happy with this plan for the reason of survival! #2 will agree to absolutely any plan the king proposes as he knows that if it gets to 203 pirates with him as king, he is doomed (from *)!
We can continue this process upwards in an inductive process. The idea is to show that when there are >200 pirates, there is an agreeable plan if and only if there are 200+2^k pirates for some non-negative integer k. (Which directly gives us 456 as the first # of pirates for which the king can avoid being killed.)
The process is slightly complicated by the fact that at this point we lose uniqueness of an optimal plan, eg (0,0,0,1,0,0,0,1,0,...,0,1) would also satisfy 204 pirates, however the essential idea is simple: We need to add more and more pirates at the top each time to vote with the king on the basis of survival in order to balance the increasing number of pirates who know they are safe and cannot be satisfied with gold. A little tired now so I will leave this for now and come back to it tomorrow. Hopefully what I have written makes some sense.
For small numbers of pirates, there is a unique optimal plan for the pirate king to propose (optimal in the sense that it maximises the gold he gets and ensures his survival). I present the first few here for you to get the idea:
(100,0), (99,0,1), (99,0,1,0), (98,0,1,0,1), (98,0,1,0,1,0) etc.
To show these plans are optimal, it suffices to compare the outcome of each of the k pirates in a given plan to his outcome if the plan is rejected and the optimal (k-1)-pirate plan is proposed and accepted. For a k pirate plan to be accepted, the king pirate must merely ensure that he offers enough of the pirates more gold than they would receive in the optimal (k-1)-pirate plan.
This is certainly possible (and unique) for small numbers of pirates. Things get a little interesting when we reach the 200 mark. Now the king pirate can no longer afford to hang on to any gold for himself, his survival is at stake. As he posesses a vote himself, he can still survive when there are 202 pirates via the plan
(0,0,1,0,1,...,1,0).
Moreover, this is the unique agreeable plan when there are 202 pirates.
So now we know that the bottom 202 pirates are safe no matter what...ie their decisions on the plans when there are > 202 pirates are motivated purely by money and their thirst for blood.
When there are 203 pirates, the king pirate can only satisfy 100 pirates with gold pieces, and his own vote makes 101, not enough for survival! So if there are 203 pirates, the pirate king is doomed no matter what he proposes. (*)
HOWEVER, this does not mean that 202 is the maximum number of pirates for which an agreeable plan is possible.
If there are 204 pirates for instance, the king can propose the plan (0,0,0,0,0,1,0,1,0,...,0,1). As before, the 100 pirates receiving gold are happy, because they do not receive gold in the unique plan that would be agreed upon if the top two pirates are killed. Finally, the king himself and his #2 are happy with this plan for the reason of survival! #2 will agree to absolutely any plan the king proposes as he knows that if it gets to 203 pirates with him as king, he is doomed (from *)!
We can continue this process upwards in an inductive process. The idea is to show that when there are >200 pirates, there is an agreeable plan if and only if there are 200+2^k pirates for some non-negative integer k. (Which directly gives us 456 as the first # of pirates for which the king can avoid being killed.)
The process is slightly complicated by the fact that at this point we lose uniqueness of an optimal plan, eg (0,0,0,1,0,0,0,1,0,...,0,1) would also satisfy 204 pirates, however the essential idea is simple: We need to add more and more pirates at the top each time to vote with the king on the basis of survival in order to balance the increasing number of pirates who know they are safe and cannot be satisfied with gold. A little tired now so I will leave this for now and come back to it tomorrow. Hopefully what I have written makes some sense.
