A Game of Pirates

[Yoruichi-san]

It seems the harmonic function that represents my activity on BD has finally crossed the x-axis once again...;P I recently came across an extension to an old favorite that I'd like to share. The original variant has been posted here several times probably but for those who don't know it, here is a recap:

Season 1 Recap:

There are 5 pirates that must split 100 gold coins among themselves. They do so following the following protocol:

1. The captain presents his proposal on how to distribute the coins.

2. The living pirates, including the captain, take a vote on whether to pass or reject the proposal. In case of a tie, the captain has the breaking vote.

3. If the proposal passes, the coins are divided according to it. If it is rejected, the captain walks the plank and the first mate becomes captain, the second mate (if they are called that?) becomes first mate, the third mate becomes second, etc, and return to step 1.

Assume the pirates are all perfectly rational, do not trust each other, and prioritize in the following order:

1. They want to survive.

2. They want to maximize their personal loot.

3. They want to see others walk the plank.

What is the captain's proposal?

Barring the cliffhanger ending, the logical next extension, then...

Season 2 recap:

Same as above but with n pirates, where n<100.

And finally, the new extension...

Season 3 spoilers:

What if n>100?

[Yoruichi-san]

Correction: for parts 2 and 3, the cutoff should be n<200 and n>200, respectively. I was in too much of a hurry typing things up, sorry.

[bonanova]

Y-San, I researched the first version of this puzzle.

It's challenging, even after reading the correct strategy.

I'm very interested to see what is suggested for the current version.

[m00li]

if we start backwards and think of what happens when only two pirates are left, and then extrapolate, its clear that, the captain should handover 1 coin each to the existing 2nd, 4th,6th,... mates.

In case of 5 pirates the captain keeps 98 and gives 1 each to 2nd and 4th mate.
for n <= 202, he retains 100-[(n-1)/2] where [3.5] = 3
for n>202, the captains keep dying till n reaches 202

[plasmid]

Suppose there are 500 pirates. You propose that all pirates will die until pirate #202 is reached.

If pirates #203 to #500 all decide they would rather live than die, and agree to take nothing while distributing coins to pirates up to #200, that would seem to fulfill their logical criteria and not lead to their deaths.

On the other hand, if pirate #499 makes a convincing argument that he would save pirates 203-499 while letting them all see #500 walk the plank...

Edited May 24, 2014 by plasmid

[m00li]

Suppose there are 500 pirates. You propose that all pirates will die until pirate #202 is reached.

If pirates #203 to #500 all decide they would rather live than die, and agree to take nothing while distributing coins to pirates up to #200, that would seem to fulfill their logical criteria and not lead to their deaths.

On the other hand, if pirate #499 makes a convincing argument that he would save pirates 203-499 while letting them all see #500 walk the plank...

No plasmid. What you are stating will work only if condition 3 is relaxed

[plasmid]

Condition 1 overrides condition 3. The pirates would want to live if possible, so if enough of them cooperate then they should be able to override the initial 202 pirates who want to see them walk the plank.

Pirates 203-500 will, at all costs, live if it's at all possible based on condition 1. They know if they simply toss the captain overboard until they reach 202, then they will all die, so among the options of

A) Pirates 202-500 vote for pirate 500's plan to give a gold piece to each even pirate from 2 to 200

B) Pirates 202-500 become shark bait

they will choose A.

There might be some other option C that I haven't fully worked out that involves some of them getting tossed overboard, but the point is they would not go along with choice B if they know it would lead to their death and they have any alternative.

[m00li]

There is no information given in the question on consensus building. If I understand your assumption correctly, if 500 (captain) proposes a distribution in which no. 499 to 201 don't get anything, they will still agree to it. This implies that they fear, that killing no.500, will start an avalanche of killings. Why?

Lets see this in more detail.

I am assuming that it is established that if there are 202 pirates. No 202, will distribute 1 coin to no. 200, 198,.....,6,4,2, and they will all live.

Now, if there are 203 pirates(p=203). Suppose 203 again proposes 200,198,196,...,4,2 to get 1 coin each. No one will agree, because they know they can make him walk the plank, and still get the same distribution. So, no. 203 has to propose a distribution among 202,201,199,197,195,...5.3.1 but he can pacify at most 100 and thus can never get the majority. So no matter what, in this scenario, no. 203 always dies.

Next, assume there are 204 pirates. No matter what 204 proposes, no. 202 to 1 will have at most 100 consents (as they know, that none of them from 1-202 can die). If 203 doesnt agree, he dies next, so 204 will get 101 votes and including his own, he can survive. So, if there are 204 pirates they all live but 201,202,203,204 do not get anything.

p=205: captain can never survive as the remaining 204 know that, when 205 dies, they will survive. (this is exactly like p=203 in the sense that, the captain dies no matter what)

p=206 to 207: captain proposes 1 coin distribution to 2,4,6,8,...,200 and gets 100 votes. no. 201-204 will never agree. so 104 dissenters. hence the captain dies in p=206-207

p=208: if captain dies, so do 207 to 205, so 205-208 will agree to what 208 proposes (distribute 1 coin to 2,4,6,..,200) and there will be 104 votes. so no. 208 survives

p=209 to 215: they can propose to distribute to 1,3,5,7..,199 but will have at least 108 dissenters, so the captains will always die

p=216: proposes to distribute 1 coin each to 2,4,6,8,...200 and survives

Hence, the final solution:

(1) n<=200:

n keeps 100 - [(n-1)/2] coins for himself and gives 1 coin each to no's n-2,n-4,n-6,...

(2) for n>200

(2.1) Let n = 200 + 2^k (k=1,3,5,7...) i.e. n=202,208,232,...

captain proposes 1 coin each for 200,198,196,..,6,4,2 and there are exactly 100 + 2^(k-1) dissentors so the proposal is accepted

(2.2) for n=200 + 2^k (k=0,2,4,6,8..) i.e. n=204,216,264,..

captain proposes 1 coin each for 199,197,195,..,5,3,1 and there are exactly 100 + 2^(k-1) dissentors so the proposal is accepted

(2.3) for n = 200 + m (m is not a power of 2 and m>2)

captain dies no matter what he proposes, next captain dies no matter what, and so on, till n reaches (2.1) or (2.2) above and follows that case respectively.

[Yoruichi-san]

There is no information given in the question on consensus building. If I understand your assumption correctly, if 500 (captain) proposes a distribution in which no. 499 to 201 don't get anything, they will still agree to it. This implies that they fear, that killing no.500, will start an avalanche of killings. Why?

Lets see this in more detail.

I am assuming that it is established that if there are 202 pirates. No 202, will distribute 1 coin to no. 200, 198,.....,6,4,2, and they will all live.

Now, if there are 203 pirates(p=203). Suppose 203 again proposes 200,198,196,...,4,2 to get 1 coin each. No one will agree, because they know they can make him walk the plank, and still get the same distribution. So, no. 203 has to propose a distribution among 202,201,199,197,195,...5.3.1 but he can pacify at most 100 and thus can never get the majority. So no matter what, in this scenario, no. 203 always dies.

Next, assume there are 204 pirates. No matter what 204 proposes, no. 202 to 1 will have at most 100 consents (as they know, that none of them from 1-202 can die). If 203 doesnt agree, he dies next, so 204 will get 101 votes and including his own, he can survive. So, if there are 204 pirates they all live but 201,202,203,204 do not get anything.

p=205: captain can never survive as the remaining 204 know that, when 205 dies, they will survive. (this is exactly like p=203 in the sense that, the captain dies no matter what)

p=206 to 207: captain proposes 1 coin distribution to 2,4,6,8,...,200 and gets 100 votes. no. 201-204 will never agree. so 104 dissenters. hence the captain dies in p=206-207

p=208: if captain dies, so do 207 to 205, so 205-208 will agree to what 208 proposes (distribute 1 coin to 2,4,6,..,200) and there will be 104 votes. so no. 208 survives

p=209 to 215: they can propose to distribute to 1,3,5,7..,199 but will have at least 108 dissenters, so the captains will always die

p=216: proposes to distribute 1 coin each to 2,4,6,8,...200 and survives

Hence, the final solution:

(1) n<=200:

n keeps 100 - [(n-1)/2] coins for himself and gives 1 coin each to no's n-2,n-4,n-6,...

(2) for n>200

(2.1) Let n = 200 + 2^k (k=1,3,5,7...) i.e. n=202,208,232,...

captain proposes 1 coin each for 200,198,196,..,6,4,2 and there are exactly 100 + 2^(k-1) dissentors so the proposal is accepted

(2.2) for n=200 + 2^k (k=0,2,4,6,8..) i.e. n=204,216,264,..

captain proposes 1 coin each for 199,197,195,..,5,3,1 and there are exactly 100 + 2^(k-1) dissentors so the proposal is accepted

(2.3) for n = 200 + m (m is not a power of 2 and m>2)

captain dies no matter what he proposes, next captain dies no matter what, and so on, till n reaches (2.1) or (2.2) above and follows that case respectively.

Correct on your analysis of parts 1 and 2, but for part 3...one thing to consider...

Even/odd parity

.

[Yoruichi-san]

There is no information given in the question on consensus building. If I understand your assumption correctly, if 500 (captain) proposes a distribution in which no. 499 to 201 don't get anything, they will still agree to it. This implies that they fear, that killing no.500, will start an avalanche of killings. Why?

Lets see this in more detail.

I am assuming that it is established that if there are 202 pirates. No 202, will distribute 1 coin to no. 200, 198,.....,6,4,2, and they will all live.

Now, if there are 203 pirates(p=203). Suppose 203 again proposes 200,198,196,...,4,2 to get 1 coin each. No one will agree, because they know they can make him walk the plank, and still get the same distribution. So, no. 203 has to propose a distribution among 202,201,199,197,195,...5.3.1 but he can pacify at most 100 and thus can never get the majority. So no matter what, in this scenario, no. 203 always dies.

Next, assume there are 204 pirates. No matter what 204 proposes, no. 202 to 1 will have at most 100 consents (as they know, that none of them from 1-202 can die). If 203 doesnt agree, he dies next, so 204 will get 101 votes and including his own, he can survive. So, if there are 204 pirates they all live but 201,202,203,204 do not get anything.

p=205: captain can never survive as the remaining 204 know that, when 205 dies, they will survive. (this is exactly like p=203 in the sense that, the captain dies no matter what)

p=206 to 207: captain proposes 1 coin distribution to 2,4,6,8,...,200 and gets 100 votes. no. 201-204 will never agree. so 104 dissenters. hence the captain dies in p=206-207

p=208: if captain dies, so do 207 to 205, so 205-208 will agree to what 208 proposes (distribute 1 coin to 2,4,6,..,200) and there will be 104 votes. so no. 208 survives

p=209 to 215: they can propose to distribute to 1,3,5,7..,199 but will have at least 108 dissenters, so the captains will always die

p=216: proposes to distribute 1 coin each to 2,4,6,8,...200 and survives

Hence, the final solution:

(1) n<=200:

n keeps 100 - [(n-1)/2] coins for himself and gives 1 coin each to no's n-2,n-4,n-6,...

(2) for n>200

(2.1) Let n = 200 + 2^k (k=1,3,5,7...) i.e. n=202,208,232,...

captain proposes 1 coin each for 200,198,196,..,6,4,2 and there are exactly 100 + 2^(k-1) dissentors so the proposal is accepted

(2.2) for n=200 + 2^k (k=0,2,4,6,8..) i.e. n=204,216,264,..

captain proposes 1 coin each for 199,197,195,..,5,3,1 and there are exactly 100 + 2^(k-1) dissentors so the proposal is accepted

(2.3) for n = 200 + m (m is not a power of 2 and m>2)

captain dies no matter what he proposes, next captain dies no matter what, and so on, till n reaches (2.1) or (2.2) above and follows that case respectively.

Correct on your analysis of parts 1 and 2, but for part 3...one thing to consider...

Even/odd parity

.

Lol, nvm, I was reading the wrong post...(again with the whole rushing things thing . Anyways, great job .

[k-man]

If captains proposal must specify exactly who gets what then I agree with the previous post (by m00li) with a small correction. If there are 204 pirates, then the captain will not get the votes if he distributes the coins to even numbered pirates (2,4,6,...200). Those pirates have no reason to vote for this distribution as if they vote NO they will see 204 and 203 walk the plank and get the same deal again from 202. So, to survive, 204 has to give the coins to odd numbered pirates except 203. There are 101 odd numbered pirates and this captain has a choice of which 100 of 101 will get coins.

This got me thinking and I possibly came up with a way to save captain 203.

Since the OP doesn't require the proposal to specify exactly who gets the coins, I think this proposal by 203 should save his neck:

Captain 203 proposes that all 100 odd numbered pirates (1-201) and 202 participate in a random drawing. 100 of them will get 1 coin and one of them will get nothing. They all have 100/101 chance of getting a coin and if they reject this proposal they all get nothing. This should be enough for them to vote "yes", which gives this captain the necessary 102 votes (including his own).

Obviously, this strategy can be used for other captains with higher numbers too.

[Yoruichi-san]

Hmm...well technically, I believe the term "distribute" implies a discrete division, not a probabilistic one, but I do like that variation on the game. That seems like a really fascinating extension...I'll see if I can work on it (or anyone else who wants to )

Edited May 29, 2014 by Yoruichi-san