Let's put the number of coins at $c$ and see what happens if we increase $n$. We'll number the pirates from meekest ($1$) to fiercest ($n$).
| Nr. of pirates | Pirate<br>meekest to fiercest | Nr. of coins | Vote |
|---------------:|------------------------------:|-------------:|:-----|
| 1 | 1 | c | yes |
| 2 | 1<br>2 | 0<br>c | no<br>yes **breaks tie** |
| 3 | 1<br>2<br>3 | 1<br>0<br>c-1 | yes<br>no<br>yes |
| 4 | 1<br>2<br>3<br>4 | 0<br>1<br>0<br>c-1 | no<br>yes<br>no<br>yes **breaks tie** |
| 5 | 1<br>2<br>3<br>4<br>5 | 1<br>0<br>1<br>0<br>c-2 | yes<br>no<br>yes<br>no<br>yes |
| ... | | | |
| 2c | 1<br>2<br>3<br>...<br>n | 0<br>1<br>0<br><br>1 | no<br>yes<br>no<br><br>yes **breaks tie** |
If we define a solution as stable if nobody gets fed to the sharks, we can say that all solutions so far have been stable. This is because for each $n$, there are more or at least as much (in which case the tie is broken) pirates who would be worse off in the solution for $n-1$.
But now, we're at $n = 2c + 1$. Are we getting ready for carnage? Not quite:
| Nr. of pirates | Pirate<br>meekest to fiercest | Nr. of coins | Vote |
|---------------:|------------------------------:|-------------:|:-----|
| 2c+1 | 1<br>2<br>3<br>...<br>n-1<br>n | 1<br>0<br>1<br><br>0<br>0 | yes<br>no<br>yes<br><br>no<br>yes |
Here, the fiercest pirate can escape alive, but without gold.
Okay, but now surely the sharks are getting fed? Let's see.
| Nr. of pirates | Pirate<br>meekest to fiercest | Nr. of coins | Vote |
|---------------:|------------------------------:|-------------:|:-----|
| 2c+2 | 1<br>2<br>3<br>...<br>n-2<br>n-1<br>n | 0<br>1<br>0<br><br>1<br>0<br>0 | no<br>yes<br>no<br><br>yes<br>no<br>yes **breaks tie** |
The fiercest pirate now broke the tie to stay alive.
How about $n = 2c + 3$ then?
| Nr. of pirates | Pirate<br>meekest to fiercest | Nr. of coins | Vote |
|---------------:|------------------------------:|-------------:|:-----|
| 2c+3 | 1<br>2<br>3<br>...<br>n-3<br>n-2<br>n-1<br>n | 1<br>0<br>1<br><br>0<br>0<br>0<br>0 | yes<br>no<br>yes<br><br>no<br>no<br>no<br>yes **shark bait** |
Here, finally, at $n = 2c + 3$, we reach our first unstable solution. The fiercest pirate can buy $c$ votes, adds his own vote for a total of $c+1$, but the opposition has $c + 2$ votes.
Note that here, pirate $n-3$ is pirate $n-2$ from the solution before it. Voting $\text{no}$ yields a coin. Pirates $n-2$ and $n-1$ get no gold by voting against this proposal, but as per the third rule, vote to feed the sharks.<sup>‡</sup>
But does that mean that from now on, all pirates get their feet wet? Not at all.
| Nr. of pirates | Pirate<br>meekest to fiercest | Nr. of coins | Vote |
|---------------:|------------------------------:|-------------:|:-----|
| 2c+4 | 1<br>2<br>3<br>...<br>n-4<br>n-3<br>n-2<br>n-1<br>n | 1<br>0<br>1<br><br>0<br>0<br>0<br>0<br>0 | yes<br>no<br>yes<br><br>no<br>no<br>no<br>yes **potential shark bait**<br>yes **breaks tie** |
Now both the fiercest pirate and the almost-as-fierce pirate are voting for their lives, since the solution with one pirate less is unstable and will see the almost-as-fierce pirate being fed to the sharks. The fiercest pirate breaks the tie and this solution is stable.
| Nr. of pirates | Pirate<br>meekest to fiercest | Nr. of coins | Vote |
|---------------:|------------------------------:|-------------:|:-----|
| 2c+5 | 1<br>2<br>3<br>...<br>n-5<br>n-4<br>n-3<br>n-2<br>n-1<br>n | 0<br>1<br>0<br><br>1<br>0<br>0<br>0<br>0<br>0 | no<br>yes<br>no<br><br>yes<br>no<br>no<br>no<br>no<br>yes **shark bait** |
| 2c+6 | 1<br>2<br>3<br>...<br>n-6<br>n-5<br>n-4<br>n-3<br>n-2<br>n-1<br>n | 0<br>1<br>0<br><br>1<br>0<br>0<br>0<br>0<br>0<br>0 | no<br>yes<br>no<br><br>yes<br>no<br>no<br>no<br>no<br>yes<br>yes **shark bait** |
| 2c+7 | 1<br>2<br>3<br>...<br>n-7<br>n-6<br>n-5<br>n-4<br>n-3<br>n-2<br>n-1<br>n | 0<br>1<br>0<br><br>1<br>0<br>0<br>0<br>0<br>0<br>0<br>0 | no<br>yes<br>no<br><br>yes<br>no<br>no<br>no<br>no<br>yes<br>yes<br>yes **shark bait**
| 2c+8 | 1<br>2<br>3<br>...<br>n-8<br>n-7<br>n-6<br>n-5<br>n-4<br>n-3<br>n-2<br>n-1<br>n | 0<br>1<br>0<br><br>1<br>0<br>0<br>0<br>0<br>0<br>0<br>0<br>0 | no<br>yes<br>no<br><br>yes<br>no<br>no<br>no<br>no<br>yes **potential shark bait**<br>yes **potential shark bait**<br>yes **potential shark bait**<br>yes **breaks tie** |
And we've found a stable one again.
| Nr. of pirates | Pirate<br>meekest to fiercest | Nr. of coins | Vote |
|---------------:|------------------------------:|-------------:|:-----|
| 2c+9 | 1<br>2<br>3<br>...<br>n-9<br>n-8<br>n-7<br>n-6<br>n-5<br>n-4<br>n-3<br>n-2<br>n-1<br>n | 1<br>0<br>1<br><br>0<br>0<br>0<br>0<br>0<br>0<br>0<br>0<br>0<br>0 | yes<br>no<br>yes<br><br>no<br>no<br>no<br>no<br>no<br>no<br>no<br>no<br>no<br>yes **shark bait** |
And so on.
When $n > 2c$, we'll see more and more large runs of downvoting pirates, until the number of pirates upvoting to save their lives becomes equal to the number of downvoters and we find a stable solution again.
----
This yields the following formula for stable solutions:
$$ n \leq 2c \lor n = 2c + 2^z\,|\,z \in \mathbb Z_{\ge 0}$$
The procedure by which to distribute the coins is based on the fact that a pirate can only buy votes if coins are given to the opposite pirates from the next stable solution.
It is as follows:
* For $n \leq 2c$ give a coin to every pirate with the same parity as $n$, with any left over coins going to the fiercest pirate.
* For $2c + 2^{z-1} < n \leq 2c + 2^z\,|\,z \in \mathbb Z_{\ge 0}$ start with the meekest pirate with the opposite parity of $z$ and move up in ferocity.<sup>†</sup>
----
<sup>
‡: I prefer to think of the pirates as kindhearted people who <em>care</em> for the sharks and don't want them to go hungry.<br />
†: It can be argued that if a solution is known to be unstable, <em>all</em> other pirates will vote no, since it doesn't matter who gets the coins — they won't get to keep them. But for the stable solution, it <em>is</em> necessary to distribute the coins like this.
</sup>