# Pirates and Gold Coins (again)

A group of P pirates need to split G gold coins. Oldest pirate propose split and if he gets majority of votes (including his own), his proposal is implemented. Otherwise he is killed and next oldest pirate is making his proposal under same rules. Assuming pirates are intelligent, greedy and bloodthirsty, question is:

How many gold coins will oldest pirate get?

Few notes:

• this essentially ask for formula R(G,P) that returns number of coins oldest pirate will get at best and still survive, for arbitrary amount of gold G and number of pirates P. Formula return "0" if he survives but does not get any coin.
• if oldest cannot survive, formula should return negative number showing how many coins he missed - how many more coins he needed to survive. Eg if formula returns "-3" it means that if he had 3 coins in his pockets and offered them in addition to G, he could have survived
• problem may look similar to classic problem like one here , but is significantly different (and harder) due to "majority" rule, while in classic version only half is needed. I also posted similar problem here, but it was closed as "duplicate", which is why I stressed this time difference to classical problem
• this is harder compared to classic not only because formula is needed, but also because even manual solutions for specific (G,P) are more complex
• "majority" means he need V > P/2 votes. For example, with 4 pirates he needs 3 votes (his own and two more)
• pirates priority for optimal result: survive, greedy, bloodthirsty
• "intelligent" means that they can assume all pirates are able to find optimal solution
• "greedy" means that pirates will propose and vote in such way that they maximize their expected gold gain and still survive, so they will vote NO if they expect more gold from next proposal
• "bloodthirsty" means pirates will also vote NO if they expect same gold from next proposal
• to simplify formula, we can ignore special cases with low numbers. So assume P≥5 and G>5

Some hints (semi spoilers on formulas):

- unlike classical problem, pirates here will have to offer more than 1 gold to others
- there is important mechanism ( key for optimal solution, and not present in classic problem ) which allows offers to individual pirates never to go above 2g, and even at one point to drop to 1g. That point "a" marks start for second "region"
- consider case with 5 gold and 9 pirates, it is good example for above mechanism
- pirates are "greedy and intelligent", so when faced with situation where they 'maybe' get some gold they will consider highest expected gain. Eg if next pirate will offer them 3g with chance 1/2, they consider that as 1.5g expected value, and will reject this offer unless it gives them more (2g)
- at one point P pirates can not survive until enough of them are passed for one to survive again, similar to classic problem but again with different formula. That point "b" is start of third "region"
- if we ignore special cases with low numbers, there are three "regions" where solution differs based on P, so solution is basically three different formulas, eg R1(G,P=5..a), R2(G,P=a..b), R3(G,P=b..)
- individual formulas for each region are not too complex ( but are more complex than for classic version, which also does not have middle region)

More direct hints ( spoilers, proposals for up to 7 pirates ):

- even while rules should be clear from question, these examples explicitly show how "expected value" is implemented in solving
- if R denote "remaining gold" that pirate propose to himself, R=G- sum of whatever he offered to other pirates, and if initial G is large enough, then proposals for first 7 pirates are:
#1: G ; R=G in this case, #1 gets all
#2: G X ; X= #2 dies no matter what (#1=bloodthirsty)
#3: 0 0 G ; #2 must vote YES, or he dies next
#4: 1 1 0 R ; R=G-2 here, #1/#2 will vote YES since 1g>0g
#5: 0 2 1 0 R ; 2g is offered EITHER to #1 or #2, so they "expect" 1/2x2g= 1g !
#6: 0 2 2 1 0 R ; #123 all "expect" 1g if #5 offer, so #6 can offer 2g to ANY two of them
#7: 0 0 2 2 1 0 R ; #123 expect 2/3x2g=1.3g, #4 ex 1g, so ANY will take 2g

Some verification values, for people that avoid hints:

R(5g,9p)=0 ... result for hint example
R(6g,10p)=1g, R(10g,15p)=3g, R(20g,14p)=7g, R(11g,40p)=-7g

• In the face of mixed strategies, what does a pirate consider an "optimal" result? Commented Jul 27 at 3:26
• Not sure what "mixed strategies" would refer to, but pirate consider optimal result when he satisfy in order: survive, greedy, bloodthirsty
– lost
Commented Jul 27 at 7:53
• It seems to me that it should not be ambiguous, but I will modify question to make it more clear
– lost
Commented Jul 27 at 18:21
• it IS different, and if you read my question here you should have seen that it is clearly explained several times in question why exactly it is different. Not only does it ask for formula, but problem itself is harder due to "majority" condition.
– lost
Commented Jul 28 at 9:02
• Should we start a community wiki for some simple cases so that we're all on the same page regarding the rules? Commented Jul 29 at 9:59

This is a partial answer to get the ball rolling. I will only focus on an odd amount $$N$$ of gold coins ($$\geq 5$$). Also, as is probably intended, I will assume that the oldest pirates will choose uniformly at random between different optimal proposals and that each pirate will vote for a proposal if she stands to gain more gold from it than the expected value she would face if the current proposal is rejected.

With only up to six pirates, everything is pretty much a special case, which is not too hard to analyse by hand:

• A single pirate takes all gold coins to herself.
• Hence, the second pirate cannot buy the vote of the youngest pirate, so her offer will always be rejected.
• The third pirate will therefore always secure the vote of the second, and can win with the proposal $$(0,0,N)$$.
• The fourth pirate needs at least two additional votes. As $$N> 0$$, the cheapest way to obtain these is by the proposal $$(1,1,0,N-2)$$.
• Finally, the fifth pirate need two other votes as well. Since $$N>2$$, there are two cheapest proposals, namely $$(2,0,1,0,N-3)$$ and $$(0,2,1,0,N-3)$$.

I now claim that the proposals for $$6\leq P\leq N+1$$ pirates will all be according to the following pattern:

• If $$6\leq P \leq N+1$$ is even, the oldest will give two coins to $$\frac{P-2}{2}$$ of the pirates from rank 1 up to $$P-3$$, one coin to pirate $$P-2$$, nothing to $$P-1$$ and the remaining $$N+1-P$$ to herself.
• If $$P$$ (in the same interval) is odd, the oldest will give two coins to $$\frac{P-3}{2}$$ of the pirates from rank 1 to $$P-3$$, one to $$P-2$$, nothing to $$P-1$$ and the remaining $$N+2-P$$ to herself.

This can be proved by induction on $$P$$: For starters, consider $$P=6$$. The oldest pirate needs three additional votes. By our reasoning above, the youngest three each need $$2$$ gold to secure a vote, the next one needs 1 and the penultimate needs $$N-2$$. As $$N\geq 5$$ throughout, the cheapest proposals all follow our pattern above.

Now, for the inductive step, assume first that $$8\leq P \leq N+1$$ is even (odd will be similar) and that the pattern holds for $$P-1$$ pirates. As such, the first $$P-4$$ pirates will have an EV of $$\frac{2\cdot \frac{P-4}{2}}{P-4}=1$$ coins if the current offer is to be rejected. Therefore, the vote of each pirate up to $$P-3$$ (as $$P-3$$ would also be paid 1 gold) costs 2 gold. Since $$P-2$$ would get nothing, their vote costs only 1. And, since the next oldest would pay herself $$N+2-(P-1)=N+3-P\geq 2$$, her vote would cost at least 3 gold $$(*)$$. As such, the cheapest proposals all follow the pattern described above. (The proof for odd $$P$$ is completely analogous.)

Note that the assumption $$P\leq N+1$$ crucially enters in $$(*)$$! For already $$P=N+2$$ pirates, the second oldest pirate would get nothing from her own proposal, which makes her vote a cheaper alternative. Thus, at some point not long after, due to the cheaper older pirates, the EV for the younger ones starts to drop below 1 gold. (I have not yet analysed how exactly this transition plays out, but it should roughly last from $$P\sim N$$ to $$P\sim 2N$$ pirates (at which point the gold finally runs out). I'll update this answer once I figure it out.)

Okay, it seems this is not so difficult after all, if we yet increase the amount of gold to $$N\geq 7$$ odd: The next two rounds (with $$N+2$$ and $$N+3$$ pirates) are somewhat special, but then we have another straightforward pattern that lasts up until $$2N+1$$ pirates.

What happens for $$P=N+2$$ pirates? Recall that the next offer in line grants two coins to $$\frac{N-1}{2}$$ pirates of ranks from 1 to $$N-2$$, one to pirate $$N-1$$ and nothing to $$N$$ and $$N+1$$. As such, the oldest pirate (who needs $$\frac{N+3}{2}$$ votes) can now buy the next two oldest for one coin each and $$\frac{N-3}{2}$$ of the youngest $$N-1$$ pirates for two coins each. This is her cheapest options, which leaves $$N-2-2\cdot\frac{N-3}{2}=1$$ coin to herself.

Note, that the EV of these now gives less than one coin to the $$N-1$$ youngest pirates, so that their votes have now become significantly cheaper! As such, for $$P=N+3$$ pirates, the oldest one can simply buy $$\frac{N+3}{2}$$ of these possible $$N-1$$ votes (note that $$\frac{N+3}{2}< N-1$$, as $$N\geq 7$$) for only one coin each, to leave $$\frac{N-3}{2}$$ coins for herself. This is the cheapest option, since the other three voters could only be satisfied with at least two coins each.

At this point, the EV of everyone but (possibly) the oldest pirate is less than 1 gold coin (which is not true for $$N=5$$!). As such, the following pattern will emerge from this point on:

• For $$N+3\leq P \leq 2N$$, the oldest pirate will give one coin to $$\left \lfloor \frac{P}{2} \right \rfloor$$ of the pirates up to rank $$P-2$$ and the rest to herself.

(This is an easy induction, noting that the EV stays below 1 for each proposal.)

At the point $$P=2N$$, the remainder will be nothing, hence, for $$P=2N+1$$ pirates, the oldest pirate will instead distribute the coins among all pirates up to $$P-1$$ (as opposed to $$P-2$$) and also get nothing for herself.

From that moment on, the money runs out so that the next pirate in line will not be able to secure enough votes for herself (and thus walk the plank). At this point, the behaviour will follow the original variant, with essentially the same reasoning: The only pirates to survive will have rank $$P=2N+1+2^K$$ for some $$K\geq 1$$ and they will propose to give one coin to $$N$$ of the pirates from ranks 1 up to $$2N+1+2^{K-1}$$ (with the single exception of $$2N+3$$ pirates, where the coins are distributed only among the $$2N+1$$ youngest).

What remains to complete the puzzle is, of course, to expand the analysis to an even number of coins (which should not be difficult) and to handle the special cases $$N=1,3,5$$. For the last one, note that the strict inequality $$\frac{N+3}{2}< N-1$$ fails, which makes the case for 9 pirates special as well. The analysis of these special cases is not difficult to do by hand, so I won't give any more details on them.

I would be interested if anyone can come up with a "cleaner" solution (perhaps one that does not get as hung up on parity issues) and gives a more unified approach. Nonetheless, this was a cute puzzle and I enjoyed solving it a lot!

• checking this out, but I sure wish you used G for gold coins ;p
– lost
Commented Jul 29 at 11:29
• Nice work, that is correct solution for "first region", or R1(G,P)= G-P+oddP?2:1
– lost
Commented Jul 29 at 11:49
• Your solution for "second region" is also correct, R2(G,P:a..2G)= G-[P/2] ( where boundary "a" differs by 1 for even G )
– lost
Commented Jul 29 at 12:31
• also, you reasoning for 3rd region (P>2G) is valid, but it lacks formula for R3(G,P). Those are either negative numbers or zero for 2^k cases, but formula would return how much gold pirate P was "missing"
– lost
Commented Jul 29 at 12:34

While this was correctly answered by Tim Seifert above, a few cases were not covered so I will post my solution for completeness's sake. I will not go into details on how I got to solution, since one way was explained in Tim's answer, but I will post my resulting formula(s).

Solution for R(G,P), where:

• R: number of remaining coins that oldest pirate expects to gain (or, if negative, miss in order to survive)
• G: initial number of gold coins that is being split
• P: number of pirates that are splitting gold, where Pth pirate is oldest and propose first

Solution has four regions with different formulas, based on P:

• R0, P=[1,5): special cases for low number of pirates, P<5
• R1, P=[5,a): first "normal" region where P offers 2g, 1g or 0g
• R2, P=[a,b): second region where P offers 1g or 0g
• R3, P=[b,∞): final region where P offers 1g or 0g, and mostly expect negative

Formulas for region boundaries, a(G) and b(G):

a = G + odd(G)? 3:2
b = 2 * G

where odd(G)?3:2 means 3 if G is odd, 2 if even

Solution formulas R(G,P) for regions asked in question, using integer divisions and Log2:

R1(G,P) = G - P + odd(P)? 2:1
R2(G,P) = G - P/ 2
R3(G,P) = [ P-b - 2^( 1+Log2[P-b] ) ]/2

Those same formulas using Floor[] function instead of integer math :

R1(G,P) = G - P + odd(P)? 2:1
R2(G,P) = G - Floor[P/2]
R3(G,P) = Floor[ ( 1 + P-b - 2^( 1+Floor[Log2(P-b)] ) )/2]

note "plus one" in R3=Floor[1+...] , because -5/2=-2, but Floor(-5/2.0)=-3

Solution for initial region R0 and special cases (not asked in question):

R0(G,P) = P switch { 2 => -1, 4 => G - 2, _=> G }
"low pirates" special cases: R0(G,1)=G, R0(G,2)=-1, R0(G,3)=G, R0(G,4)=G-2

if (G,P) in { (3,5), (4, 7), (5, 9) } => R=0
if (G,P) in { (4,6) } => R=-1
"low gold" special cases

for P == a-1 => R=1
special case that differ from R1 for odd G, e.g. R1(7g,9p)=0g but correct is 1g

Combined R(G,P) formula does, in order:

• calculate boundaries a and b
• if P<5 return R0(G,P)
• if special cases return its value
• if P<a return R1(G,P)
• if P≤b return R2(G,P)
• else return R3(G,P)