Best Answer m00li, 24 May 2014 - 11:03 PM

Spoiler for I agree plasmid but not completely.

Go to the full post

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.