Been super busy, haven't updated in ages! I feel very guilty. Here's a classic interview problem, plus my solution. (my regards to my algorithms lecturer, Aleks Ignjatovic, for the write-up)
Call the five pirates $A,B,C,D,E$. The leftmost pirate in the line goes first.
$E$ can always vote against $D$, resulting in a tie, meaning $E$ gets all the money.
$D$: dead
$E$: 100
There are five pirates who have to split 100 bars of gold. They all line up and proceed as follows:Like many other problems of the sort, it's helpful to start by considering a very small case -- for example, when $n=2$.
- The first pirate in line gets to propose a way to split up the gold (for example: everyone gets 20 bars)
- The pirates, including the one who proposed, vote on whether to accept the proposal. If the proposal is rejected, the prate who made the proposal is killed.
- The next pirate in line then makes his proposal, and the 4 pirates vote again. If the vote is tied (2 vs 2) then the proposing pirate is still killed. Only majority can accept a proposal. The process continues until a proposal is accepted or there is only one pirate left. Assume that every pirate :
- above all wants to live;
- given that he will be alive he wants to get as much gold as possible;
- given maximal possible amount of gold, he wants to see any other pirate killed, just for fun;
- each pirate knows his exact position in line;
- all of the pirates are excellent puzzle solvers.
Call the five pirates $A,B,C,D,E$. The leftmost pirate in the line goes first.
2 Pirates: $D,E$.
$D$ proposes. $D$ votes for himself.$E$ can always vote against $D$, resulting in a tie, meaning $E$ gets all the money.
$D$: dead
$E$: 100
3 Pirates: $C,D,E$.
$C$ proposes. $C$ votes for himself.
$D$ knows that if $C$ dies, then $D$ will also die in the following
round (as in the 2 pirates case). So $D$ will avoid death by voting
for $C$ regardless of $C$'s proposition.
$C$ wins with $2/3$ votes.
$C$: 100
$D$: 0
$E$: 0
$C$ can get 100 bars by killing $B$, and gains nothing if $B$ lives, so $C$ will vote against $B$.
$D$ will get nothing if $B$ dies, and as pirates always want to kill pirates for fun, he will kill $B$ unless $B$ gives him some incentive to vote for $B$'s proposition. So if $B$ gives $D$ 1 bar, $D$ will vote for $B$.
Similarly for $E$ -- so $B$ gives $E$ 1 bar in exchange for $E$'s vote. $B$ wins with 3/4 votes.
$B$: 98
$C$: 0
$D$: 1
$E$: 1
$B$ can get 98 bars by killing $A$, and gains nothing if $A$ lives, so $B$ will vote against $A$.
$C$ will get nothing if $A$ dies, and as pirates always want to kill pirates for fun, he will kill $A$ unless $A$ gives him some incentive to vote for $A$'s proposition. So if $A$ gives $C$ 1 bar, $C$ will vote for $A$.
$D$ will get 1 bar if $A$ dies, and as pirates always want to kill pirates for fun, he will kill $A$ unless $A$ gives him some incentive to vote for $A$'s proposition. So if $A$ gives $C$ 2 bars, $C$ will vote for $A$.
$A$ wins with 3/5 votes.
$A$: 97
$B$: 0
$C$: 1
$D$: 2
$E$: 0
Therefore $A$ should propose that $A$ gets 97 gold bars, $C$ gets 1 gold bar and $D$ gets 2 gold bars.
4 Pirates: $B,C,D,E$.
$B$ proposes. $B$ votes for himself.$C$ can get 100 bars by killing $B$, and gains nothing if $B$ lives, so $C$ will vote against $B$.
$D$ will get nothing if $B$ dies, and as pirates always want to kill pirates for fun, he will kill $B$ unless $B$ gives him some incentive to vote for $B$'s proposition. So if $B$ gives $D$ 1 bar, $D$ will vote for $B$.
Similarly for $E$ -- so $B$ gives $E$ 1 bar in exchange for $E$'s vote. $B$ wins with 3/4 votes.
$B$: 98
$C$: 0
$D$: 1
$E$: 1
5 Pirates: $A,B,C,D,E$.
$A$ proposes. $A$ votes for himself.$B$ can get 98 bars by killing $A$, and gains nothing if $A$ lives, so $B$ will vote against $A$.
$C$ will get nothing if $A$ dies, and as pirates always want to kill pirates for fun, he will kill $A$ unless $A$ gives him some incentive to vote for $A$'s proposition. So if $A$ gives $C$ 1 bar, $C$ will vote for $A$.
$D$ will get 1 bar if $A$ dies, and as pirates always want to kill pirates for fun, he will kill $A$ unless $A$ gives him some incentive to vote for $A$'s proposition. So if $A$ gives $C$ 2 bars, $C$ will vote for $A$.
$A$ wins with 3/5 votes.
$A$: 97
$B$: 0
$C$: 1
$D$: 2
$E$: 0
Therefore $A$ should propose that $A$ gets 97 gold bars, $C$ gets 1 gold bar and $D$ gets 2 gold bars.
General Case
This is a simple recursive procedure -- the $n$th pirate has to bribe just enough other pirates so that he gets enough votes, while also maximising his own money. This can be done by finding those pirates who would get the least amount of gold bars in the case of $n-1$ pirates, then bribe them with one extra gold bar more than they would otherwise have gotten. Here is a $O(n\log n)$ Python implementation, and its output.def best_strategy(n):
if n == 2:
return [-1, 100]
else:
moneys = [100] + best_strategy(n-1)
copy = sorted(zip(moneys, range(n-1)))
next = [100] + [0] * (n-1)
for i in xrange(int((n-1) / 2)):
their_money, person = copy[i]
next[person] = their_money + 1
next[0] -= next[person]
return next
for i in xrange(2, 15):
print i, best_strategy(i)
Output
2 [-1, 100] 3 [100, 0, 0] 4 [99, 0, 1, 0] 5 [97, 0, 1, 2, 0] 6 [97, 0, 1, 2, 0, 0] 7 [96, 0, 1, 2, 0, 1, 0] 8 [96, 0, 1, 2, 0, 1, 0, 0] 9 [95, 0, 1, 2, 0, 1, 0, 1, 0] 10 [95, 0, 1, 2, 0, 1, 0, 1, 0, 0] 11 [94, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0] 12 [94, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 0] 13 [93, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0] 14 [93, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0]
