1
$\begingroup$

I have a question quite similar to the 5 pirates and 100 coins puzzle, but mine is slightly different. Hopefully you can help me understand, because this question is a doozie.

There are N pirates on a ship, who have found 3 pieces of gold. Each pirate has the following priorities:

Life > Gold > Watching a pirate walk on a plank > Nothing

Essentially, each pirate values their own life over gold, and would rather win gold than watching their fellow pirates walk the plank. However, each pirate is definitely bloodthirsty, and would rather watch their peers die by the plank if anything. Also, do note that each pirate is infinitely intelligent and will make perfect decisions, if one exists.

The Nth pirate must make a division of gold across all N pirates.

If 50% or more are in favor of the proposed distribution of gold, then that pirate survives, and the planned gold distribution is carried out. If not, the pirate walks the plank, and the (N-1)th pirate is the next to propose a distribution.

Whats the maximum number of pirates that can survive on the vessel?

$\endgroup$
  • 1
    $\begingroup$ Could someone kindly help to our new user to edit their post with proper English? $\endgroup$ – Matsmath Nov 2 '16 at 22:46
  • $\begingroup$ Edited, waiting for approval. $\endgroup$ – greenturtle3141 Nov 2 '16 at 23:03
  • $\begingroup$ I think it is already solved by this answer that explains the general case ( c coins and n pirates ) $\endgroup$ – Fabich Nov 2 '16 at 23:28
6
$\begingroup$

I propse that the answer is:

$2^{\lfloor \log_2{(N-6)} \rfloor} + 6$

Reasoning:

Simply use the same method of solving the puzzle backwards.

To review the base logic, start with $2$ pirates. In this case, the pirate proposing the distribution can simply take all $3$ coins and vote for his own proposal, and the lesser pirate is powerless.

With $N=3$ pirates, the lesser pirate described previously can simply be bribed with one coin to accept the proposal, and the pirate proposing the distribution will take the rest of the 2 coins. However, the pirate second in line will receive nothing.

Repeating this logic, we eventually reach $N=7$ and $N=8$, where we are at the "tipping" point.

PIRATES

As you can now see, in these scenarios, the proposing pirate barely lives, and can't even keep coins for himself. He needs each coin to bribe alternating pirates to vote for his survival.

Now, consider $N=9$. The proposing pirate can give his coins to the last, third to last, and fifth to last pirates. The second in command has no reason to vote against this, since he will get no coins anyway, right??!?

But you see, the second in command will rather enjoy the drowning of his peer. He will surely vote against him. Bloodthirtiness did not take much part in the classical 5 pirates and 100 coins, but now the lack of morality comes into play here.

Alright, so his reasoning for voting against the proposal is to see blood. However, can he not be bribed by a coin? The answer is no. If you "move" a coin from one pirate to another, the prior pirate will get no coins, and won't get coins in the next proposal either. He will rather see bloodshed, and will just vote against the proposal.

$N=10$. The proposing pirate forsees the death of his second in command. Serely he will do everything he can do not die. If the proposing pirate walks the plank, the second in command will also walk the plank, as proven previously. The coins will bribe 3 pirates, and the seocnd in command doesn't want to die, and also, the proposing pirate will vote for himself. That makes 5 pirates in agreement, versus the other 5. For $N=10$, the proposing pirate can survive by a flippin hair!

$N=11$. Proposing pirate dies for obvious reasons. Sad.

$N=12$. Also hopeless. The second in command will vote in favor in fear of death. However, the same logic does not apply to the fourth pirate, who forsees that thie third pirate will live by a hair ($N=10$). May as well enjoy the show of death, right? To the plank!

$N=13$. Second and third pirates can see their respective deaths. It's not looking good. The proposing pirate would like to live as well. $3$ (I want to live) $+ 3$ (coins) $= 6$. Not enough. Death.

$N=14$. Second, third, AND fourth pirates are now scared af. $4+3 = 7...$ damn. Proposing pirate survives this one. Note that each of these pirates should be able to trust that they will mutually agree to vote in favor to cling on to their lives.

INTERMISSION

We need to analyze what happened. After the $N = 10$ peak, as $N$ increased, the pirates under the tenth pirate generally didn't really give much of a crap anymore and voted for a show of death and overhydration. However, with increasing $N$, comes with increasing hypothetical dead pirates, which increased the number of pirates voting in agreement for the proposal, because their life is at stake.

Using this logic, we can identify the next peak. At this stage, anyone under the 14th pirate will surely vote for death for $N>14$ unless bribed by the coins. For some N, the number of pirates voting for their life will be $N - 14$. Therefore, we have the equation,

$N - 14 + 3 \geq \frac{N}{2} $

Solving with trivial algebra, we get $N = 22$. The proposing pirate will vote for himself, and pirates #2 to #8 will be executed if this proposal doesn't go through. That means, there are currently 8 votes for the proposal. Add in the 3 coins for bribing, we get 11 total votes, in which the pirate lives by an atom.

We are now in position to find a general formula. Consider the sequence $A_n$ which contains the sequence of numbers of pirates in which the proposing pirate lives, but barely. In essence, we exclude the "trivial" cases $N \in [1, 7]$. We let $A_1$ = 8, and establish the following recurrence relation based on previous developments:

$A_n - A_{n-1} + 3 = \frac{A_n}{2}$

$A_n = 2A_{n-1}-6$

The recurrence solution, with work ommitted (I used wolfram alpha, but shhh), is:

$A_n = 2^n + 6$

With $N$ pirates, the number of pirates that will live is the greatest number in $A_n$ that is less than N itself. To do this, we substitute $N$ for $A_n$, solve for $n$, and take the floor.

$N = 2^n + 6$

$n = \lfloor \log_2{(N-6)} \rfloor$

Now we just plug it back in.

$\boxed{2^{\lfloor \log_2{(N-6)} \rfloor} + 6}$

This... this took some time to write... I hope I didn't mess up ._.

EDIT: It actually appears that the problem was already completely generalized. Eh, oh well.

Pirates and gold coins

$\endgroup$
  • 1
    $\begingroup$ very clear explanation ! $\endgroup$ – Fabich Nov 3 '16 at 0:42
0
$\begingroup$

It seems that

For any N > 7, everyone will always stay alive.
1,2,3 get a coin and vote ok
4,5,6 are in no danger so vote not ok
7 and over all vote ok because they know they will die next if they don't stop the process now.
For N < 8 It would seem that 6 pirates will survive. Not sure what happens when the votes are split 50/50

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.