Survivor of the pirates
There are 5 pirates on an island. They have a big box of treasure stashed (1000 diamonds) on the island and now they must distribute the treasure amongst themselves. They are extremely greedy pirates and they do not agree for an even split as each one wants to have more treasure. So they play a game - SURVIVOR! The senior most pirate proposes a methodology to split the treasure and everyone votes. If the senior most pirate can get at least 1/2 votes for his porposal, then they split the coins that way. If the senior most pirate cannot get majority for his proposal then, they kill the senior most pirate and start over with the next senior most pirate. The process continues until one proposal by one surviving senior pirate is accepted. So how does this game amongst the pirates proceed? Who gets to keep the stash and how much? What would be an intelligent proposal by "a senior" pirate? Can you then tell how this will work for an 'n' pirate scheme? Assume that the pirates are all very mathematical and logical for the sake of this question.Level: Medium
posted by Karthik Nagaraj at
4:31 PM
5 Comments:
pirate 1 gets 998 diamonds
pirate 4 gets 1 diamond
pirate 5 gets 1 diamond
if there are only 2 pirates lleft...the first one keeps all the stash!
pirate 4 1000
pirate 5 0
if there are 3 pirates,
pirate3 999
pirate4 0
pirate5 1
this is because 3 thinks one step ahead\! he realises that 5 will be left diamond less if he dies and he can be sure tht 5 will vote in faour even if he gets 1 diamond!
if 4 pirates, by same logic two solutions are possible! but the first one is preferred as 4 is more desperate for the diamond. coz if he loses out now he can never get a diamond! check above to see why!
pirate2 999 999
pirate3 0 0
pirate4 1 0
pirate5 0 1
if there are 5 pirates,
pirate1 998
pirate2 0
pirate3 0
pirate4 2
pirate5 1
I havent genrailzed it yet!
Balaji,
In the beginning you say P1 = 998, P4 = 1 and P5 = 1 and at the end you say P1 = 998, P4 = 2, P5 = 1. I don't get it. Which is the correct one? And why is 998, 2, 1 -> shouldn't it be 997, 2, 1 OR 998, 1, 1? Let me know!
Coming to your reasoning, I understand your thought process. The logic for 2 pirates, 3 pirates and 4 pirates is fine. But if your answer to the 5 pirates one is 997,2,1 then its not correct. If it is 998,1,1 then initially it looks to be fine, BUT there is a FLAW. Let me tell you.
If in the 5 pirate scheme you say that
P1=998
P2=0
P3=0
P4=1
P5=1
Then you are giving P4 a choice to tell 'NO', why? Because, lets see how many votes does P1's proposal need now - he needs another 2 votes besides his own vote. The question says at least 1/2 of the votes. So if he needs 2 votes then he better satisfy 2 people - in your case it is P4 and P5. Now lets say P4 says 'NO' for this proposal because he knows that anyway in the next turn when P2 proposes, P4 is bound to get 1. So why bother telling a 'Yes'. So if P4 tells a No, then P2 and P3 are anyway going to tell 'NO', then P1's proposal is failed. They kill P1 and the process continues. Hope you get what I'm trying to tell.
So the idea you have taken is correct but the buying off pattern in not correct for the 5 pirate scheme. Devise a scheme in which the pirates are forced to tell a 'Yes' in that turn itself. That's why the first pirate who starts this wins - if he is logically fit enough to make a wise decision and that assumption is already been told to make. :)
So in your case what would your analysis be for a 'n' pirate game like this? What is the basic funda of this game? Get the right scheme and your general methodology will fall right in place.
assume ages p1 > p2 > p3 > p4 >p5.
That is p5 is the youngest.
Using a backtracking approach,
Suppose only p4 and p5 are there.
p4=1000
p5 = 0
Suppose only p3, p4, p5
p3 = 999
p4 = 0
p5 = 1
Suppose p2, p3,p4,p5
p2 = 999
p3 = 0
p4 = 1
p5 = 0
p4 votes in favor of this as he knows that if the next iteration above happens he will get 0.
Suppose p1,p2,p3,p4,p5
p1=998
p2=0
p3=1
p4=0
p5=1
p3 votes in favor of this becoz in the next round he will get 0. p5 also votes in favor of this as he will get 0 in the next round.
continuing the same anology
for n pirates
p1 takes 1000-(n/2) note: n/2 is rounded off to the next higher integer.
p2 takes 0
p3 takes 1
p4 takes 0
p5 takes 1
p6 takes 0
.....and so on till p(n)
n/2 is not rounded to the next higher integer but to the greatest integer < n/2
Mayura,
I think your solution works. The basic idea here in this puzzle is that the senior most pirate who is given the first chance needs to know how many votes he needs to buy and how cheaply he can get that deal. So in your explanation, you have clearly shown why the proposal made by P1 cannot be rejected and how he can stand to get 998 diamonds. Excellent! Good thinking.
This puzzle is now SOLVED!
Subscribe to Post Comments [Atom]
<< Home