Question:
There are five pirates, ranked from 5 to 1 in descending order. The top pirate has the right to propose how 100 gold coins should be divided among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.)
Answer on the web:
The normal solution is to reduce and recurse.
At 2 pirates, number 2 gets all the gold and votes for himself and stays alive.
At 3 pirates, number 3 gets 99 coins and bribes 1 who will get nothing otherwise with 1 coin.
At 4 pirates,
* If 4 brides 1 with 1 coin then 1 might axe him anyway since he will get 1 coin when there are 3 pirates anyway
* but when there are 3 pirates 2 gets nothing so if 2 is bribed now it will work out.
So At 4 pirates, number 4 gets 99 coins and bribes 2 who will get nothing otherwise with 1 coin.
At 5 pirates,
* When there are 4 pirates 1 and 3 get nothing so bribing them with 1 coin will do
So At 5 pirates, number 5 gets 98 and 1 and 3 get 1 each.
However I believe this to be wrong.. Here is why:
At 5 pirates, What happens when if pirate 4 tries to counter bribe pirates 1 and 3.
My reasoning is simple. If 1 and 3 and smart enough to figure out the the forward case is when there are 4 pirates then isnt 4 also capable of that also? So in short the actions of 4 and 2 should also count into the 5 pirate calculation.
Lets start the reduction again.
At 2 pirates, number 2 gets all the gold and votes for himself and stays alive.
At 3 pirates,
* originally number 3 gets 99 coins and bribes 1 who will get nothing otherwise with 1 coin.
* however number 2 will counter bribe 1 with 2 coins and his reward would be 98.
* 3 needs to now better this also well as the normal case or die,
* additionally 2 can offer upto 100 gold in counter bribes to 1 and then he will win all future deals because it will become the 2 pirate case, which he always wins.
So at 3 pirates, 3 and 1 get 0 coins and 2 gets 100 coins. and maybe 3 gets to live
At 4 pirates things get crazy...
* originally number 4 gets 99 coins and bribes 2.
* but in the counter bribe case 3 knows that he wont get any thing and is likely to die if it reduces to 3 pirates.
* 2 knows that if it becomes 3 or 2 pirates he will always win.
* 2 cant bribe 3 because 3 knows he gets stiffed in the 3 pirate case so bribing 1 is also pointless
* 1 doesn't care because he is getting stiffed in all cases anyway
* 4 can offer 3 1 more gold than he would get in the the 3 pirate case
So at 4 pirates, 4 gets 99 gold and 3 gets 1 gold.
At 5 pirates (still here ... great!)
* originally number 5 gets 98 coins and bribes 3 and 1 with 1 each, however when counter brides exist.....
* 4 could get 99 if he was in control but would be in-control because of 3
* 4 needs 1 vote to live but 5 needs 2
* 3 is getting 1 coin only if 4 is in-charge and doesn't want there to be 3 pirates
* 2 wants to get the number of pirates down to 2 or 3 pirates but 4 and 3 can stop that from happening so he is back to no coins and possibly a short term bribe..
* 5 is basically stuffed like 3 was, but he needs 2 people to vote him or he dies.
* if 5 offers 1,2 or 3 a bribe up to 99 coins then 4 can still better that bride with 100 coins and survive that round but in the future 4 will not give anything to anyone but 3.
* 5 can only bribe 4 or 4s counter brides will undo him.
* at best 5 could only repeat 4's option and hope that 4 doesn't axe him.
So at 5 pirates, 4 gets 99 and 3 gets 1
Yea that was crazy....
It looks like your assuming that all pirates get a right to propose division, but the problem states only the top pirate gets to propose division.
ReplyDeleteYou will need to at least pay 1 gold to achieve majority, because paying nothing will be a definite vote of mutiny. (98)
From a psychology point of view if a person feels an unfair split they WILL vote against even if it does NOT benefit them.
So with all that bribing with 1 gold will maximise profit but the chance of dying will still be extremely high.
Since it is an interview question it is supposed to be a discussion, so perhaps you can discuss the probability that they will still kill him if half don't get close to even share.
Oh I see what your doing, if they do vote it down, your assuming that there is a new top pirate amongst the 4 that will be doing division. Which may or may not be incorrect.
ReplyDeleteAssuming that the "second in command" will think ahead to the next vote when deciding whether the "top" pirate should live or die, is very likely wrong, this is because the last pirate standing will definitely get 100.
Quite plainly if you pay a pirate 0 then the probability that he will feel it is unfair is 100%.