Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2015-10-16 07:28:43

crandles
Member
Registered: 2015-10-16
Posts: 4

100 gold coins 300 pirates

5 pirates is a nice problem,
http://www.mathsisfun.com/puzzles/5-pirates.html

but as you increase the number of pirates, the patterns get intricate and worth seeing.

First a couple of additional rules, because otherwise the solutions are not unique:
Only whole number of gold coin solutions can be proposed and they don't trust any other agreement.
If a pirate can bribe two or more different pirates for the same number of gold coins and doesn't need to bribe them all then he prefers to bribe the highest ranking pirate.

My answer


Let me know if you do not agree.

Last edited by crandles (2015-10-16 08:45:05)

Offline

#2 2015-12-15 05:58:49

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 100 gold coins 300 pirates

I solved this problem, but I'm afraid I don't even understand your answer. The solution I arrived at is that, where the highest ranking (oldest) pirate is #1 and the lowest #300, every pirate from #1 to #98 will be killed in a futile attempt to satisfy the masses with overstretched coin (they offer one coin to every pirate above them up to #100, and then every odd number, if they are odd, or even number, if they are even, as per your rule of paying the highest-ranking). They get out-voted by the masses of lower-ranked pirates who are trying to jump the queue. But #99 is the first pirate who can pay a majority (101 out of 202 including himself), but he has to give away every single coin to #100 and all the odd numbers up to #297 so they will spare his life.

Edit: I think I messed up the above analysis. I forgot to take into account that the pirates prefer to stay alive, and those that would be killed, beginning with #98, would therefore vote for those above them. I am redoing the analysis now, and will also assume that the pirates would prefer to throw a higher-ranking pirate overboard, if a lower-ranking one will offer him the same deal.

Last edited by Relentless (2015-12-15 17:35:35)

Offline

#3 2015-12-15 20:26:18

Relentless
Member
Registered: 2015-12-15
Posts: 624

Re: 100 gold coins 300 pirates

Update: I was off with my first post, except for the actions of the lowest 202 pirates were they to remain. Your solution is absolutely correct to the smallest detail, and my numbering scheme was just the reverse of yours. The very first pirate, incidentally, loses his head with 136 votes out of 300 (the 35 below him attempting to save themselves by supporting him).

Just to make the reasoning for this explicit, I will continue numbering the oldest first and explain the entire process.

Down to just 299 and 300, 299 would take everything.
298 will offer 300 1 coin and 299 nothing.
297 will offer 299 1 coin and the others nothing.
296 will offer 298 and 300 1 coin.
295 will offer 297 and 299 1 coin.
And so on. In general, odd numbers will give 1 coin to all odd numbers and even numbers will give 1 coin to all even numbers, until they run out of coins.

The pattern does indeed become interesting after number 100 has to give away everything to keep his head. He survives, and so does 99, with 101 votes out of 201 and 202. 99 pays 100, but besides that the pattern is the same.

98 is killed paying 99 and even numbers because 101 votes is no longer enough. This means that the pirates need votes for free. As I overlooked originally, they will get free votes because those who know they will otherwise die will vote for them.
For example, 98 votes for 97 without being paid, and 97 survives with 102 votes out of 204 (97 pays who 98 would have).

96, 95 and 94 are killed, but with their support 93 makes 104 votes out of 208 (he pays 97, 98, 101 and odd numbers to 295).
92 to 86 are all killed, but with their support 85 makes 108 votes out of 216 (he pays 93 to 96, 99 and even numbers to 288).
84 to 70 are all killed, but with their support 69 makes 116 out of 232 votes (he pays 85 to 92, 97, 98, 101 and odd numbers to 279).

68 to 38 are all killed, and 37 is the final survivor who with their support makes 132 votes out of 264, and pays 69 to 84, 93 to 96, 99 and even numbers to 258.

I think we see that the pattern is that the number of free votes required keeps doubling. First 1, then 2, then 4, then 8, then 16, then 32 votes were required after the 100 coins were spent. It is clear enough that if there had been at least 28 more pirates, number 1 could have made a 164 out of 328 majority, confirming this pattern.

Last edited by Relentless (2015-12-16 15:00:55)

Offline

Board footer

Powered by FluxBB