recursion - Book Proofs

Should the grizzly eat the salmon?

This Riddler puzzle concerns a random process and sequential decision-making.

A grizzly bear stands in the shallows of a river during salmon spawning season. Precisely once every hour, a fish swims within its reach. The bear can either catch the fish and eat it, or let it swim past to safety. This grizzly is, as many grizzlies are, persnickety. It’ll only eat fish that are at least as big as every fish it ate before.

Each fish weighs some amount, randomly and uniformly distributed between 0 and 1 kilogram. (Each fish’s weight is independent of the others, and the skilled bear can tell how much each weighs just by looking at it.) The bear wants to maximize its intake of salmon, as measured in kilograms. Suppose the bear’s fishing expedition is two hours long. Under what circumstances should it eat the first fish within its reach? What if the expedition is three hours long?

Here is my solution:
[Show Solution]

Recurrence relation

The bear’s optimal decision of whether to eat the current salmon or not only depends on three things: the weight of the current salmon, the weight of the largest salmon caught so far, and the number of salmon remaining. Therefore, this problem is ideally suited for dynamic programming. We’ll write a recursion that solves the general case, and then we’ll specialize to the case of a two-hour or three-hour horizon.

Define $w_k(x,t)$ to be the expected weight of all of the salmon eaten from now on, assuming there are $k$ salmon remaining, the heaviest salmon eaten so far weighed $t$ kg, and the current salmon weighs $x$ kg. If $x \le t$, the bear cannot eat the salmon because it’s too light. If $x > t$, the bear must decide whether to eat the salmon or not. We therefore have the following recursion for expected future weight:

\[
w_{k+1}(x,t) = \begin{cases}
\mathbb{E}_\xi w_k(\xi,t) & \text{if }x \le t \\
\max\left\{ \mathbb{E}_\xi w_k(\xi,t) , \mathbb{E}_\xi \left( x + w_k(\xi,x) \right) \right\} & \text{if }x > t
\end{cases}
\]

In the case $x > t$, the bear makes the decision that maximizes the expected total salmon weight. The first and second choices correspond to letting the salmon go or eating it, respectively. Let’s now define the expected future salmon weight $f_k(t) = \mathbb{E}_x w_k(x,t)$, which is averaged over all possible current salmon weights. Expanding the recursion,

\begin{align}
f_{k+1}(t) &= \mathbb{E}_x w_{k+1}(x,t) \\
&= \int_0^1 w_{k+1}(x,t)\,dx \\
&= \int_0^t f_k(t)\,dx + \int_t^1 \max\left\{ f_k(t) ,\, x + f_k(x)\right\}\,dx \\
&= t f_k(t) + \int_t^1 \max\left\{ f_k(t) ,\, x + f_k(x)\right\}\,dx \\
&= f_k(t) + \int_t^1 \max\left\{ 0 ,\, x + f_k(x)-f_k(t) \right\}\,dx
\end{align}

The trivial base case is $f_0(t) = 0$, since with no more salmon the future weight is necessarily zero. With this recursion, we can now solve for the cases asked for in the problem statement, namely $f_2(0)$ and $f_3(0)$.

Greedy grizzly case

Let’s start with the simple case where the grizzly always eats every salmon whenever possible. The recursion then simplifies to:

\begin{align}
f_{k+1}(t) &= t f_k(t) + \int_t^1 \left( x + f_k(x) \right)\,dx \\
&= t f_k(t) + \tfrac{1}{2}(1-t^2) + \int_t^1 f_k(x) \,dx
\end{align}

Taking the derivative with respect to $t$ and simplifying, we obtain:

\[
f_{k+1}'(t) = t f_k'(t)-t
\]

Substituting in $f_{0}'(t)=0$ and iterating, we observe:

\[
f_{1}'(t) = -t,\qquad f_{2}'(t) = -t-t^2,\qquad f_{3}'(t) = -t-t^2-t^3,\qquad\ldots
\]

The pattern is clear, and $f_{k}'(t) = -t-t^2-\dots-t^k$. Now integrate from $1$ to $t$ and use the fact that $f_k(1)=0$ (can’t eat any more salmon if we’ve already had one of weight 1 kg) and obtain

\[
f_k(t) = \frac{1-t^2}{2}+\frac{1-t^3}{3}+\dots+\frac{1-t^{k+1}}{k+1}
\]

So when the grizzly is greedy, we have: $f_{k}^{\prime\prime}(t) = -1-2t-3t^2-\dots-kt^{k-1} \le 0$. Therefore $f_k(t)$ is a concave function. We’ll make use of this fact later… Starting with an empty stomach and a greedy grizzly, the expected salmon weight eaten is given by the formula

\[
f_k(0) = \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{k+1}
\]

This is a harmonic sum, which grows like $\log(k)$. So given infinite time, the persnickety (and greedy) grizzly can expect to eat an infinite quantity of salmon.

When is it best to be greedy?

It turns out the grizzly’s optimal strategy is to be greedy when there is 1, 2, or 3 salmon remaining. But if there are 4 or more salmon, the optimal strategy changes. To see why, recall our recurrence relation:

\[
f_{k+1}(t) = f_k(t) + \int_t^1 \max\left\{ 0 ,\, x + f_k(x)-f_k(t) \right\}\,dx
\]

If $x + f_k(x)-f_k(t) \ge 0$ for all $0\le t \le x \le 1$, then we should always be greedy for the $(k+1)^\text{st}$ salmon. Here, we’ll make use of the previously derived fact that when the grizzly is greedy, $f_k$ is concave. This means that $x + f_k(x)-f_k(t)$ is also concave in $x$, and nonnegativity can be verified by checking the endpoints $x=t$ and $x=1$. It’s always true for $x=t$, and for $x=1$ it’s equivalent to $1-f_k(t) \ge 0$ because $f_k(1)=0$ (can’t eat any more salmon if we’ve already had one of weight 1 kg).

Let’s examine each $k$ sequentially and see whether $1-f_k(t) \ge 0$ holds…

For 1 salmon: Recall that $f_0(t)=0$. Therefore:

\[
1-f_0(t) = 1 \ge 0
\]

So the grizzly is greedy with 1 salmon left, and therefore the previously derived formula holds: $f_1(t) = \frac{1-t^2}{2}$. The expected salmon weight is $f_1(0)=\tfrac{1}{2}$. This isn’t surprising; it’s the expected weight of one salmon!

For 2 salmon: Substitute $f_1(t) = \frac{1-t^2}{2}$ and find:
\[
1-f_1(t) = \tfrac{1}{2}+\tfrac{t^2}{2} \ge 0
\]

Therefore, the grizzly is greedy with 2 salmon left, and $f_2(t) = \frac{1-t^2}{2}+\frac{1-t^3}{3}$. The expected salmon weight is $f_2(0)=\tfrac{5}{6}$.

For 3 salmon: Substitute $f_2(t) = \frac{1-t^2}{2}+\frac{1-t^3}{3}$ and find:

\[
1-f_2(t) = \tfrac{1}{6}+\tfrac{t^2}{2}+\tfrac{t^3}{3} \ge 0
\]

Therefore, the grizzly is greedy with 3 salmon left, and $f_3(t) = \frac{1-t^2}{2}+\frac{1-t^3}{3}+\tfrac{1-t^4}{4}$. The expected salmon weight is $f_3(0)=\tfrac{13}{12}$.

For 4 salmon: Substitute $f_3(t) = \frac{1-t^2}{2}+\frac{1-t^3}{3}+\tfrac{1-t^4}{4}$ and find:

\[
1-f_3(t) = -\tfrac{1}{12}+\tfrac{t^2}{2}+\tfrac{t^3}{3}+\tfrac{t^4}{4} \ngeq 0
\]

Aha! this function is no longer nonnegative for all $t$ (take $t$ near zero). So in this case, if the heaviest salmon eaten weighed $t$ kg and the current salmon weighs $x$ kg, then the bear should eat the current salmon if $x + f_3(x)-f_3(t) \ge 0$ and leave the salmon alone otherwise. Here is what the decision boundary looks like:

The green region represents when the bear should eat the current fish, assuming there are four fish remaining including this one. The bottom red triangle in the picture is forbidden because the fish doesn’t weigh enough. The small top red region is forbidden because the fish is too heavy, i.e. $x + f_3(x)-f_3(t) < 0$.

The general case

Since the strategy for four salmon is no longer greedy, we must return to the original recursion in order to find $f_k$ for $k\ge 4$. It’s no longer possible to find analytic solutions, so we resort to a numerical approximation. Upon doing this, I found the optimal decision rules for the bear as a function of how many salmon remain. Here is the result in a single plot:

As before, we always reject fish below the dotted line. Each solid line corresponds to a decision boundary for a different number of fish remaining. Above the line, let the fish go. Below the line, eat the fish. The upper-most blue curve ($k=4$ fish remaining) is the same as the one plotted earlier. As one might expect, the more fish lie ahead, the pickier we must be at first in order to maximize final weight.

Now you might be wondering… How much worse is the greedy strategy? We can get a clear picture if we plot the expected total weight of salmon as a function of how many salmon remain:

Note that the greedy solution is simply the harmonic sum we derived earlier. As expected, the optimal strategy and the greedy strategy perfectly coincide when $k=1,2,3$. They’re very close when $k=4$, but not quite the same. When $k\ge 5$, we begin to see a noticeable difference. The curves keep getting farther apart as $k$ gets larger. Here is a zoomed out version of the same plot:

The greedy curve grows like $\log(k)$ while the optimal curve grows like $\sqrt{k}$, which is much faster indeed!

The Traitorous Generals

This Riddler problem is a logic puzzle about liars and truth-tellers.

You are the emperor of Byzantium (lucky you!) and you have N generals working for you. You know that more than half of your generals are loyal, and the rest are traitors. You can ask any general about the loyalty of any other general: If the general you ask is loyal, he will answer correctly, but if he is a traitor he can answer however he likes. Your goal is to find one general you are absolutely certain is loyal while asking the fewest possible questions.

What is the minimum number of questions (in terms of N) that will guarantee a solution, and what strategy produces it?

There is a problem in cryptography known as the Byzantine Generals Problem, which has to do with achieving consensus in the presence of traitors that can sabotage communications. The Riddler problem above also involves liars and truth-tellers, but it’s a very different problem.

The following is adapted from a comment by Guy Moore. A similar solution that obtains the same final result was also found by Dmytro Taranovsky. Thank you both for your insights!

[Show Solution]

The $N$ generals have the property that there is a loyal majority. This solution efficiently eliminates generals such that the remaining group of generals preserves the loyalty majority property. The strategy is:

If there is an even number of generals, eliminate one of the generals (doesn’t matter which).
If there is an odd number of generals, set one general aside. Pair up the rest of the generals and for each pair, ask the first general if the second one is a traitor.
- If the first general says the other is a traitor, eliminate both generals.
- If the first general says the other is loyal, eliminate the first general and keep the second.
If we kept an odd number of generals, eliminate the general that was set aside. Otherwise, re-include the general that was set aside.
If there is only one general left, this general is loyal and we may stop. Otherwise, return to the first step and repeat the process with the generals that are left.

Why does this work?

At each step, the loyalty majority property is preserved. To see why, let’s examine each case.

If the first general says the second is a traitor, they cannot both be loyal. Therefore, by eliminating both, we eliminate at least as many traitors as loyal generals.
If the first general says the second is loyal, we eliminate the first one. If the general that remains is a traitor, then both of them were traitors. This can happen for at most half of the pairs, since otherwise there would be a majority of traitors. If it happens for exactly half of the pairs, then the general we set aside must be loyal and so by re-including the general we set aside we retain loyal majority.
If there is only one general remaining, then the loyalty majority implies that this general must be loyal.

How well does the strategy perform?

If we have $k$ generals, we ask $\left\lfloor{\frac{k-1}{2}}\right\rfloor$ questions. In the worst case, each question leads to only one elimination. We also re-include the general we set aside depending on parity. So the number of generals remaining in the next round is:

\[
\begin{cases}
\left\lfloor\frac{k-1}{2}\right\rfloor & \text{if }k\text{ is odd}\\
\left\lfloor\frac{k-1}{2}\right\rfloor + 1 & \text{if }k\text{ is even}
\end{cases}
\]

This is equivalent to

\[
1 + 2\left\lfloor\frac{1}{2}\left\lfloor\frac{k-1}{2}\right\rfloor\right\rfloor = 1 + 2\left\lfloor\frac{k-1}{4}\right\rfloor
\]

We can make this simplification thanks to the nested division property of the floor function. So if $q(k)$ is the maximum number of questions required, we have the recursion:

\begin{align}
q(1) &= 0 \\
q(k) &= \left\lfloor{\tfrac{k-1}{2}}\right\rfloor + q\left( 1 + 2\left\lfloor{\tfrac{k-1}{4}}\right\rfloor \right)
\end{align}

If we define $f(k) = k-q(k+1)$ and do some rearrangements, we can write the following recursion for $f(k)$:

\begin{align}
f(0) &= 0 \\
f(k) &= k- \left\lfloor{\tfrac{k}{2}}\right\rfloor- 2\left\lfloor{\tfrac{k}{4}}\right\rfloor + f\left(1+2\left\lfloor{\tfrac{k}{4}}\right\rfloor\right)
\end{align}

It turns out that $f(k)$ is the number of 1’s in the binary representation of $k.$ Or, equivalently, $f(k)$ is the sum of the binary digits of $k$. I’ll omit the derivation, but you can work it out by writing $k$ in binary and noting that each operation does something simple to the digits. For example, if $x = abcde_2$ then $\lfloor x/2 \rfloor = abcd_2$. Therefore, we conclude that if there are $N$ generals, the number of questions required in order to ensure we can select a loyal general is:

$\displaystyle
q(N) = N-1-f(N-1)
$

where $f(k)$ is the number of 1’s in the binary representation of $k.$ Here is a plot showing the questions needed as a function of the number of generals.

We always require slightly fewer questions that there are generals, and we can bound the number of questions as:

\[
N-1-\log_2(N) \le q(N) \le N-2
\]

Random walk with endpoints

The Riddler post for today is about a bar game where you flip a coin and move forward or backward depending on the result. Here is the problem:

Consider a hot new bar game. It’s played with a coin, between you and a friend, on a number line stretching from negative infinity to positive infinity. (It’s a very, very long bar.) You are assigned a winning number, the negative integer -X, and your friend is assigned his own winning number, a positive integer, +Y. A marker is placed at zero on the number line. Then the coin is repeatedly flipped. Every time the coin lands heads, the marker is moved one integer in a positive direction. Every time the coin lands tails, the marker moves one integer in a negative direction. You win if the coin reaches -X first, while your friend wins if the coin reaches +Y first. (Winner keeps the coin.)

How long can you expect to sit, flipping a coin, at the bar? Put another way, what is the expected number of coin flips in a complete game?

Here is my solution:
[Show Solution]

This problem is famously known as Gambler’s ruin and it’s an example of a one-dimensional random walk. In the typical Gambler’s ruin setup, you flip a coin repeatedly and either gain \$1 or lose \$1 depending on the outcome. You have a fixed starting budget and a desired goal amount. You keep playing until either you have reached your goal amount, or you run out of money. The bar game we’re looking at here is precisely Gambler’s ruin, but shifted so that you start with \$0 and end when you’re either up \$Y or you’re \$X in debt.

Here is one possible solution. Let’s define $E_n$ to be the expected number of coin flips in a complete game assuming the marker starts at location $n$ on the number line. We would like to find $E_0$. Suppose that at each flip, we move forward with probability $p$ and backward with probability $q$ (where $p+q=1$). If we are currently at $n$, then with probability $p$, we came from $n-1$ and with probability $q$ we came from $n+1$. Either way, we incurred one additional flip. We can therefore write the following recurrence relations for the expected number of coin flips:

\begin{align}
E_{-X} &= 0 \\
E_n &= p E_{n-1} + q E_{n+1} + 1 \qquad\text{for }-X < n < Y\\ E_Y &= 0 \end{align} In matrix form, these equations look like: \[ \begin{bmatrix} 1 & -q & 0 & \dots & 0 \\ -p & 1 & -q & \ddots & \vdots \\ 0 & -p & 1 & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & -q \\ 0 & \dots & 0 & -p & 1 \end{bmatrix} \begin{bmatrix} E_{-X+1} \\ E_{-X+2} \\ \vdots \\ E_{Y-2} \\ E_{Y-1} \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ \vdots \\ 1 \\ 1 \end{bmatrix} \] This system of equations has a nice structure; the matrix on the left is both tridiagonal and Toeplitz. One can solve this system of equations using a specialized form of Gaussian elimination, for example.

Although the equations have a closed-form solution, it is pretty messy. Instead, I’ll show how you can derive the answer by hand in the case $p=q=\tfrac{1}{2}$. The last equation can be solved for $E_{Y-1}$ in terms of $E_{Y-2}$:

\[
E_{Y-1} = \tfrac{1}{2} E_{Y-2} + 1
\]

We can then substitute this into the second equation and solve for $E_{Y-2}$ in terms of $E_{Y-3}$:

\[
E_{Y-2} = \tfrac{2}{3} E_{Y-3} + 2
\]

Substitute into the third equation and solve for $E_{Y-3}$ in terms of $E_{Y-4}$:

\[
E_{Y-3} = \tfrac{3}{4} E_{Y-4} + 3
\]

The pattern is now clear (you can prove it using induction if you like). Continuing in this fashion until we get to the starting point,

\[
E_{1} = (1- \tfrac{1}{Y}) E_{0} + Y – 1
\]

We can do something similar but starting from the other end. e.g. solving for $E_{-X+1}$ in terms of $E_{-X+2}$, and then $E_{-X+2}$ in terms of $E_{-X+3}$, and so on. This time, we obtain the result:

\[
E_{-1} = (1- \tfrac{1}{X}) E_0 + X – 1
\]

We can now combine the fruits of our labor with the only equation we haven’t used yet, which relates $E_0$, $E_1$, and $E_{-1}$. The result is that:

\begin{align}
E_0 &= \tfrac{1}{2} E_{-1} + \tfrac{1}{2} E_1 + 1 \\
&= \tfrac{1}{2}\left( (1- \tfrac{1}{X}) E_0 + X – 1 \right) + \tfrac{1}{2} \left( (1 – \tfrac{1}{Y}) E_0 + Y – 1 \right) + 1\\
&= \tfrac{1}{2}\left( 2- \tfrac{1}{X} – \tfrac{1}{Y} \right) E_0 + \tfrac{1}{2}(Y + X)
\end{align}

Rearranging and solving for $E_0$, we obtain:

$\displaystyle
E_0 = \frac{ Y + X }{ \tfrac{1}{X} + \tfrac{1}{Y} } = XY
$

A similar approach can be used to compute the probability that each player will win. To do this, let $P^Y_n$ be the probability that we’ll reach $Y$ first given that we are currently at $n$, and similarly define $P^X_n$. Then the recursions look like:

\begin{align}
P^Y_{-X} &= 0 \\
P^Y_n &= p P^Y_{n-1} + q P^Y_{n+1} \qquad\text{for }-X < n < Y\\ P^Y_Y &= 1 \end{align} Written as matrices, the only difference between this problem and that of finding expectation is the right-hand side of the equation! Using a similar recursive approach, we can solve the equations and we obtain:

$\displaystyle
P_0^X = \frac{Y}{X+Y} \qquad\text{and}\qquad P_0^Y = \frac{X}{X+Y}
$

So, practically speaking, if we must travel twice as far on the number line as our opponent, we are half as likely to win the game. Just for fun, I made some plots that show how the expected value and the probability of winning change if you’re not using a fair coin. The plots show the case where $X+Y = 50$. For example, the 40% curve means that the coin flips in your favor 40% of the time.

If you’re interested in a derivation of the solution for the case $p\ne \tfrac{1}{2}$, there is a well-written set of notes here.

and here is a much slicker solution, courtesy of Daniel Ross:
[Show Solution]

The blue-eyed islanders

Today’s Riddler problem is another classic. The current incarnation of the puzzle is about error-prone mathematicians, while the classic version is about blue-eyed islanders.

A university has 10 mathematicians, each one so proud that, if she learns that she made a mistake in a paper, no matter how long ago the mistake was made, she resigns the next Friday. To avoid resignations, when one of them detects a mistake in the work of another, she tells everyone else but doesn’t inform the mistake-maker. All of them have made mistakes, so each one thinks only she is perfect. One Wednesday, a super-mathematician, whom all respect and believe, comes to visit. She looks at all the papers and says: “Someone here has made a mistake.”

What happens then? Why?

Here is the solution:
[Show Solution]

On the tenth Friday, all mathematicians will resign. To understand why this happens, we’ll use a recursive approach similar to what we did for the puzzle of the pirate booty.

For simplicity, we’ll say a mathematician is flawed if they made a mistake, and perfect otherwise. Let’s look at the world through the eyes of Alice, one of the ten mathematicians. Alice doesn’t know whether she is flawed or not. She does, however, know how many of her colleagues are flawed.

According to the problem statement, all the mathematicians are flawed. So Alice sees that all nine of her colleagues are flawed. Let’s solve a simpler version of the problem first. What if none of Alice’s colleagues were flawed? In this case, the news that “someone here has made a mistake” can only mean one thing: that “someone” must be Alice! So Alice will resign on Friday.

What if exactly one of Alice’s colleagues is flawed? Two possibilities:

If Alice is perfect, then the flawed mathematician will see that everyone else is perfect and resign on Friday, just as Alice would have done in the previous case when she saw her colleagues were all perfect.
If Alice is flawed, then nothing happens on Friday. Alice then deduces that she must be flawed and resigns on the next Friday.

What if exactly two of Alice’s colleagues are flawed? Two possibilities:

If Alice is perfect, then each flawed mathematician sees one other flawed mathematician. As in the previous case, we expect them to both resign on the second Friday.
If Alice is flawed, then nothing happens on the second Friday. In that case, Alice will know of her flaw and resign on the third Friday.

The pattern is clear: if Alice has $k$ flawed colleagues but Alice is perfect, then the flawed mathematicians all resign on the $k^\text{th}$ Friday. If Alice is flawed, then nothing happens on the $k^\text{th}$ Friday, and Alice resigns on the $(k+1)^\text{st}$ Friday (along with all the other flawed mathematicians). In particular, if all ten mathematicians are flawed as in the problem statement, they all resign on the tenth Friday.

But but but…

It seems that we have a paradox — we aren’t telling the mathematicians anything they don’t already know! Each mathematician can clearly see that they have flawed colleagues, so why should explicitly announcing this fact make any difference? The answer lies in the distinction between mutual knowledge and common knowledge.

If everybody knows some proposition $P$ to be true, then $P$ is mutual knowledge. However, if everybody knows $P$, and everybody knows that everybody knows $P$, and everybody knows that everybody knows that everybody knows $P$, and so on, then $P$ is common knowledge. Although the fact that there is at least one flawed mathematician is mutual knowledge, it is not common knowledge. When the super-mathematician makes her announcement that there is at least one flawed mathematician, it becomes common knowledge, and this makes all the difference.

Rather than giving a detailed solution, I will defer to some other existing solutions online that are already well-explained. No need to reinvent the wheel! Here are some pointers.

The solution to the blue eyes puzzle featured on the xkcd website.
The wikipedia article on common knowledge, which uses the blue eyes puzzle as an illustrative example.
A post on the math stackexchange site that gives a detailed an formal proof of result.

The puzzle of the pirate booty

Today’s puzzle was posed on the Riddler blog, but it’s actually a classic among problem-solving enthusiasts, and is commonly known as the pirate game. Here is the formulation used in the Riddler:

Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.

The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)

Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:

Self-preservation: A pirate values his life above all else.

Greed: A pirate seeks as much gold as possible.

Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.

Under this system, how do the PRPLs divide up their gold?

Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.

Here is the solution to the main problem:
[Show Solution]

This problem is a perfect example of when to use recursion. If there are $P$ pirates, when each pirate contemplates how to vote, they are comparing what would happen if they voted yes (and agreed to the current proposal) to what would happen if they voted no (and the current pirate died, reducing to the $P-1$ case).

Let’s start with two pirates and build up from there. For each case, here is a list of each pirates’ share of the gold. We ordered the pirates from lowest rank to highest rank (captain).

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & 10 \end{bmatrix} && 1\\
v_3 &: \begin{bmatrix} 1 & 0 & 9 \end{bmatrix} && 2\\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & 9 \end{bmatrix} && 2\\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 8 \end{bmatrix} && 3\\
v_7 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_8 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 7 \end{bmatrix} && 4\\
v_9 &: \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5 \\
v_{10} &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 6 \end{bmatrix} && 5
\end{align}

Let’s examine this table one row at a time. If there are two pirates ($v_2$), a majority is decided by a single vote. Since the captain gets to vote, they can safely propose to keep all the gold.

If there are three pirates ($v_3$), a majority is decided by two votes. So the captain needs to secure one extra vote. The first pirate (lowest rank) won’t win anything if the captain dies, because we would reduce to the $v_2$ case. The captain must give this pirate at least one gold piece to buy their vote and avoid death, but can keep the remaining $9$ pieces.

Similarly, if there are four pirates ($v_4$), a majority is decided by two votes. This time, the first pirate’s vote costs two gold pieces because they stand to win one gold piece if we reduce to $v_3$. However, the second pirate’s vote now costs one gold piece because they win nothing in the $v_3$ case. A similar argument applies as we continue to add pirates.

The final solution is that if we number the pirates $1,2,\dots,10$ in order from lowest rank to highest rank, then pirates $2,4,6,8$ each get one gold piece and the captain gets $6$ gold pieces.

And here is a solution to the general case:
[Show Solution]

As we saw in the previous solution, it makes sense to recurse on $P$, the number of pirates. If $G$ is the number of gold pieces, the pattern we observed in the simpler case still hold here, and we can continue it until the captain runs out of gold and is no longer able to bribe enough of his fellow pirates. So the table looks like:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_2 &: \begin{bmatrix} 0 & G \end{bmatrix} && 1 \\
v_3 &: \begin{bmatrix} 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_4 &: \begin{bmatrix} 0 & 1 & 0 & G-1 \end{bmatrix} && 2 \\
v_5 &: \begin{bmatrix} 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
v_6 &: \begin{bmatrix} 0 & 1 & 0 & 1 & 0 & G-2 \end{bmatrix} && 3 \\
&\vdots &&\vdots\\
v_{2G+1} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 \end{bmatrix} && G+1\\
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1
\end{align}

In the last two rows of the table, there are $G$ 1’s. In the case with $2G+2$ pirates, a majority is decided by $G+1$ votes, so the captain wins nothing; they must forfeit all the gold in order to buy the votes necessary to survive. From this point forward, it may seem that if we add any additional pirates, they will be killed because there isn’t enough gold to buy enough votes. However, this isn’t quite the case. Here is what happens if we keep adding pirates:

\begin{align}
&\quad\text{Gold distribution} &\text{Votes}&\text{ needed}\\ \hline
v_{2G+2} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 \end{bmatrix} && G+1 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}3}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}2 \\
v_{2G+4} &: \begin{bmatrix} 1 & 0 & \dots & 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} && G+2 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}5}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}6}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} \end{bmatrix} && \color{red}G\color{red}+\color{red}3 \\
{\color{red}v_{\color{red} 2\color{red}G\color{red}+\color{red}7}} &: \begin{bmatrix} ? & ? & \dots & ? & ? & ? & ? & ? & ? & {\color{red}0} & {\color{red}0} & {\color{red}0} \end{bmatrix}\hspace{-2cm} && \color{red}G\color{red}+\color{red}4 \\
v_{2G+8} &: \begin{bmatrix} 0 & 1 & \dots & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\hspace{-2cm} && G+4
\end{align}

Once we get to $P = 2G+3$ pirates, the captain will always be killed (deaths are indicated in red) since there isn’t enough gold to buy the required votes. In the $2G+4$ case, however, the second in command is doomed to die if he votes to kill the captain, so he will vote yes even if offered nothing. This gives the captain a free vote, which is enough to secure the required $G+2$ votes. The captain must make an offer that compares favorably to the $2G+2$ case since the intermediate case $2G+3$ always leads to $2G+2$.

In the $2G+5$ case, none of the pirates have an incentive to keep the captain alive (since everybody will be safe with $P=2G+4$). The same happens with $2G+6$ and $2G+7$. Once we arrive at $2G+8$, three of the pirates are doomed if the captain dies, so they will vote yes even if offered nothing. Once again, this allows the captain to barely survive. This pattern continues, each time doubling the interval length between safe captains.

The solution to the general problem. Number the pirates $1,2,\dots,P$ in order from lowest rank to highest rank. If we have $G$ gold pieces to distribute, then we consider two cases:

If $P \le 2G+2$, then:

If $P$ is odd, pirates $1,3,5,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-1}{2}$ pieces.
If $P$ is even, pirates $2,4,6,\dots,P-2$ each get one gold piece, and the captain gets the remaining $G-\frac{P-2}{2}$ pieces.

If $P > 2G+2$, then the highest ranked captains will die until there are $P = 2G+2^k$ pirates remaining with $k$ as large as possible. Then:

If $k$ is even, pirates $1,3,5,\dots,2G-1$ each get one gold piece and nobody else gets anything.
If $k$ is odd, pirates $2,4,6,\dots,2G$ each get one gold piece and nobody else gets anything.

In the case where $P \ge 2G+2$, the solution is not unique in the sense that once we arrive at $P=2G+2^k$, there are other admissible ways of dividing up the gold besides the one shown above.

If this sort of problem interests you, I recommend taking a crack at the riddle of the blue-eyed islanders, or the unfaithful husbands. More information here as well.